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, O((n+m)logn) per query

The following greedy assignment works: take the smallest team size k and repeat k times: assign the child with aik and smallest bik. It can be implemented in time O((n+m)logn) 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 (ai,bi), forming a set P, a team of size k can be mapped to a rectangle R(k)=[0,k]×[k,+]. We can reformulate our query as follows:

Is it possible to simultaneously assign ki points to a rectangle R(ki)? (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 [x1,x2]×[y1,y2] in time O(logn). 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 yi<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 c1,c2,,cz, the update will remove some (maybe 0) of consecutive corners starting before c2 and insert a single new corner.

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

O(nlogn) preprocessing, O(m2logn+mlog2n) query

We can find the appropriate corner cl such that there are at least k allowed points in a rectangle [0,k]×[0,cl] in time O(llogn) (we test sequentially c1,c2,, each time asking about points in some rectangle and summing them up).

Once we found cl, we know that the y coordinate of our new corner will be somewhere between y(cl1) and y(cl). We can binary search for the exact y in time O(log2n).

O(nlogn) preprocessing, O(mnlogn) amortized query

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

  • we run the first solution if m>n,
  • we run the second solution if mn.

O(nlogn) preprocessing, O(mlog2n) 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 O(mlog2n).

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 ki, 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)=|neighbors of A|(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 ki's are distinct and sorted (just for clarity).

We can propose a simple dynamic programming solution.

Let Di be the minimal c(A) such that ki is the greatest element of A. Then: Di=min{Dj+Z(j,i)ki:j<i}, where Z(j,i)=|children [a,b] s.t. a[kj+1,ki],bki|.

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

Another O(m2logn) solution

As computing Z(j,i) is asking about the number of points in some rectangle, we can implement this DP in O(m2logn).

Another O(mnlogn) amortized solution

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

O(mlogn) 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 Dk. Then, for any l>k, it's also more beneficial to take index i instead of j. Why? We have from our assumption:

Di+Z(i,k)Dj+Z(j,k), which is equivalent to:

DjDi|children [a,b] s.t. a[ki+1,kj],bkk|.

If we replace kk with klkk, the right side won't increase, so indeed Di+Z(i,l)Dj+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 O(logn).

The improved DP goes like this: when computing Dk, 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 Dk.

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 Dl", for some l.

There are O(m) set updates/accesses and each time we use O(logn) 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 O(logn). Let B=DjDi.

We need to find smallest y, such that there are at least B input points in [ki+1,kj]×[y,+]. 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 xx and last with xx in [A,mid].
  • the first point with xx and last with xx in [mid+1,B].

This allows us to binary search for ki and kj 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.