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.
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
This comment is hidden due to too much negative feedback. Show it anyway.
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.
Isn't that harder?