Editorial for COCI '06 Regional #2 Tetris


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.

Imagine that a piece is at the bottom of an empty field. The piece can then be encoded as a sequence of numbers if we write down the lowest occupied row for each column the piece occupies.

For example, piece number 5 in its four rotations gives following four sequences:

\{1, 1, 1\}, \{1, 2\}, \{2, 1, 2\} and \{2, 1\}.

We say that sequence A corresponds to sequence B if adding some constant to all elements of A gives sequence B.

For example, sequence \{2, 1, 2\} corresponds to \{5, 4, 5\}, but not to \{4, 5, 4\} or \{5, 4\}.

Observe that a piece can be inserted at a given position only if the sequence of heights at that position corresponds to the encoding of the piece. Therefore in order to obtain the solution we simply need to check all possible positions of all rotations for the given piece and field. Note that not all pieces have 4 possible rotations. Piece 2 is the same regardless of the rotation and pieces 1, 3 and 4 have only two possible rotations.


Comments

There are no comments at the moment.