Auto comment: topic has been updated by flaviu2001 (previous revision, new revision, compare).

Why is it getting WA on pretest 4?

void solve(int test_case){
	int i, j;
	int x, y;
	cin >> x >> y;
	vector<int> c(7);
	for(i=1;i<=6;i++)cin >> c[i];
	c[1] = min(c[1] , c[6]+c[2]);
	c[2] = min(c[2] , c[1]+c[3]);
	c[3] = min(c[3] , c[2]+c[4]);
	c[4] = min(c[4] , c[3]+c[5]);
	c[5] = min(c[5] , c[4]+c[6]);
	c[6] = min(c[6] , c[5]+c[1]);
	
	int ans;
	if(x <= 0 && y <= x){
		int dist = (c[4])*abs(x);
		ans = dist+c[5]*abs(y-x);
	}else if(x <= 0 && y >= 0){
		int dist = (c[3])*abs(x);
		ans = dist+c[2]*abs(y);
	}else if(x <= 0){
		int dist = (c[3])*abs(x);
		ans = dist+c[4]*abs(y);
	}else if(y >= x){
		int dist = (c[1])*abs(x);
		ans = dist+c[2]*abs(y-x);
	}else if(y <= 0){
		int dist = (c[6])*abs(x);
		ans = dist+c[5]*abs(y);
	}else if(y > 0){
		int dist = (c[6])*abs(y-x);
		ans = dist+c[1]*abs(x);
	}cout << ans << '\n';
	return;
}

UPD: submission

I overkilled B initially by using BFS. Then I realized that it can be done by using just a couple of 'if' conditions.

Wow so fast editorial!

C's testcase contains a major hint.

Another way to go about D is to think of the hexagonal world as a regular 2D grid, where you can move from (0,0) to six directions. [all directions except (-1,1) and (1,-1)]

Then it's just checking all the possible routes.

NB: The image is not uploading correctly for some reason. If somebody knows why, please let me know. Thanks.

А кто-нибудь знает, где найти разбор на русском?

Feeling depressed after seeing the solution of C and also that I thinked on it for an Hour , I got the hint part while thinking , but didn't got that we can move n-1 to n+1 .

For A, even OR works (a^(a|b))+(b^(a|b))

Another way to solve A is we can find the minimum value if we take same 2 digits like 6^6 is zero. so we can take the minimum value from a and b and put that value in x and solve the equation as it said. Simple as that.

Strong pretests for B https://www.imageupload.net/image/inkedadsiz-li.tW8IJ

Can someone please explain the dp solution in E? Thanks in advance :-)

How didn't this solution 95865345 get RE on pretests?

Edit: nvm

After solving A-D : Why did I learn algorithms ? ;ㅅ;

I had a bit different solution to D.

it is easy to notice, that we need to move on diagonals, or straight line. And, number of different points we need is quite small. After drawing on piece of paper it is obvious that we need only some cominations of $$$x, y, x-y, y- x$$$. So, I added points $$$(0, x), (0, y), ...$$$ (ones on staight gorizontal line with $$$(0; 0)$$$), then $$$(x, 0), (y, 0) ... $$$ — first diagonal, and $$$(x, x), (y, y) ... $$$ on second.

We have 14 points, it`s easy to calculater distance between points on same diagonal or line. After doing so I run Floyd-Warshall on this graph, so all solution works in $$$O(14^3) = O(1)$$$;) per test case.

Code.

How to find the pattern of problem E in 24 minutes like kefaa2? I found it hard for me to solve this kind of problem...

Why my similar approach isn't working for C

for example:
abcd
cbabcd
cbabcd cbab
cbabcdcbab abc

printf("L %d\n",n-1);
printf("R %d\n",n-2+1);
printf("R %d\n",n-2+ n + 1);

So fast OoO

On problem B, can anyone please tell me what does this statement really means "Waters can move from a square to any other square adjacent by a side, as long as he is still in the grid". Can Waters move from grid[i][j] to grid[i+1][j+1]?

I really hope this hint/solution format of editorials becomes the norm :)

Explain this solution to me please. what is delta? what is delta_a what is delta_b?? I think a and b are the mvoes along the i and j axis. but i cant find formula for delta_a and delta_b. Thanks 95917963 stefdasca

Magical DP for E: 95899682

Please help! why i am getting wrong answer in Div2/C on test case 1

define ll long long int

int main() {

string s;
    cin>>s;
   ll n= s.size();
    ll i,ans=0;
    for(i=0;i<(s.size()/2);i++)
    {
        if(s[i] == s[n-i-1])
            ans++;
    }
    if(ans == n/2)
    {
        cout<<"0"<<endl;
    }
    else
    {
        cout<<"1"<<endl;
        cout<<"L"<<" "<<n<<endl;
    }

}

Can someone explain what's the intuition behind the pattern in Problem E. DP aside, it seems very hard to just observe that pattern from the problem. The tutorial proves that it's right but how can we come up with something like that in the contest.

UPD: Found the bug!

Can anyone tell me the detailed solution of Problem D. I got the part that we need to consider only two edges but how to calculate the distance after that?

I didn't think about quadrants and shortest paths in problem D

Can someone please explain a solution which involves linear algebra/matrices on problem D?

More like IfElseForces.

An interesting adaption based on B: For a given graph, what is the minimum number of invertions we need to make so that Pink Floyd can successfully go through (1,1) to (n,n)?

For example:

4
S000
0000
0001
001F

Then the answer should be 1. For if we invert the cell (3,4), Pink Floyd can go from (1,1) to (n,n). And it can be proved that 1 is the most optimal answer. So how to solve this?

I am surprised that nobody I've seen did binary search for D... (The official solution seems easier, though :p)

I'm sorry if this is duplicated question. Why problems aren't rated after contests?

I got the idea for B using 16 if-else immediately. But later spent 1 hr thinking how to implement it better. Finally ended up with an 8 if-else implementation.. Should have gone with the 16 if-else implementation itself...

How to prove the conclusion of E((n+m)%3=1) via induction？

It's very nice to see this form of Tutorial.Thanks a lot!

MikeMirzayanov any updates when will rating get updated for previous rounds problems ?

Can someone explain why ternary search will work for D? I mean ternary search like this:

We do ternary search on distance moved along $$$y=x$$$ using C1 or C4. Then for remaining we use the Manhattan distance and use the required amount of other direction vectors. Why does this function always form a V shaped graph?

How to do it for multiple bits? Single bit proof is trivial for this : We'll leave it up to you to prove that (a ⊕ (a & b)) + (b ⊕ (a & b)) = a ⊕ b, where ⊕ is the bitwise XOR.

Upd: I got the proof. Thanks.

If you print:

3
L 2
R 2
R 2n-1

At C task, you'll get ac too, it's good to think about that.

The solution for D is tiring. I'm bored of it.

D could be solved by running Simplex without making any observations :b

problem C: Palindromifier

consider substring s[2...(n-1)] as a single character. Now you get a string of length 3.

now apply

1. R 2

2. L n

3. L n-1

works!

example "abc" here 'b' is s[2...(n-1)

after operation 1=> abcb //here 1st b is actual b and 2nd one is reversed

after operation 2=> cbabcb // 1st b is reversed , 2nd one is actual and 3rd one is reversed

after operation 3=> bcbabcb // 1st b is actual, 2nd one is reversed, 3rd one is actual and 4th one is reversed

I struggled to solve problem D even after reading the editorial and the comments so I will try to explain it my way:

• we can notice that each cell(hexagon) can be indicated by (x,y) coordinates same as the picture in the problem statement
  
• but we can notice also that each cell can be indicated as diagonals coordinates
  
• we have 2 types of diagonals: main diagonal(/) we call it d1 and secondary diagonal() we call it d2
  
• so each cell can be indicated by (d1,d2) coordinates
  
• to convert from (x,y) coordinates to (d1,d2):
  notice that all the cells on the same main diagonal have the same value y-x
  notice that all the cells on the same secondary diagonal have the same value y
  so to convert we do this: (d1,d2) = (y-x,y)
  
• so we will use the (d1,d2) coordinates instead of (x,y) coordinates in the problem statement we have six operations with costs C1,C2,...C6 each operation might change d1 or d2 or both so the ops array(in my code) stores the changes of d1 and d2(d1x and d2x) of each operation

• the numbering of the operations follows the one in the picture in the problem statement
  
  
  

• lets prove that only 2 operations are required in the optimal solution:
  as we know each operation has another opposite operation
  op1 opposite of op4
  op2 opposite of op5
  op3 opposite of op6
  that means in the final solution we can use at most 3 operations out of the six because using the operation and it's opposite has no benefit
  

• we can also notice that to be able to use 3 operations they have to be adjacent operations in order to avoid using opposite operations together, for example you can use
  (op1,op2,op3) or (op2,op3,op4) .... or (op6,op1,op2) and lets call each one a triplet
  
• we can notice that for each triplet the middle operation can be replaced by the other 2
  operations in the same triplet:
  (op1,op2,op3) --> op2 = op1 + op3
  (op2,op3,op4) --> op3 = op2 + op4
  .......
  (op6,op1,op2) --> op1 = op6 + op2
  
• in the same way we can say for each triplet the other 2 operations can be replaced by the middle one (we choose according to the minimum cost)
  
• so if we have a valid solution(not necessary minimal solution) this solution will use one of the triplets
  and if we do operation replacement for example (replace op2 by op1+op3 or replace op1+op3 by op2)
  we end up with only 2 operations in the solution(think about it and try it on paper)
  
• that means the final solution will have only 2 operations where we have to do the replacement to minimize the cost
  

• to solve the problem we need to shift the start cell (0,0) to the target cell using 2 operations and each operation might be used 0 or multiple times
  so we brute force to try all pairs of operations

• we notice that shifting a cell to another cell means shifting the d1 diagonal and the d2 diagonal of the first cell to match the (d1 and d2) of the target cell
  

• each operation might be used to shift the d1 diagonal or the d2 diagonal so we also brute force 2 possibilities for each operation to try to shift on one of the diagonals each time

here is my code

For Div2D, I had the following approach

Theoretical Approach -

Consider that all (X, Y) is such that X>=0 and Y>=0 We have the following setup — To go right, we can take — upright and downright steps. Similarly for going upright, we can take right and upleft.

Note that we don't care for other dimensions, since X>=0 and Y>=0, and other dimensions(namely left, and downleft) take us away from the target.

Finally, we can add up the values — minPossibleRight = min(right, upright + downright) and minPossibleUpright = min(upright, upleft + right)

Implementation

We can rotate our coordinate axis such that right>=0 and upright >=0 For rotation, we can consider the following idea —

    // X, Y
    // up/down, right/left

    int right = y - x;
    int upright = x;
    int upleft = -y;
    vector<int> val({right, upright, upleft});
    // make sure the right and upright is +ve and upleft is negative
    // else we need to rotate the coordinate axis anti-clockwise
    while (!(right >= 0 && upright >= 0 && upleft <= 0)) {
        // right becomes upright
        // upright becomes upleft
        // upleft becomes right
        right = -val[1];
        upright = -val[2];
        upleft = -val[0];
        val = {right, upright, upleft};
        // Also keep rotating the values.
        int first = c[0];
        c.erase(c.begin());
        c.push_back(first);
    }

After rotating the coordinate axis, it becomes much more simpler.

int c1 = c[0], c2 = c[1], c3 = c[2], c4 = c[3], c5 = c[4], c6 = c[5];
    // for going right,
    // we have 2 choices,
    // go right, or go upright and downright
    c1 = min(c1, c2 + c6);
    // similar for upright
    // go upright, or go upleft and right
    c2 = min(c2, c1 + c3);

    int ans = c1 * upright + c2 * right;
    

For the problem E : "The proof can be done via induction", I didn't quite get how exactly that will work.

Assumption : For $$$n-1$$$ elements, let's say we have $$$m'$$$ minus signs. So, we will assume that $$$(n-1+m')\%3=1$$$. Now we can have the next element as a positive one or a negative one.

Say it's positive :

Then we have $$$n$$$ elements with $$$m'$$$ minuses, giving $$$(n+m'-1+1)\%3 = 2$$$ which isn't equal to 1.

Again, if it's negative :

Then we have $$$n$$$ elements with $$$m'+1$$$ minuses, giving $$$(n+m'+1+1-1)\%3 = (n-1+m'+2)\%3 = 0$$$, which again isn't equal to 1.

Obviously I am doing something wrong, but can someone point what?

Twice Fan caught in 4K :)