Editorial for COCI '14 Contest 5 #3 Traktor

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.

The goal of this task is to find the first moment when there are exactly K mushrooms in a row, column or line parallel to the diagonal.

The solution that was enough for 50\% represents the meadow in a matrix and, when adding a new mushroom, checks whether there are exactly K 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 x and y coordinate how many mushrooms there are with that x or y 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 x-y is constant, whereas for the second type the value of x+y is constant and there are 2 \times 10^5 - 1 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 K when a new mushroom is growing.

Total complexity is \mathcal O(N).


There are no comments at the moment.