Editorial for IOI '15 P3 - Teams
Submitting an official solution before solving the problem yourself is a bannable offence.
No preprocessing, per query
The following greedy assignment works: take the smallest team size and repeat times: assign the child with and smallest . It can be implemented in time 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 , forming a set , a team of size can be mapped to a rectangle . We can reformulate our query as follows:
Is it possible to simultaneously assign points to a rectangle ? (no point can be assigned to or more rectangles)
From now on, we assume that we preprocess the set , so that we can query the number of points in some rectangle in time . 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 . 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 .
We need to assign lowest points (smallest ) from outside the forbidden region and update the forbidden region. If we represent the region by corners , the update will remove some (maybe ) of consecutive corners starting before and insert a single new corner.
Therefore, we only need to find the right place for the new corner.
preprocessing, query
We can find the appropriate corner such that there are at least allowed points in a rectangle in time (we test sequentially , each time asking about points in some rectangle and summing them up).
Once we found , we know that the coordinate of our new corner will be somewhere between and . We can binary search for the exact in time .
preprocessing, amortized query
We can combine the two solutions above to obtain a better bound:
- we run the first solution if ,
- we run the second solution if .
preprocessing, 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 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 .
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 of team sizes , that the set of points that can be assigned to any team from (let's call those points neighbors) is smaller than the sum of numbers in .
Therefore, we want to construct such set , that the number is smallest possible. If the smallest turns out to be negative, then the answer is NO, otherwise it's YES.
Assume that 's are distinct and sorted (just for clarity).
We can propose a simple dynamic programming solution.
Let be the minimal such that is the greatest element of . Then: , where .
Optimal is thus equal to .
Another solution
As computing is asking about the number of points in some rectangle, we can implement this DP in .
Another amortized solution
This can be again combined with the brute force solution to speed it up.
solution
Let us assume, that we have three indices , such that it's more beneficial to take index than , while computing the minimum in the formula for . Then, for any , it's also more beneficial to take index instead of . Why? We have from our assumption:
, which is equivalent to:
.
If we replace with , the right side won't increase, so indeed .
Therefore, for any indices we can compute the exact moment of DP computation, when the index will be better than .
It can be done in time .
The improved DP goes like this: when computing , we maintain a set of those indices that might be useful according to our current knowledge. It also means that if indices and , are in the set right now, then is more beneficial. Hence, the last index from the set constitutes an optimal transition for .
Maintaining the set of indices involves a queue of events. For each two indices that happen to be neighbors in the set at some point in time, we push the event "remove from the set once you reach computation of ", for some .
There are set updates/accesses and each time we use time to compute a moment when is useless.
It remains to show, how to preprocess the input points to be able to find in time . Let .
We need to find smallest , such that there are at least input points in . This can be solved with a variant of a segment tree. However, in a node of the segment tree we store all the points (children) with in . The points inside a single node are sorted by increasing and each point stores the pointers to:
- the first point with and last with in .
- the first point with and last with in .
This allows us to binary search for and only in the root of the segment tree, and then just follow the pointers on a path to the leaf
Comments