Editorial for IOI '07 P5 - Pairs


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 N be the number of animals, M the size of the board and D the largest distance.

Solution for 1D board

To solve the 1D board, we first sort the coordinates and then perform a sweep-line algorithm. We keep track of two pointers: head and tail. When the head is pointing to an element with coordinate x, the tail is pointing to the first element with coordinate greater than or equal to x-D.

For each position of head we add \mathrm{head}-\mathrm{tail} to the total result. As we advance head to the next element, we can easily adjust tail to point to the required element.

The time complexity of this algorithm is \mathcal O(N \log N) for sorting, and \mathcal O(N) for sweeping.

Solution for 2D board

To solve the 2D version of the problem, we first consider the distance formula:

\displaystyle \operatorname{dist}(P, Q) = |P_x - Q_x| + |P_y - Q_y|

The formula above will resolve to one of the following four formulas:

\displaystyle \begin{align*}
\operatorname{dist}(P, Q) &= P_x - Q_x + P_y - Q_y = (P_x + P_y) - (Q_x + Q_y) \\
\operatorname{dist}(P, Q) &= P_x - Q_x - P_y + Q_y = (P_x - P_y) - (Q_x - Q_y) \\
\operatorname{dist}(P, Q) &= -P_x + Q_x + P_y - Q_y = (Q_x - Q_y) - (P_x - P_y) \\
\operatorname{dist}(P, Q) &= -P_x + Q_x - P_y + Q_y = (Q_x + Q_y) - (P_x + P_y)
\end{align*}

It is easy to see that the distance is always equal to the largest of these four values. As P_x + P_y and P_x - P_y represent the "diagonal coordinates" of point P we substitute:

P_{d_1} := P_x + P_y and P_{d_2} := P_x - P_y.

Now, we can rewrite the distance formula in terms of d1 and d2:

\displaystyle \operatorname{dist}(P, Q) = \max(P_{d_1} - Q_{d_1}, P_{d_2} - Q_{d_2}, Q_{d_2} - P_{d_2}, Q_{d_1} - P_{d_1}),

or shorter:

\displaystyle \operatorname{dist}(P, Q) = \max(|P_{d_1} - Q_{d_1}|, |P_{d_2} - Q_{d_2}|)

After substitution, we sort all the points by the first coordinate (d_1) increasingly and perform a sweep-line algorithm similar to the one-dimensional case. Since each point P between head and tail satisfies the inequality \mathrm{head}_{d_1} - P_{d_1} \le D, we only need to find out for how many of them the inequality |\mathrm{head}_{d_2} - P_{d_2}| \le D is satisfied as well. To calculate that value, we keep all points (their d_2 coordinates) between head and tail in either an interval tree or a binary indexed tree data structure.

The time complexity of the algorithm implemented with a binary indexed tree data structure is \mathcal O(N \log N) for sorting, and \mathcal O(N \log M) for sweeping, where M is the upper bound on the coordinates.

Solution for 3D board

Inspired by our 2D solution we start with the distance formula once again and obtain:

\displaystyle \begin{array}{r r@{\!\!}c@{\!\!}l}
& \operatorname{dist}(P, Q) &=& \max\left( |P_{f_1} - Q_{f_1}|, |P_{f_2} - Q_{f_2}|, |P_{f_3} - Q_{f_3}|, |P_{f_4} - Q_{f_4}| \right), \\
\text{where:} \\
& P_{f_1} &:=& P_x + P_y + P_z \\
& P_{f_2} &:=& P_x + P_y - P_z \\
& P_{f_3} &:=& P_x - P_y + P_z \\
& P_{f_4} &:=& P_x - P_y - P_z
\end{array}

Again, we perform a sweep-line algorithm on the f_1 coordinate while keeping all of the points between head and tail in a 3D binary indexed tree in order to count the number of points P satisfying inequalities |\mathrm{head}_{f_2} - P_{f_2}| \le D, |\mathrm{head}_{f_3} - P_{f_3}| \le D and |\mathrm{head}_{f_4} - P_{f_4}| \le D.

The time complexity of the algorithm is \mathcal O(N \log N) for sorting, and \mathcal O(N \log^3 M) for sweeping.

It is worth mentioning that we can use this solution to solve all types of boards. We just assign any constant value (1 for example) to each of the missing coordinates and implement a 3D binary indexed tree using either dynamic memory allocation, or using a one-dimensional array and manually mapping the 3-dimensional space to elements of the array.


Comments

There are no comments at the moment.