Editorial for COCI '11 Contest 3 #3 Pogodak


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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 2,6,5,1 changed, and we can observe that they shifted circularly to the right, i.e. 2651 became 1265.

With the observations above, we can simulate all the moves, which would lead to an \mathcal O(RS) 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 S-1 horizontal moves give the same state of the cube as if we made only (S-1) \bmod 4 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 4, and it's not hard to see that each of these groups has the sum of 14, since one group contains two pairs of opposing faces.

The final complexity is now \mathcal O(R).


Comments

There are no comments at the moment.