Codeforces Round #676 (Div. 2)

Had to perform better than last round to increase the rating again but started thinking in wrong direction for problem D, but solved it afterwards without editorials and easy to come up with solution. So I had to get this analysis out of the way before tonight’s Div.3 round. Contest was easy enough till D. I’m still not able to understand how I will approach problem E, it will be a blog in itself when I understand that.

Solved during contest

A. XORwice

• Fairly easy and interesting problem.
• In problems involving XOR I (and generally everyone) create answer bit by bit, because if you set MSB then you’re already better off then setting or unsetting bits on smaller positions.
• Here answer was straightforward a $\oplus$ b. As there are only four cases to consider and build answer bit by bit.

B. Putting Bricks on the wall

• Everyone had an easier solution to it, by checking only if flipping position to right and down of “S” and flipping positions to left and up of “F” works or one of their combination.
• Used the same idea but overkilled it by doing a full traversal after every adjustment. It had bugs so again took me 60 minutes to submit correctly.
• Second B. in a row where I spent more time than C and ended up loosing thinking time for D.

C. Palindromifier

• Intended solution was easy to come up. Took me 15 minutes.
• Once you get hang of what are the operations ‘L’ and ‘R’ you realize that you can always replicate whole string except first and last letter. So have to think of some letter to centre the palindrome around and some steps such that copying the second letter would be the last step.

Solved after contest

D. Hexagons

• Before contest tried some equations calculating contributions of different moves to get to the final position. After calculating that, I found out that you don’t need moves that go in opposite directions in one way so but still had 3 variables and 2 equations. Here went my 40 minutes.
• After contest saw the editorial, didn’t understand much of it, but problem was easy enough that you have only certain combinations of moves you can make for example if you want to reach $(x,y)$ first try going directly there by using the moves that allow you to do so - this will be our base answer. After that try going $(x,x)$ first and then make adjustments to combe to $(x,y)$ or you can go $(y,y)$ first and then come to $(x,y)$. It covers everything.
• These combinations were the three variables in two equations that I wasn’t able to solve.
• Code

E. Swedish Heroes

• Check back later on to see, I haven’t solved it yet.
• There are two type of solutions I’ve seen so far one is dynamic programming solution where states are

dp[prefix len][(len+negatives)%3][valid or invalid solution]

• I don’t understand it yet and other solution just uses the idea of setting negatives such that (n+m)%3==1 and no alternate pattern of + and - forms.