Editorial for COCI '16 Contest 2 #5 Zamjene
Submitting an official solution before solving the problem yourself is a bannable offence.
We will use the union-find data structure in solving this task.
Let's first describe the solution that isn't fast enough, but serves as a motivation for the actual solution.
What data must be remembered in each component? Each component corresponds to a set of positions. Let's denote the multiset of all values contained in the array on positions contained in component with , and the multiset of all values contained in the sorted array on positions contained in component with . When joining components and into a new component , we see that and .
It is crucial to notice that the array can be sorted if and only if holds for each component.
After this, we can notice that it is not necessary to remember the exact multisets of numbers, but only their hash values. If number is contained times in multiset , number times, …, times, then we define the hash value of set as:
When joining components, we simply add the hash values of the original components.
But, we still haven't mentioned how to answer query number 4. We actually want to know the number of pairs such that it holds:
(where now and denote the hash values)
Now we know how to answer the query by maintaining map where tells us how many nodes there are with the component's difference being exactly .
The time complexity of this solution is .
Comments