Editorial for COCI '14 Contest 5 #3 Traktor
Submitting an official solution before solving the problem yourself is a bannable offence.
The goal of this task is to find the first moment when there are exactly mushrooms in a row, column or line parallel to the diagonal.
The solution that was enough for represents the meadow in a matrix and, when adding a new mushroom, checks whether there are exactly
mushrooms in a row, column or on the lines where the new mushroom is located.
The solution that was enough for all points remembers for each and
coordinate how many mushrooms there are with that
or
coordinate. Let's observe the lines parallel to the diagonals of the meadow. There are two types of such lines. For the first type, the value of
is constant, whereas for the second type the value of
is constant and there are
such lines for each diagonal. For each such line, we can remember how many mushrooms are located on it.
Now we are only left with finding the first moment when some of the counters get to when a new mushroom is growing.
Total complexity is .
Comments