The accordion warehouse
A warehouse rents halls, and the capacity of a hall is always a power of two: 1, 2, 4, 8, … boxes. At first the warehouse is empty and occupies a hall for one box. Boxes are brought in and taken away one at a time, and the moving rules are strict.
- If a box has to be put in and the hall is full, the warehouse rents a hall twice as big and carries all the boxes there. Then it puts the new one in.
- If, after a box has been taken away, the boxes occupy a small share of the hall, the warehouse moves to a hall half the size and also carries all the boxes. There is no hall smaller than one box.
The director and the accountant argue about when the share counts as small. The director says: move out as soon as half the hall or less is occupied. The accountant: only when a quarter or less is occupied. From the warehouse log, count how many boxes the movers will carry over all the moves under the director's rule and under the accountant's rule.
Input
The first line holds the number of log entries q (1 ≤ q ≤ 200,000). Each of the following lines holds a sign and a number: + k, k boxes were brought in, - k, k boxes were taken away (1 ≤ k ≤ 10⁹). Only what is in the warehouse is taken away. The boxes within one entry are brought in and taken away one at a time, and the rules are checked after each.
Output
Two numbers separated by a space: how many boxes are carried under the director's rule (half) and under the accountant's rule (a quarter). The answers fit in a 64-bit integer.
Examples
Example 1
4 + 5 - 3 + 6 - 7
26 16
Example 2
7 + 8 + 1 - 1 + 1 - 1 + 1 - 1
55 15
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
This is a dynamic array: a hall is a block of memory, boxes are elements, a move is copying. The director's rule is the very shrinking at a half that the seesaw in the article rocks. But first, speed: a single entry “+ 10⁹” is a billion boxes. They cannot be gone through one at a time.
2Hint 2
Between moves the boxes are simply added or subtracted. How many boxes can be brought in before the next move? And taken away?
3The idea
Move not box by box but from move to move. When k boxes are brought in, cap − size fit before a move: if k is no more than that, just add. Otherwise fill the hall to the brim, move (carry cap boxes), double the hall and continue with the rest. When boxes are taken away, the hall shrinks when the boxes number cap / t (t = 2 for the director, 4 for the accountant). If more than that remain after taking k away, there is no move. Otherwise take away exactly down to the threshold, carry the remaining boxes, halve the hall and continue. Each move changes the hall by a factor of two, so one entry takes at most a couple of hundred steps.
4Walkthrough
One function simulate(events, t), called twice. Edge cases: a hall for one box never shrinks; for the accountant a hall for two boxes shrinks only when there are zero boxes (a quarter of two is less than one box). The first sample under the director's rule: five boxes, with moves at 1, 2 and 4 boxes, 7 carried. The very first box taken away leaves 4 of 8, exactly half: a move into a hall for 4, 4 carried. The third leaves 2 of 4, half again: into a hall for 2, 2 more. Count the rest yourself and check against the answer 26.
The second sample is a seesaw: a full hall for 8 boxes, and a box is now brought in, now taken away. For the director each such pair is two moves of 8 boxes, for the accountant after the first expansion there are no moves at all. The fourth test is the same with 2²⁹ boxes: under the director's rule the movers carry more than 10¹⁴ boxes, under the accountant's about a billion. That is the reason dynamic arrays shrink at a quarter and not at a half.
4+Solution
5Complexity
For an entry “+ k”, O(1 + the number of doublings); for “− k”, O(1 + the number of halvings). The hall cannot double more than 60 times in a row, so O(q · log N) in all, where N is the largest number of boxes.
6Common mistakes
- One box at a time. Correct and simple, but the third test is two billion steps.
- Shrinking at “less than” rather than “at most”. By the statement a move happens when exactly a half (or a quarter) is occupied: the boundary is included.
- Shrinking several steps at once. If almost everything has been taken away, the hall does not shrink straight to the needed size but in steps, and at each step all the remaining boxes are carried. So after a shrink the threshold must be checked again.
- A 32-bit counter. Under the director's rule the answer reaches 10¹⁴.