Tuesday, July 7, 2015

IOI 2007 Sails

Observation 1
The inefficiency of a level is determined by the number of sails at that level. The order of the masts does not matter, so we can rearrange them in ascending order of height.
Greedy strategy:
Place the sails from front (shortest) mast to rear (tallest) mast. For each new mast, place each sail on the level from the bottom that has least number so far. (As you go back and the masts increase in height, so new levels have count 0.)
Is this greedy strategy correct?
Given any optimal placement, we can show that we can transform step by step it into something that the greedy strategy will produce. (This is the standard way to prove a greedy algorithm is correct — "exchange" argument.)
Initially, all levels have 0. So, any placement of the first mast is consistent with the greedy suggestion.
Let us assume that upto the first K masts, we have perturbed the optimal solution to look like greedy. We now show that we can rearrange the (K+1)st mast to also be consistent with greedy without losing optimality.
Why is the (K+1)st mast not compatible with greedy?
There is (at least) one mast that is in the wrong place according to greedy, and the greedy slot is vacant.
              l1          o         r1

              l2          *         r2

   <------------------->     <----------------->
    1 to K is greedy     K+1  K+2 onwards is not greedy
Assume that l1 < l2, so we want to move the mast from * to o.
Suppose we move the mast from l2 to l1.
The new inefficiency is
old + (l1 - l2) + (r1 - r2)
This is less than or equal to old provided
(r1 - r2) ≤ (l2 - l1)
If this inequality holds, we are done.
What if this inequality does not hold?
r1 - r2 > l2 - l1 > 0
Therefore, r1 is at least 1. Since r1 - r2 > 0, there is at least one position where r1 has a sail and r2 does not. We move one sail from r1 to r2.
Now, the new cost is
old + (l1 - l2) + (r1 - r2) + ((l2 + r2) - (l1 + r1))
which is just the same as old.
Implementing greedy
Maintain a min-heap with pairs of the form (level, sails). When we reach a new mast, insert (l,0) for each newly added level.
This will take time O(number of sails × log (levels)), which gets 40% of the marks.
A more efficient implementation:
Store the levels sorted in descending order. Instead of keeping the absolute value of sails per level, keep the difference of each level with respect to the previous level in the sorted sequence.
e.g., if the levels are ordered as
     10  10   9   8   8   7   7   7   7   0   0
we store the differences
           10   0  -1  -1   0  -1   0   0   0  -7   0
When we process a new mast, we first append the new empty levels at the right of this list.
Now we want to add K sails to the levels with the lowest occupancy, namely the last K. This means we have to update the last K difference values.
In general, to update a segment [i,j], we only need to change the values at the left and right end — decrease the difference i - (i-1) by 1, or increase the entry at i by 1, and increase the difference at (j+1) - j by 1, or reduce the entry at j+1 by 1. If one endpoint of the segment to be updated is the right end, we only have to update the left endpoint.
For instance, if we add 6 sails from the right to the sequence above, we get
     10   0  -1  -1   0   0   0   0   0  -7   0
                              updated levels
This difference list corresponds to the updated level values
           10  10   9   8   8   8   8   8   8   1   1
after adding 1 to the last 6 entries.
What if we added only 4 entries, not 6? The new difference list would have been
     10   0  -1  -1   0  -1   0   1   0  -7   0
This corresponds to the updated level values
     10  10   9   8   8   7   7   8   8   1   1
which correctly captures the fact that the last 4 entries have been incremented, but this list is not in sorted order.
The problem is that the updated segment ended in the middle of a "level group" of 7's. It is not difficult to see that the only values that are not in sorted order are the elements at the right end of the level group that was only partially incremented.
When we update part of level group, we have to shift the elements from the right of the group to the left end. In this case, the final sorted sequence we should have is
     10  10   9   8   8   8   8   7   7   1   1
whose difference sequence is
     10   0  -1  -1   0   0   0  -1   0  -6   0
This corresponds to taking the level group of 7's in the original sequence and incrementing a segment [6,7] by 1, so we increase the value at position 6 and decrease the value at position 7+1 = 8, as described for a general [i,j] segment earlier.
                          level group
     10   0  -1  -1   0  -1   0   0   0  -7   0
                         <---->          <---->
                         update          update

     10   0  -1  -1   0   0   0  -1   0  -6   0
This gives us the overall update procedure for adding K sails on a mast:
  • Count the last K levels from the right. If this ends at the boundary of a level group, do a simple update for the interval [N-K+1,N].
  • Otherwise, update everything to the right of the incomplete level group as usual and separately update the left end of the level group.
How do we find the end point of a level group? A level group [A,B] consists of a contiguous interval of 0's, so we need to find the next non-zero value to the left and right of a given position K from the right. To get full credit, this has to be done using a segment tree. For each interval of the sequence of levels, store the position of first nonzero position from the right end of an interval and the first nonzero position from the left end of an internval. Using this, we can find the endpoints of the level group containing a given position K in time proportional to log(number of levels). This segment tree can also be updted in time proportional to log(number of levels).
Overall, the complexity is then O(number of masts × log (max levels)).

No comments:

Post a Comment