Editorial for COCI '16 Contest 2 #5 Zamjene


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.

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 p on positions contained in component K with P_K, and the multiset of all values contained in the sorted array q on positions contained in component K with Q_K. When joining components A and B into a new component C, we see that P_C = P_A \cup P_B and Q_C = Q_A \cup Q_B.

It is crucial to notice that the array can be sorted if and only if P_K = Q_K 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 1 is contained c_1 times in multiset S, number 2 c_2 times, …, n c_n times, then we define the hash value of set S as:

\displaystyle h(S) = c_1 H + c_2 H^2 + \dots + c_{n-1} H^{n-1}

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:

P_A+P_B = Q_A+Q_B (where now P and Q denote the hash values) \iff P_A-Q_A = -(P_B-Q_B)

Now we know how to answer the query by maintaining map M where M[d] tells us how many nodes there are with the component's difference P-Q being exactly d.

The time complexity of this solution is \mathcal O(Q \log N).


Comments

There are no comments at the moment.