Editorial for IOI '15 P3 - Teams


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.

No preprocessing, \mathcal O((n+m) \log n) per query

The following greedy assignment works: take the smallest team size k and repeat k times: assign the child with a_i \le k and smallest b_i \ge k. It can be implemented in time \mathcal O((n+m) \log n) by processing the teams and children in increasing order and maintaining a priority queue of children available for assignment.

Constructive approach

Now we enter the world of geometry. If we map the children to points (a_i, b_i), forming a set P, a team of size k can be mapped to a rectangle R(k) = [0, k] \times [k, +\infty]. We can reformulate our query as follows:

Is it possible to simultaneously assign k_i points to a rectangle R(k_i)? (no point can be assigned to 2 or more rectangles)

From now on, we assume that we preprocess the set P, so that we can query the number of points in some rectangle [x_1, x_2] \times [y_1, y_2] in time \mathcal O(\log n). This can be done for example using a persistent segment tree or some other method.

We again try to form teams in the order of increasing k. The idea is to maintain the set of "forbidden" points, that is, the region of plane containing the points which are either assigned to some previously processed rectangle, or not available because y_i < k.

We need to assign k lowest points (smallest y) from outside the forbidden region and update the forbidden region. If we represent the region by corners c_1, c_2, \dots, c_z, the update will remove some (maybe 0) of consecutive corners starting before c_2 and insert a single new corner.

Therefore, we only need to find the right place for the new corner.

\mathcal O(n \log n) preprocessing, \mathcal O(m^2 \log n + m \log^2 n) query

We can find the appropriate corner c_l such that there are at least k allowed points in a rectangle [0, k] \times [0, c_l] in time \mathcal O(l \log n) (we test sequentially c_1, c_2, \dots, each time asking about points in some rectangle and summing them up).

Once we found c_l, we know that the y coordinate of our new corner will be somewhere between y(c_{l-1}) and y(c_l). We can binary search for the exact y in time \mathcal O(\log^2 n).

\mathcal O(n \log n) preprocessing, \mathcal O(m \sqrt n \log n) amortized query

We can combine the two solutions above to obtain a better bound:

  • we run the first solution if m > \sqrt n,
  • we run the second solution if m \le \sqrt n.

\mathcal O(n \log n) preprocessing, \mathcal O(m \log^2 n) query

If we store the corners in some kind of binary search tree and decompose the forbidden area into rectangles (picture) so that each corner knows how (is responsible for) many points are there in its rectangle, then we can binary search for the y of new corner directly: each guess will involve a range sum in the corners structure and a single query to the points structure.

Thus, the running time is \mathcal O(m \log^2 n).

Non-constructive approach

The above solutions, although implicitly, construct the assignments. However, our question is binary and thus another approach is possible.

The Hall theorem says the following:

It's not possible to assign children to teams if there exists such subset A of team sizes k_i, that the set of points that can be assigned to any team from A (let's call those points neighbors) is smaller than the sum of numbers in A.

Therefore, we want to construct such set A, that the number c(A) = |\text{neighbors of }A|-(\text{sum of numbers in }A) is smallest possible. If the smallest c(A) turns out to be negative, then the answer is NO, otherwise it's YES.

Assume that k_i's are distinct and sorted (just for clarity).

We can propose a simple dynamic programming solution.

Let D_i be the minimal c(A) such that k_i is the greatest element of A. Then: D_i = \min\{D_j+Z(j, i)-k_i : j < i\}, where Z(j, i) = |\text{children }[a, b]\text{ s.t. }a \in [k_j+1, k_i], b \ge k_i|.

Optimal c(A) is thus equal to \min\{D_i\}.

Another \mathcal O(m^2 \log n) solution

As computing Z(j, i) is asking about the number of points in some rectangle, we can implement this DP in \mathcal O(m^2 \log n).

Another \mathcal O(m \sqrt n \log n) amortized solution

This can be again combined with the brute force solution to speed it up.

\mathcal O(m \log n) solution

Let us assume, that we have three indices i < j < k, such that it's more beneficial to take index i than j, while computing the minimum in the formula for D_k. Then, for any l > k, it's also more beneficial to take index i instead of j. Why? We have from our assumption:

D_i+Z(i, k) \le D_j+Z(j, k), which is equivalent to:

D_j-D_i \ge |\text{children }[a, b]\text{ s.t. }a \in [k_i+1, k_j], b \ge k_k|.

If we replace k_k with k_l \ge k_k, the right side won't increase, so indeed D_i+Z(i, l) \le D_j+Z(j, l).

Therefore, for any indices i < j we can compute the exact moment W(i, j) of DP computation, when the index i will be better than j.

It can be done in time \mathcal O(\log n).

The improved DP goes like this: when computing D_k, we maintain a set of those indices that might be useful according to our current knowledge. It also means that if indices i and j, i < j are in the set right now, then j is more beneficial. Hence, the last index from the set constitutes an optimal transition for D_k.

Maintaining the set of indices involves a queue of events. For each two indices i < j that happen to be neighbors in the set at some point in time, we push the event "remove j from the set once you reach computation of D_l", for some l.

There are \mathcal O(m) set updates/accesses and each time we use \mathcal O(\log n) time to compute a moment when j > i is useless.

It remains to show, how to preprocess the input points to be able to find W(i, j) in time \mathcal O(\log n). Let B = D_j-D_i.

We need to find smallest y, such that there are at least B input points in [k_i+1, k_j] \times [y, +\infty]. This can be solved with a variant of a segment tree. However, in a node [A, B] of the segment tree we store all the points (children) with y in [A, B]. The points inside a single node are sorted by increasing x and each point stores the pointers to:

  • the first point with x' \ge x and last with x' \le x in [A, mid].
  • the first point with x' \ge x and last with x' \le x in [mid+1, B].

This allows us to binary search for k_i and k_j only in the root of the segment tree, and then just follow the pointers on a path to the leaf


Comments

There are no comments at the moment.