Editorial for COCI '11 Contest 3 #3 Pogodak
Submitting an official solution before solving the problem yourself is a bannable offence.
The first thing to do is decide how to store the cube. One possible way is to lay its faces to the plane, like in the figure below. This figure shows the cube in its starting position, i.e. in the upper left corner of the matrix.
Let's roll the cube one field to the right, and see what it looks like now.
We can see that this move only changed the blue row in the figure, and that this row shifted circularly to the left. Also note that one move to the left is the same as three moves to the right. This will be helpful later.
Let's see what happens if we roll the cube one field down. The figure shows what the cube looks like after moving it one field down from the starting position.
Only green faces marked changed, and we can observe that they shifted circularly to the right, i.e. became .
With the observations above, we can simulate all the moves, which would lead to an solution and would be too slow.
We can improve our solution by finding a faster way to calculate the sum of each row and the final state of the cube at the end of that row. After four horizontal moves we end up in exactly the same state, so horizontal moves give the same state of the cube as if we made only moves.
To find the sum of the whole row, we must also add the rest of the moves. These moves can be divided into groups of , and it's not hard to see that each of these groups has the sum of , since one group contains two pairs of opposing faces.
The final complexity is now .
Comments