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)$ $O (N^{2})$

Comments

There are no comments at the moment.