A new pirate sailing ship is being built. The ship has N masts (poles) divided into unit sized segments - the height of a mast is equal to the number of its segments. Each mast is fitted with a number of sails and each sail exactly fits into one segment. Sails on one mast can be arbitrarily distributed among different segments, but each segment can be fitted with at most one sail.
Different configurations of sails generate different amounts of thrust when exposed to the wind. Sails in front of other sails at the same height get less wind and contribute less thrust. For each sail we define its inefficiency as the total number of sails that are behind this sail and at the same height. Note that "in front of" and "behind" relate to the orientation of the ship: in the figure below, "in front of" means to the left, and "behind" means to the right.
The total inefficiency of a configuration is the sum of the inefficiencies of all individual sails.
Example
/|
/ 0|
---+
/| /| /|
/ 2| / 1| / 0|
---+ ---+ ---+
/| | | /| /|
/ 2| | | / 1| / 0|
---+ + + ---+ ---+
| /| | | /|
| / 1| | | / 0|
+ ---+ + + ---+
/| | | /| /| |
/ 2| | | /1| /0| |
---+ + + --+ --+ |
Front | | | | | | Rear
----------------------------------------------
\ /
-----------------------------------------
This ship has 6 masts, of heights 3, 5, 4, 2, 4 and 3 from front (left side of image) to back. This distribution of sails gives a total inefficiency of 10. The individual inefficiency of each sail is written inside the sail.
Write a program that, given the height and the number of sails on each of the N masts, determines the smallest possible total inefficiency.
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:
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)).
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky