Editorial for Mock CCC '19 Contest 1 S2 - Pusheen's Puzzle Present

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.

This problem is a homage to CCC 2018 S2, which tripped up competitors who had difficulty with rotating two-dimensional arrays.

For the first subtask, the answer is guaranteed to be 2.

For the second subtask, the answer is 3 if and only if the center element of the array is equal to 5. Otherwise, it is equal to 2.

For the third subtask, a brute force solution that attempted to rotate every valid subgrid would have worked.

To get full credit, the critical observation to make is that the corners of the subgrid are guaranteed to be different. As a result, it sufficed to compute the bounding box of all elements that were not where they should have been, and return the size of the bounding box.

Comments

-5

p1geon commented on Jan. 21, 2019, 11:45 p.m.

An easier way to implement a solution is to ceiling function the root of the number of cells that aren't in the right position (since there is the possibility of the middle cell of the sub-grid being in the right position if the size length of the sub-grid is odd).

This comment is hidden due to too much negative feedback. Show it anyway.

1

Zeyu commented on Jan. 24, 2019, 3:22 p.m.

Building on to your idea, we only need to count the number of displaced cells in the first row of the rotation then short-circuit out to save some time. This avoids both the issue of finding the square root and the possibility of the middle cell rotating on itself.

7

Relativity commented on Jan. 22, 2019, 2:42 p.m.

Isn't that harder?