Editorial for COI '14 #3 Ogledala

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.

The first subtask can be solved so that for all $M$ ~M~ fields we calculate when they will be occupied and then easily answer queries. This can be simply done in time complexity $\mathcal O(N + M \log M + Q)$ ~\mathcal O(N + M \log M + Q)~ and space complexity $\mathcal O(M)$ ~\mathcal O(M)~.

The second subtask has too many washbasins to apply this approach. However, the number $B_Q$ ~B_Q~ is small so we can simulate the arrival of all the ladies up to lady $B_Q$ ~B_Q~. When there are $X$ ~X~ ladies occupying the washbasins, there are at most $X+1$ ~X+1~ segments of continuous unoccupied washbasins. These segments can be represented as ordered pairs $(\text{beginning}, \text{length})$ ~(\text{beginning}, \text{length})~ and keep them in a priority queue appropriately sorted so that the peak is always the leftmost longest segment. If that segment is represented by pair $(P, D)$ ~(P, D)~, the next lady coming will occupy washbasin $P+\frac{D-1}{2}$ ~P+\frac{D-1}{2}~ (integer division) and new segments $(P, \frac{D-1}{2})$ ~(P, \frac{D-1}{2})~ and $(P+\frac{D-1}{2}+1, \frac D 2)$ ~(P+\frac{D-1}{2}+1, \frac D 2)~ will form. For the described procedure, it takes $N+2B_Q$ ~N+2B_Q~ pushing into the priority queue and $B_Q$ ~B_Q~ popping so the time complexity of the algorithm is $\mathcal O(N + B_Q \log(N+B_Q))$ ~\mathcal O(N + B_Q \log(N+B_Q))~, and memory $\mathcal O(N+B_Q)$ ~\mathcal O(N+B_Q)~.

The third subtask requires a different approach because we can't simulate the arrivals of all ladies. Can we at least determine the size of the block which the $X^\text{th}$ ~X^\text{th}~ lady is coming to, for an arbitrary $X$ ~X~? Of course we can!

To begin with, we need to calculate how many blocks of which size will form during the arrival of all the ladies to the restroom. When we know that, it's easy to find the answer to our question because the ladies choose the blocks in descending order.

How to calculate how many blocks will form of which size? Let's observe the state of the washbasins after the arrival of the first $N$ ~N~ ladies:

.X.....X..

In the upper example, we have segments of empty washbasins of length $1$ ~1~, $5$ ~5~ and $2$ ~2~. Let's call these segments main segments. As the ladies arrive, they will be split into smaller and smaller segments. It is crucial to notice that the main segment of size $D$ ~D~ will split into at most $2 \log D$ ~2 \log D~ segments of different lengths. For example, for $D = 8$ ~D = 8~, we have $4$ ~4~ different lengths:

$\text{[math]}$

For each main segment, we can easily calculate all the different segment lengths that will appear when it's splitting and how many of them there are. When we calculate this for each main segment, we can construct an array of triplets (length, quantity, of which main segment) that describe all the segment lengths that will ever appear.

If we sort this array descending by the length of segment and from left to right by the main segment, we get even more than we asked for. Now we can also determine the length of segment $L$ ~L~ which the $X^\text{th}$ ~X^\text{th}~ lady will "hop into", but also the main segment which that segment is going to belong to.

We are left with determining where in the main segment the required segment is going to be located. From the large sorted array, we can find out the ordinal number of the required segment (by the time of occurrence) among all the segments of the same length from that main segment. Let's denote its ordinal number with $K$ ~K~. Now we can forget about all the other main segments and focus on the division of one main segment.

Let's imagine the first division of the main segment (the arrival of the first lady in it), and it splits into two parts. All segments of length $L$ ~L~ that will ever appear in the left part will be chosen before all segments of length $L$ ~L~ from the right part. Therefore, if there are at least $K$ ~K~ segments of length $L$ ~L~ in the left part, we discard the right part and repeat the same procedure. If there are less than $K$ ~K~, we denote that number with $P$ ~P~, discard the left part and look for the $(K-P)^\text{th}$ ~(K-P)^\text{th}~ segment of length $L$ ~L~ in the right part. We end the procedure when the segment we're splitting up becomes of length $L$ ~L~.

The counting of segments of length $L$ ~L~ that will form from a segment can be done in the complexity of $\mathcal O(\log M)$ ~\mathcal O(\log M)~ dividing it in the same way as the main segments before we inserted them in the large array. Since in each step we split the segment into two equal parts and discard one of them, the algorithm will complete in $\mathcal O(\log M)$ ~\mathcal O(\log M)~ so the total complexity of this solution is $\mathcal O(N \log M \log N + Q \log^2 M)$ .

Comments

There are no comments at the moment.