First 3 problems were kinda easy. Grime Zoo also felt easy at first. Quickly wrote a quick DP solution and only 40 minutes after the match I finished debugging the last bug. When problem is all about 01 you have many places for off by one mistakes. I must practice more.
My general idea for Grime Zoo was simple, at any specific point in string you have given number of question marks. Any fraction of them could be used as 1s. So you store the lowest number of comments obtainable for each number of 1s and advance from there.
And even version after additional debugging passed only the pretests.
C was mostly just noticing the idea of cycles from the samples.
You made a new account just for writing this comment.........................
How did you approach solution of problem C? Can you explain more in details and steps? Thanks in advance.
If they stand at their position $$$x_i = y_i$$$, dont move it
Otherwise let use $$$p[x_i] = y_i$$$ meaning that column of the rock at $$$x_i$$$ is $$$y_i$$$
Since you have the constraint $$$m < n$$$ you can move the rock without checking others
Since there are no pair of rocks checked by each other, you only need one operation each rock to move to its main diagonal
Consider a set of rocks $$$x_i, p[x_i], p[p[x_i]], ...$$$ you can move it to correct position and cost one operation each rock. But if it form a cycle, where $$$p[p[...p[x_i]..]] = x_i$$$, then you cost one more operation to move it out (so that other wont check it while moving to its correct order)