flaviu2001's blog

By flaviu2001, history, 7 months ago, In English

1421A — XORwice

Idea and solution: flaviu2001

Hint
Solution

1421B — Putting Bricks in the Wall

Idea: flaviu2001, solution: flaviu2001 and stefdasca

Hint
Solution

1421C — Palindromifier

Idea and solution: flaviu2001

Hint
Solution

1421D — Hexagons

Idea: flaviu2001, solution: flaviu2001 and koala_bear00

Hint
Solution

1421E — Swedish Heroes

Idea and solution: flaviu2001

Hint
Sneaky corner case
Solution
Proof for the pattern

You can also see the video solutions on stefdasca's Youtube channel

 
 
 
 
  • Vote: I like it
  • +158
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When will the induction end for the problem E?

»
7 months ago, # |
Rev. 6   Vote: I like it -21 Vote: I do not like it

Why is it getting WA on pretest 4?

Spoiler

UPD: submission

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Just submit it and wait for anwer...

  • »
    »
    7 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    I think the condition of else if(x<=0) is wrong. This condition is reached when x<=0 and x<y<0. So it should be c[4]*abs(y)+c[3]*(x-y). 95905133

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes,it was a bit tricky. Infact i was also thinking bfs kind of stuff. But later realized that it can be solved just with a greedy aproach.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think if we are asked to minimize c then BFS should be use!! Like there will be cases such as S and F has 0 in there adjacent cells but all other cell is having 1 then optimal c will be zero.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -73 Vote: I do not like it

    I tried the bfs approach as well but failed could you pls send me your submission link ? I am interested to see it. Mine is this — don't why it doesn't work tho ?


    #include <bits/stdc++.h> using namespace std; int n; int grid[205][205]; bool visited[205][205]; void dfs(int cx, int cy, int obstacle) { if(cx == n-1 && cy == n-1) return; visited[cy][cx] = true; int dx[] = {-1, 0, 0, 1}; int dy[] = {0, 1, -1, 0}; // explore neighbours in all 4 directions for(int i=0; i<4; ++i) { int nx = cx + dx[i]; int ny = cy + dy[i]; if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if(grid[ny][nx] == obstacle) { continue; } if(!visited[ny][nx]) { dfs(nx, ny, obstacle); } } } void solve() { char start_; cin >> start_; grid[0][0] = -1; for(int i=0; i<n; ++i) { for(int j=0; j<n; ++j){ visited[i][j] = false; if(i == 0 && j == 0) continue; if(i == n-1 && j == n-1) break; cin >> grid[i][j]; } } grid[n-1][n-1] = -1; char end_; cin >> end_; // to tell if we can approach the finish block from top or left side bool top = false; bool left = false; // choose digit 1 dfs(0, 0, 0); if(grid[n-2][n-1] == 1 && visited[n-2][n-1]) { left = true; } if(grid[n-1][n-2] == 1 && visited[n-1][n-2]) { top = true; } // Reset visited array for(int i=0; i<n; ++i) { for(int j=0; j<n; ++j){ visited[i][j] = false; } } // choose digit 0 dfs(0, 0, 1); if(grid[n-2][n-1] == 1 && visited[n-2][n-1]) { left = true; } if(grid[n-1][n-2] == 1 && visited[n-1][n-2]) { top = true; } // Print what blocks to invert if(left && top) { cout << 2 << "\n"; cout << n - 1 << " " << n << "\n"; cout << n << " " << n - 1 << "\n"; } else if(left) { cout << 1 << "\n"; cout << n - 1 << " " << n << "\n"; } else if(top) { cout << 1 << "\n"; cout << n << " " << n - 1 << "\n"; } else { cout << 0 << "\n"; } } int main(){ int t; cin >> t; while(t--){ cin >> n; solve(); } return 0; }
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried exactly the same stupid approach :(

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We can't avoid BFS to check if we can reach F right??

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      No, It can be done in O(1), just think of all the cases.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      The thing is you're actually not required to check that (you don't need to optimize for minimum "c")

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is just tricky we have to just take care of 4 nodes i.e is the two neighbouring nodes of S and two neighbouring nodes of F and then we just have to make a combination like this 1. all neighbours of S are 1 and all neighbours of F are 0 2. all neighbours of S are 0 and all neighbours of F are 1

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same..but i could'nt solve it btw

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Wow so fast editorial!

»
7 months ago, # |
  Vote: I like it +10 Vote: I do not like it

C's testcase contains a major hint.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    In constructive problems, the problem-setter always try to hidden the right construcion approach and even use some misleading approach in sample output, so I prefer to ignore the sample output in such problems.

    However, this time it did help lol

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    +1

»
7 months ago, # |
Rev. 4   Vote: I like it +16 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 .

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was a little depressed too, it took me 2 days thinking about task C to be able to solve it.

    A good tip is to just look at the editorial when you think the problem uses some algorithm that you don't know. Otherwise, the best thing to do is not to look at the editorial and fight against task.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Just use a^b as the answer.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Can anyone actually prove this?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Greedy approach, you just take xor of bigger number with both the numbers,bigger one vanishes and we get the answer which is basically xor of bigger and smaller one.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        If you're talking about proof of why XOR a^b works, then it's this way. Let's take i'th digit from both numbers (in binary). 1. If both of them are 1, then for x we put there 1 as well. This way we'll make that digit become 0 in our answer. 2. If one of them is 1, then no matter what we put there at x, that place in the answer will be 1. 3. If none of them is 1, then we need to put 0 there at x, that place in the answer will be 0. From these approaches, you can see that if digits in respective places are same, then that digit will be 0 in our answer, otherwise, it will be 1. And this is what XOR does indeed.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • Because the only one situation that can decrease the answer is that same bit of a and b is 1
        • So actually x=a&b
        • for example if a=1011 and b=1101
        • than x=a&b=1001
        • let's foucus on zeroes which means in that bit a is different with b
        • there are 4 situation which
        • NO.1 2 3 4
        • a= 00 01 10 11
        • b= 11 10 01 00
        • We found that for each case the equation (a xor x)+(b xor x)=11=a xor b for the zero bits of x
        • let think about 1 bits in x
        • wo know x=a&b ,so only if the same bit of a and b is 1 can makes the same bit of x equal 1, and obviously 1 xor 1 equals 0
        • So for the 1 bits in x, wo also get a equation
        • (a xor x)+(b xor x)=00=a xor b
        • By combining the two formulas, we can get the formula
        • (a xor x)+(b xor x)=a xor b
        • Have fun :>
»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://paste. ubuntu.com /p/Y 9yB9rvZ89/ What I wanted to say

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Edit: nvm

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    n is inital strings length not current

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The n in (L, n) is w.r.t the new string, which is of length n+1 (after the first (R n-1)).

»
7 months ago, # |
  Vote: I like it -16 Vote: I do not like it

y u no post code? maybe v vill learn new technique? or dat is bad??? u have code somewear obviously >:(

»
7 months ago, # |
  Vote: I like it +55 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it -20 Vote: I do not like it

    deleted because of downvoting

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Wonsei your solution for problem D looks so simple. Can you please explain your idea and solution in a short? I am not understanding the editorial.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      You can see here that to go from the first dot to the second dot, you can take two choices, c1 or c2+c6. so, we call n1(the cost to the right upper hexagon) minimum of those two values. You do that for all 6 directions. After that, you just go the shortest path to the destination from 0,0 using the new values.

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

»
7 months ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

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...

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just wanted to confirm something about B: the person cannot move from (1,1) to (2,2) right? Basically diagonally?

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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);
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So fast OoO

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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]?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes waters can move from gird[i][j] to 1 position left, or right, or top, or down, on the condition that that position should be in the grid.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In this case, 3 S10 101 01F He cannot reach to grid[n][n],then why we have to invert the squares grid[1][2] and grid[2][1]?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, that's what I had asked as a question during the contest, the reply was "there can be multiple answers"

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "adjacent by side"

    grid[i+1][j+1] is NOT adjacent by side to grid[i][j]

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No as grid[i][j] and grid[i+1][j+1] are not adjacent by a side. They don't have a common side.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In A) when they say the first bit, I would have said the first bit was the most left hand one. However, I also would have said that b's first bit is 0. Where am I wrong?

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I swear I got the answer for B here, https://codeforces.com/submissions/Lithosphere , does anyone know why I failed pretest 2?

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Fuck You Ringo!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I'm not sure why they are named that way in the code, but I recognize that it looks just like what I did. If you set up the linear equations as a matrix, delta is the determinant of the matrix and delta_a/delta_b are the matrix product of inv(A) * (x, y). When divided by delta (the determinant) they give the solutions to the linear equations (i.e. how many steps in each direction are needed).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried every possible case in 2nd question. Can anyone tell me where it went wrong ? https://codeforces.com/contest/1421/submission/95878916

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it -10 Vote: I do not like it

    YOUR LAST TESTCASE IS WRONG: IT IS WRITTEN =>


    else if (a[0][1] == '0' && a[1][0] == '1' && a[n - 1][n - 2] == '0' && a[n - 2][n - 1] == '0') { cout << "1\n" << 1 + 1 << " " << 0 + 1; }

    SHOULD BE:


    else if (a[0][1] == '0' && a[1][0] == '1' && a[n - 1][n - 2] == '0' && a[n - 2][n - 1] == '0') { cout << "1\n" << 0 + 1 << " " << 1 + 1; }

    Accepted 95920491

    your cout line is wrong broo

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank You :) got the mistake, silly one because I wrote such a brute force solution it became difficult for me to debug.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        its fine. I also wrote brute force. better for u to use small variables for a[0][1], a[1][0] etc. I used br,bl,tr,tl for bottom right, bottom left, top right, top left etc.

»
7 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Magical DP for E: 95899682

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Many red coders have used the dp for E. Can you please explain the dp solution? Thanks :-)

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Basically, the first dimension describes the number of minus signs placed modulo 3, and the other dimension is a boolean flag describing whether or not we "broke" the plus-minus-plus pattern or not. In the end, the number of minuses has to be equal to $$$2n+1$$$ modulo 3 and the flag must be on.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have read the editorial and I understand the corner case and the proof.

        But I still can not understand the way of dp transfer.

        I have seen this solution: https://codeforces.com/contest/1421/submission/95897364, it is more clear in state transfer.

        It seems that when we put '+' in an even position (or put '-' in an odd position), we can transfer the illegal state to the legal state.

        Why we can do this?

        If you have time, can you explain that? Thank you a lot!

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      the problem is equivalent to : assign + and — to every number , query the max sum,but "+-+-+-"is illegal and (the number of '-' + n) mod 3 =1. then the dp is obvious.

»
7 months ago, # |
Rev. 2   Vote: I like it -29 Vote: I do not like it

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;
    }

}

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the question clearly says only up to n-1,where n is the length of the string and u are using n.

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    You can brute force it and look at the set of sequences of signs you get

»
7 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

UPD: Found the bug!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just exact same procedure I had followed for problem c as editorial

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    find two or one direction to get to the desired hexagon. Next, try to reduce the cost of transition by adjacent hexagons (c [i] = min (c [i], c [i + 1] + c [i — 1]);). Then you find the number of steps and find the answer in long long. I found the distance just by brute force, but I'm sure that it can be better)).

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +34 Vote: I do not like it

More like IfElseForces.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think so. You can even solve A-D problem without any algorithm.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    An optimal set of inversions must either only change 0-cells to 1-cells and create a path consisting of 1-cells, or only change 1-cells to 0-cells and create a path consisting of 0-cells. So, you can run two instances of either 0-1 BFS or Dijkstra's algorithm, one to find the cost of making a path of 0-cells, and one to find the cost of making a path of 1-cells. Then the answer will be the minimum of these two values.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can take time to set problem ratings after end of round.

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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...

»
7 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    This is clearly true for the base cases when $$$n = 1, 2, 3$$$. Now, consider a general $$$n$$$. Suppose for a moment that you have already performed the sequence of operations $$$n - 2$$$ times, and are therefore left with just two remaining elements: $$$X_1$$$ and $$$X_2$$$. Note that $$$X_1$$$ is really just the sum (with possible -1s in front) of some elements of $$$a$$$. Let $$$n_1$$$ be the number of elements in that sum, and similarly define $$$n_2$$$. (Note: $$$n$$$ = $$$n_1$$$ + $$$n_2$$$). Let $$$m_1$$$ and $$$m_2$$$ be the number of elements with -1 in front in $$$X_1$$$ and $$$X_2$$$ respectively. By our induction hypothesis, we have that

    $$$ m_1 + n_1 \equiv 1 \text{ (mod 3)} $$$
    $$$ m_2 + n_2 \equiv 1 \text{ (mod 3)} $$$

    Let $$$m$$$ be the number of terms with -1 in front in our final sum after doing the operation to $$$X_1$$$ and $$$X_2$$$. Then $$$m = n_1 - m_1 + n_2 - m_2$$$.

    Finally:

    $$$n + m \equiv n_1 + n_2 + n_1 - m_1 + n_2 - m_2 \equiv 2n_1 + 2n_2 - m_1 - m_2 \equiv 2n_1 + 2n_2 - (1 - n_1) - (1 - n_2) \equiv 1 \text{ (mod 3)} $$$
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we solve problem D with using DFS??.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, I don't know why in test case 2, the answer c = 2. I thought it should be 0 because after Waters goes into cell (1,2) or (2,1) he has no any cells to go? Blame me if I'm wrong, please just tell me why?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I just got tilted with my low IQ on seeing solution of C. Lmao xD

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For the question 1421B — Putting Bricks in the Wall

ans for the test case

3 S10 101 01F can be 0 as well, We can alternatively target for

S10
10x
0xx

or

S01
01x
1xx 
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

While solving C, constraints in the resulting palindrome shouldn't have a size of 1e6 (10^6) and if we do this won't that nearly double the original length?

The length of the resulting palindrome must not exceed 10^6 And the size The only line contains the string S (3≤|s|≤10^5) of lowercase letters from the English alphabet.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not getting this expression.how left side equal to right side Anyone here will clear my doubt? (a ⊕ (a & b)) + (b ⊕ (a & b)) = a ⊕ b

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let $$$A = a \oplus (a $$$ & $$$b)$$$ and $$$B = b \oplus (a $$$ & $$$b)$$$

    $$$x + y = x \oplus y + 2 \cdot (x $$$ & $$$y)$$$ Where, $$$x $$$ & $$$y$$$ is the number of carries and should be shifted left once thus multiplying it by 2.

    Using this on LHS,
    $$$A \oplus B + 2 \cdot (A $$$ & $$$B)$$$
    $$$A \oplus B = a \oplus (a$$$ & $$$b) \oplus b \oplus (a $$$ & $$$b)$$$
    Since, xor is commutative. Simplifying, $$$A \oplus B$$$ = $$$a \oplus b$$$

    And $$$(A $$$ & $$$B)$$$ = 0, it can be proved by contradiction.

    Thus, $$$A + B = a \oplus b$$$

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 —

Click

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

Click