Editorial for COCI '14 Contest 2 #5 Šuma

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.

Let us first solve a simpler version of this task where there are no two adjacent fields with trees of the same height and the same growth speed.

Let us examine two adjacent fields. The trees in those fields can be of equal height in at most one single moment. The moment when trees in two adjacent fields become of the same height will be called an event.

The number of events is smaller than 4N. For each event, we can use DFS (or BFS) to spread from the field where trees have become of the same height and counting trees in a component, being careful that for a certain moment we do not iterate over one field more than once.

This algorithm has a complexity of \mathcal O(N^2) because we will iterate over every field 4 times at most (once for each event which includes that field).

In the original task, a connected component of trees can grow together (if their initial heights and growth speed are equal). If we apply the previously described algorithm, we are left with a time complexity of \mathcal O(N^4). This complexity is achieved in the example where there exists a large component growing together. This approach was sufficient for 30\% of total points. The next idea that might come to one's mind is to compress the component of trees that grow together into one node and construct a graph where two nodes are connected if their corresponding components are adjacent in the initial matrix. This approach does not change the complexity because there can exist a component with many edges (order of magnitude N^2), and during DFS for every event, we will be iterating over all of its edges. This approach, given some additional (non-deterministic) optimization, was sufficient for 50\% of total points.

The solution for 100\% of total points is based on the previous solution, but we will not be using BFS or DFS but union-find structure for event processing. Union-find structure will remember the parents of each node and the root of each connected set remembers the size of its corresponding set.

First, we compress all connected trees that grow together into a single node, then calculate all events for every two adjacent nodes. The events are processed so that we connect the nodes in the union-find structure which in that moment become of equal height. During the event processing, we remember all the changes we made in the union-find structure in order to be able to restore the structure to the state before the event processing began. After the event processing, we restore the union-find structure to its initial state. This solution is of the complexity \mathcal O(N^2 \log N).

It is good to note that we don't need to use floating points numbers during calculations, sorting and comparison of events. Careless handling of data types with floating point resulted in wrong answers in some of the test cases.


There are no comments at the moment.