muxecoid's blog

By muxecoid, history, 3 years ago, In English

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.

  • Vote: I like it
  • -30
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C was mostly just noticing the idea of cycles from the samples.

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

    You made a new account just for writing this comment.........................

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

How did you approach solution of problem C? Can you explain more in details and steps? Thanks in advance.

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

    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)