Editorial for CCC '18 S2 - Sunflowers - DMOJ: Modern Online Judge

Editorial for CCC '18 S2 - Sunflowers

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.

Author: Kirito

Observe that a rotation of 90 degrees counterclockwise is the same as a 270 degree rotation clockwise, a rotation of 180 degrees counterclockwise is the same as a 180 degree rotation clockwise, and a rotation of 270 degrees counterclockwise is the same as a 90 degree rotation clockwise. These, along with a rotation of 0 degrees, are the only rotations you need to consider.

Thus, we can rotate the grid 0 degrees, 90 degrees, 180 degrees, and 270 degrees, clockwise, and print the valid grid.

The rotations can be thought of as an operation which maps the square at $(x,y)$ ~(x,y)~ to $(x',y')$ ~(x',y')~.

For a 0 degree rotation clockwise, we have $(x,y) \mapsto (x,y)$ ~(x,y) \mapsto (x,y)~.
For a 90 degree rotation clockwise, we have $(x,y) \mapsto (y,N-1-x)$ ~(x,y) \mapsto (y,N-1-x)~.
For a 180 degree rotation clockwise, we have $(x,y) \mapsto (N-1-x,N-1-y)$ ~(x,y) \mapsto (N-1-x,N-1-y)~.
For a 270 degree rotation clockwise, we have $(x,y) \mapsto (N-1-y,x)$ ~(x,y) \mapsto (N-1-y,x)~.

All of the above assume a 0-indexed grid.

Time Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

Comments

There are no comments at the moment.