Codeforces Round #804 (Div. 2) Editorial

A — The Third Three Number Problem

Authors: antontrygubO_o, Gheal

B — Almost Ternary Matrix

Author: Gheal

C — The Third Problem

Author: Gheal

D — Almost Triple Deletions

Author: Gheal

E — Three Days Grace

Author: tibinyte

If there is anything wrong or unclear in this editorial, feel free to ping me or any of the other setters in the comments.

• 40 hours ago, # ^ |

• 31 hour(s) ago, # ^ | I know, right?! Could someone please explain the implementation? I didn't get what the solution shared in the editorial is saying exactly...

  • 31 hour(s) ago, # ^ | Start by solving a 2x2 matrix. For the 2x4 matrix, you can flip the 2x2 matrix to the right. You can see that if you just flip the 2x2 matrix to the right every time, you can solve matrices of sizes 2x6, 2x8, and so on. The same can be applied with nx2 matrices (4x2, 6x2, 8x2 and so on), except this time you flip the 2x2 matrix down.

  • 30 hours ago, # ^ | ← Rev. 3 →   +22 a much easier implementation would be to notice that a pattern in the binary matrices like this and we can obtain any row x column by increasing or decreasing the rows or columns accroding to this pattern. for eg : a 8 x 10 will look like this so for implementing just make a 50 x 50 matrix (which is not much of a trouble if you use copy and paste) and output for given row and column my code : code

    • 29 hours ago, # ^ | amazing

    • 27 hours ago, # ^ | bro is a true gamer

    • 17 hours ago, # ^ | OMG, I can't believe I didn't try this uff. I was unnecessarily trying to automate the process! Thank you very much. I realize why I didn't get this

• 25 hours ago, # ^ |

  • 23 hours ago, # ^ | Well, it didn't have any particular way to solve it, you just had to guess the structure of the matrix and I just found that pretty annoying... idk about you.

• 43 hours ago, # ^ |

• 43 hours ago, # ^ | Sorry for this, it should be fixed now.

• 43 hours ago, # ^ | Most testers said that the current C would be better as a div2 D. We did try to insert a new C between the current B and C, however this wasn't approved in the end.

  • 43 hours ago, # ^ | Ohh..that was the case...but overall contest was pretty good.

  • 42 hours ago, # ^ | ← Rev. 2 →   0 Though i couldn't do it, but C was really an interesting problem.

• 42 hours ago, # ^ | I went on the wrong track, and even tried to implement offline fenwick tree queries lol. I thought it had something to do with the number of elements greater than a number k between the first appearance of a number from 0 to k and the last appearance of a number in the range 0 to k. The solution was much simpler lol. I didn't have time to finish this solution so idk if it works.

• 42 hours ago, # ^ | D was too hard too, contests should be easier so they don't make me feel bad :((( Also they should make me grandmaster

  • 42 hours ago, # ^ | Hahaha

  • 6 hours ago, # ^ | Bro, You were MASTER once . Damn

• 42 hours ago, # ^ | Here's my submission. 162794168

• 42 hours ago, # ^ | Thank you.

• 42 hours ago, # ^ | That's the most cursed thing I have ever written, accidentally or not. Has been fixed.

• 42 hours ago, # ^ | Well, I guess that was the whole point of B, figuring out the solution was easier than standard div2B's, but the implementation was the tricky part.

  • 42 hours ago, # ^ | I mean, implementation was harder than standard B's, but not that hard. Also, the simplicity of the idea kinda makes up for it in my opinion.

  • 42 hours ago, # ^ | My implementation is pretty short, I genuinely thought the idea was the hard part.

    • 41 hour(s) ago, # ^ | I guess I'm getting smarter B-)

• 42 hours ago, # ^ | That is true, thank you for noticing. It has been fixed now.

• 42 hours ago, # ^ | Please ban these kind of users

  • 42 hours ago, # ^ |

• 42 hours ago, # ^ | I would request Mike and his team to kindly look into this since it made the contest unfair for many! ;(

• 42 hours ago, # ^ | ← Rev. 2 →   +16 Like if you cover the boarder in the picture, you have a checkerboard that looks like this: XX..XX XX..XX ..XX.. ..XX.. XX..XX XX..XX I think that's what they meant. Hope that helps.

  • 42 hours ago, # ^ | Thank you, it wasn't clear to me neither.

  • 42 hours ago, # ^ | Are you going to be posting a screencast of this contest?

    • 38 hours ago, # ^ | Welllllll.... I recorded an incredibly entertaining screencast and was going to post it. But for some reason my mic was set up incorrectly so there was no sound, despite my recording software visually showing me that there was sound. So I feel kind of cheated out of it, but unfortunately on screencast this time, especially because this one would have been great. :(

      • 19 hours ago, # ^ | I'm very sorry to hear this... Right when i saw you in the standings I was hyped to see a screencast. However, did you like the problems ?

  • 42 hours ago, # ^ | ← Rev. 5 →   +4 my construction was that these 2 2X2 blocks have to be used alternately. Sorry for the bad formatting.

    • 37 hours ago, # ^ | That's the way I thought too. I am still wondering how jiangly's brain works after seeing this solution: for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { std::cout << ((i ^ j ^ (i >> 1) ^ (j >> 1)) & 1) << " \n"[j == m - 1]; } } what on earth is this

      • 36 hours ago, # ^ | It's just a more concise way of formatting writing the checkerboard thing. Essentially, it's just the parity of (i = 1 mod 2) + (j = 1 mod 2) + (i = 1 or 3 mod 4) + (j = 1 or 3 mod 4), which is exactly what you want if you look at the checkerboard. It would be more clear if I could post a whiteboard drawing, but in any case, I think just chewing on this type of parity stuff will make it easier to internalize/visualize/quickly convert from tilings to math.

      • 32 hours ago, # ^ | lol what a orz guy.

• 42 hours ago, # ^ | No one is. The contest is like that.

  • 42 hours ago, # ^ | People are attempting hacks, i can see that in the hacks menu.

    • 42 hours ago, # ^ | I am sorry. I made a mistake. I can't hack neither.

• 42 hours ago, # ^ | The contest has ended, and outside of contest only higher rated players can hack (https://codeforces.com/blog/entry/68204)

• 42 hours ago, # ^ | ← Rev. 2 →   +1 j==m can be transformed into int(j==m); " \n" is a string constant (char array). Then it's just the same as accessing an array.

  • 42 hours ago, # ^ | cool way to code clean!

    • 42 hours ago, # ^ | Interesting, because I felt that such kind of coding style is the complete opposite of clean coding (unless, if you think clean code == shortest possible code).

    • 29 hours ago, # ^ | As far as I know, clean code means the one which is easily understandable to others. Condensing your code so much that no one else understands it, I don't understand the logic behind it.

  • 30 hours ago, # ^ | so when we will get only " " and when we will get " \n" how it is decided ??...

    • 29 hours ago, # ^ | when j == m, the output is true which is taken as 1. and when it is less that m, the output is false, i.e 0;

    • 29 hours ago, # ^ | Let us assume s = " \n", so s[0] = ' ' and s[1] = '\n'. Here, in the for loop, he wrote " \n"[j == m], so if j == m, j == m will be 1 and " \n"[1] = '\n' will be printed, otherwise " \n"[0] = ' ' will be printed.

• 41 hour(s) ago, # ^ | they probably could've used the time it took them to insert all these lines to actually solve the problem lol, I really don't understand those people... good job for calling them out

• 40 hours ago, # ^ | ← Rev. 2 →   +10 bored_kid if you are bored, go and learn new things. Rather than copying and defaming your country by just mentioning India, instead mention your real name and institution.

cout<<((i%4<=1)!=(j%4<=1))<<" \n"[j==m]; 

• 42 hours ago, # ^ | See this comment.

• 35 hours ago, # ^ | if j==m, it means j is the last element of the row, so j==m is 1 and " \n"[1] is actually '\n'. Otherwise, j==m is 0 and " \n"[0] is a whitespace. This small trick is used to print whitespaces between elements, and a newline after a row of elements.

• 42 hours ago, # ^ | ← Rev. 3 →   0 I actually had generator with large divisors, but I think i should have considered a bigger upperbound on the number of divisors. I think it was set to be at most 50 divisors less than the maximum possible number of divisors...

• 42 hours ago, # ^ | Consider the lowest bit of the three numbers, and check all cases.

  • 42 hours ago, # ^ | Any formal proof?

    • 42 hours ago, # ^ | I included a formal proof in the solution for A.

      • 41 hour(s) ago, # ^ | ← Rev. 2 →   0 How we can conclude that a ⊕ b and a + b have the same parity (odd or even number of 1-bits) from the equation a + b = a ⊕ b + 2⋅(a&b)? And also how same parity ensures that (a ⊕ b)+(b ⊕ c)+(a ⊕ c) will be even?

        • 41 hour(s) ago, # ^ | is always even, so it would make sense that and have the same parity. The parity of is the same as the parity of , which is always even.

          • 41 hour(s) ago, # ^ | ← Rev. 2 →   0 You are considering parity as the property of an integer of whether it is even or odd or it means parity of a number whether it contains an odd or even number of 1-bits?

            • 41 hour(s) ago, # ^ | Parity as in whether an integer is even or odd.

• 42 hours ago, # ^ | for odd numbers it is impossible to have a b c to satisfy the condition and for even number one possible pair is 0 n/2 n/2 so the sum is always even.hope it helps

• 42 hours ago, # ^ | ← Rev. 3 →   0 last bit of all 3 elements 0 0 0 now xor them and add last bit will always be zero. :)

• 41 hour(s) ago, # ^ | ← Rev. 3 →   +1 PROOF FOR A

  • 30 hours ago, # ^ | ← Rev. 2 →   0 Thank you for your nice explanation.

• 17 hours ago, # ^ | ← Rev. 2 →   0 consider the case where n is odd which has last bit as 1, so we need last bit as 1. but if we check all cases where numbers having last bit like 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 All cases give last bit as 0 if we try out it in given equation.

42 hours ago, # | ← Rev. 2 →   +48 Here is a way to approach problem B: (let me use "color" instead of "value") We have to find a coloring, such that each cell has exactly 2 neighbours of a different color. IMHO, 2 neighbours of a different color are quite annoying. I've tried to avoid it, reformulating like this: each cell has 4 neighbours, so let's find a coloring, such that each cell has 4-2=2 neighbours of the same color. But it fails on the borders. However, we can avoid "different color" part! Let's xor each cell with corresponding cell in the chess coloring. Now we have to find a coloring, such that each cell has exactly 2 neighbours of the same color. From that side, the solution is easier: split the matrix into 2x2 squares and color neighbouring ones differently. Here's the solution for 8x6 matrix (I've assumed black is 0, white is 1): Interesting facts: The answer is ((i/2 + j/2) % 2) ^ ((i + j) % 2) The answer is the same as in the editorial

• 41 hour(s) ago, # ^ | can't understand from the part "however we can avoid ..." can you please explain a bit more how are you xoring with the chess board and how this approach comes into your mind

  • 40 hours ago, # ^ | Suppose you have a matrix a, such that every cell (i, j) have exactly two neighbours of the same value. Then you put the matrix on a chess board and flip those values that lay on white cells. Effectively, you assume that black is 0, white is 1 and perform xor of corresponding cells. Consider some black cell (the logic with white cells is pretty much the same). It has only white neighbours. That means it doesn't change value, but all the neighbours do. In result, the former cell has now exactly two neighbours with different value. Can't say anything about how to come up with the idea...

• 42 hours ago, # ^ | I made it using vanilla HTML and JavaScript. Code

• 41 hour(s) ago, # ^ | Same for me, I am surprised by the big number of solves.

  • 41 hour(s) ago, # ^ | it's due to cheating B is a good problem and its difficult to observe the pattern

• 40 hours ago, # ^ | Lol I spent more than 30 minutes coming up with a solution right now. Constructive problems are wild, eh? I saw someone's comment saying "B was easier than regular div2 B" ☠️

• 41 hour(s) ago, # ^ | Man, I never would've thought of this dp idea. I wasn't able to solve D during the contest but it seems like you can solve it kinda greedily as well. I created the can_delete matrix to store if some subarray can be deleted and then I just found out the max length possible greedily. Can't prove it tho. my submission

  • 41 hour(s) ago, # ^ | Hmm, that's a strange solution... However you were very close to the solution, most difficult thing imo was checking weather subarray can be deleted...

    • 39 hours ago, # ^ | I figured out a solution during the contest that if we create some matrix that stores if a subarray can be deleted or not we can easily build a dp table such that dp[i] denotes the maximum number of the same elements as a[i] of which the last element is at the ith position. Just couldn't think of a way to make the matrix (matrix — isposs[i][j] = 1/0 depending on whether we could delete the subarray i...j or not respectively). The observation (n/2 must be even and max(freq[1..n]) <= n/2) was not intuitive. Link to my solution

  • 38 hours ago, # ^ | Try something like 1 2 1 2 1 2 1 2 3 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3

• 39 hours ago, # ^ | ← Rev. 2 →   +8 Same here. I thought checking for each distinct value is obvious thing as it also matched the complexity O(n^2). I did try to think of some dp after that. Something like, dp[i][j] = maximum equal value j we can get from first i elements; then dp[i][j] = max( dp[i-1][j] + 1 ,if a[i]==j; dp[i-1][j] - 1, if a[i]!=j; , ....more transitions here) but couldn't figure out the whole thing.

• 35 hours ago, # ^ | First all, it is easy to know 0 and 1 must have the same position in 'a' as 'b'. It is easy to find examples that 'a' is not similar with 'b' if the statement is not true. Next, consider the interval by the position of 0 and 1. If 2 is in this interval in 'b', then 2 can be any position in the interval in 'a'. To prove this, there are several cases to consider. But it is easy to understand the reason if you use a sample to learn. And if 2 is out of the interval in 'b', then 2 must be in the same position in 'a'. After 2 is considered, continue to consider the interval by the position of 0, 1, and 2. And consider whether 3 is in the interval or is out of the interval. And so on until to n-1. I don't know how this formula is gotten: "(r−l+1)−k", but you can always calculate how many position are available in one interval and multiply the number to the answer. One sample submit: https://codeforces.com/contest/1699/submission/162835519

  • 26 hours ago, # ^ | yeah thanks I understand now, for the formula for ex if pos of 1 is 0 and pos of 0 is 3 then the no of positions for 2 are =3-0+1-(num of pos taken by 0 and 1) which is 2 itself so 3-0+1-2=2 hence the formula (r-l+1)-k hope you can understand now

  • 22 hours ago, # ^ | I know number 0 . But why is the position of number 1 the same as that of number 1 of array a? Please indicate,thanks.

  • 3 hours ago, # ^ | houxiang thanks for the approach, got it now !

• 41 hour(s) ago, # ^ | Possibly, but it's definitely not necessary. A simple matrix traversal is enough for this problem.

• 41 hour(s) ago, # ^ | what exactly do you mean by DFS traversal? what exactly would you do for each node?

  • 41 hour(s) ago, # ^ | for every node (i,j) goto (i-1,j),(i+1,j),(i,j+1)and(i,j-1) then make exactly two of them to opposite color of (i,j).

    • 41 hour(s) ago, # ^ | how do you decide which ones to flip then?

• 41 hour(s) ago, # ^ | For gcd, the intended solution is .

  • 41 hour(s) ago, # ^ | for mod is the logic correct?

    • 41 hour(s) ago, # ^ | Yes. If I recall correctly, , and needed to be distinct, which I didn't mention in the blog. My solution was , , .

      • 41 hour(s) ago, # ^ | thanks got it btw nice editorial

        • 41 hour(s) ago, # ^ | thanks, glad you liked it

      • 41 hour(s) ago, # ^ | Can you please reply to my query as well. How is this solution 162759681 working exactly and what is the intuition behind this implementation

• 41 hour(s) ago, # ^ | Base row1..... .... 1001 Base row2... . ... 0110 Again repeated row3 0110 Row4.. .......... 1001 Like this formats its repeated

• 41 hour(s) ago, # ^ | ← Rev. 2 →   0 Spoiler

  • 39 hours ago, # ^ | The statement in solution C says "For every interval [l,r] such that (l≤p[0]<p[1]≤r), MEX([bl,…,br]) must be at least 2. For every other interval, MEX([bl,…,br]) cannot exceed 2". The interval L = 0, R = 2 you mentioned satisfies the condition (l≤p[0]<p[1]≤r). But the question is about intervals that don't satisfy this condition.

• 27 hours ago, # ^ | Yeah I had the same Confusion

• 40 hours ago, # ^ | And I really enjoyed you not participating!

• 40 hours ago, # ^ | And I really enjoyed the bried time before this comment where you hadn't assumed I asked! cadmiumky

• 40 hours ago, # ^ | ← Rev. 2 →   +9 I found B hardest among A-D, seems skill issue on my part.

  • 39 hours ago, # ^ | Maybe we're just good at different types of tasks, I can't say that I'm really into DP problems ;)

  • 24 hours ago, # ^ | Can you Explain the Solution of Problem D a bit more?So hard for me![cry][cry]~

• 40 hours ago, # ^ | Can U explain B . I found it to be very tricky and could'nt solve it!

  • 39 hours ago, # ^ | Just look at the pattern in the first sample. Split your n * m board into 2 * 2 squares, and paint these squares like chessboard, but instead of black and white use [[0, 1], [1, 0]] and [[1, 0], [0, 1]]. You can extend this pattern to infinite boards.

    • 38 hours ago, # ^ | wow thanks for the help dude

      • 31 hour(s) ago, # ^ | btw, those squares have to be alternating.

• 40 hours ago, # ^ | i see your comment in every blogs.. you are so active..

  • 40 hours ago, # ^ | Is it bad?

    • 31 hour(s) ago, # ^ | i guess no .. if you have enough time... just it was my observation..

• 40 hours ago, # ^ | OMG, you're awesome!

  • 40 hours ago, # ^ | You too king ❤️

• 39 hours ago, # ^ | ← Rev. 2 →   0 For a number and all ways of writing it as product of some values that are , take the one that has the lowest maximum value. It is easy to see only values that can affect this dp must be divisors of so we only need to consider those.

  • 38 hours ago, # ^ | thanks, that helped

• 30 hours ago, # ^ | This test was added automatically because of a successful hack with it, I'm not sure if the submissions will be rejudged though.

• 31 hour(s) ago, # ^ | lol, I just go in order.

• 24 hours ago, # ^ | Hey harshitbhatt!Can you Explain the Solution of Problem D a bit more?Thank you!

if (n % 2) {
    cout << "-1\n";
    return;
}

cout << "0 0 " << n/2 << "\n";

• 29 hours ago, # ^ | good at problem solving fazik

• 27 hours ago, # ^ | My bad. In romanian, the transliterations of subsequence and subarray have swapped meanings. Thank you for spotting this mistake, it has been corrected.

• 24 hours ago, # ^ | Hey,naman1601! Can you Explain the Solution of Problem D a bit more?Thank you!

• 25 hours ago, # ^ | Usage of maps for finding at what index would divisor x be in number i.

• 17 hours ago, # ^ | I observed this 2x2 pattern from the given test-cases: If you place this pattern of [[1, 0], [0, 1]] in the top left 2x2 sub-matrix, then you can alternatively place this pattern and its mirror — [[0, 1], [1, 0]], in the rest of the rows and columns. The design will spread such that all numbers will be guaranteed to have 2 different neighbors.

• 5 hours ago, # ^ | ← Rev. 4 →   0 We can think of this in terms of individual bits. 0+0=0⊕0+2*(0&0)=0 0+1=0⊕1+2*(0&1)=1 1+0=1⊕0+2*(1&0)=1 1+1=1⊕1+2*(1&1)=2 Just testing out all of these possibilities, it can easily be seen that the equation holds true. A more intuitive understanding of the formula would be: the 2*AND operator is there because the XOR operator effectively cancels out a 1 and a 1. Therefore, to account for the case of double 1's, we just need a 2*AND operator. Otherwise if at least a or b is zero, then a+b=a⊕b

  • 5 hours ago, # ^ | Thanks!

• 3 hours ago, # ^ | a ⊕ b is the sum of individual bits and 2⋅(a&b) is the carry.