Editorial for COCI '09 Contest 5 #3 Kletva


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.

If we could normalize different locks to some form that would wield the same form for equal keys we could solve this task by comparing all normalized locks and counting the number of different forms. Fortunately, such normalization exists. First, let us examine how rotations come into play. Because the outline of the keyhole is composed of lines parallel to the edges of the lock, only rotations of 0, 90, 180 and 270 degrees are viable. All of these rotations can be simply accounted for. Rotation of 0 and 180 degrees is the same sequence read in the left-to-right or right-to-left order. Rotations of 90 and 270 degrees can be performed by subtraction and addition from the length/width of the lock. The normalization algorithm is as follows: first find the lowest point of the keyhole. This is our referent point. Now construct a new sequence from the lower edge sequence subtracting the referent point. This, paired with another sequence containing the widths of all keyhole segments (subtract the lower edge from the upper edge) gives us a perfect normal form for this task.


Comments

There are no comments at the moment.