The swap log
A warehouse is a long corridor lined with n cells; cell j is pj metres from the door. At first item i lies in cell i. In a month item i is fetched from the door fi times, and some pairs of items are picked together: pair (a, b) w times, and each time the picker walks the distance between their cells. The cost of a layout is the total walk for the month:
$$\sum_i f_i \cdot \mathrm{pos}(i) \; + \sum_{(a,\,b,\,w)} w \cdot \bigl|\mathrm{pos}(a) - \mathrm{pos}(b)\bigr|,$$where pos(i) is the distance from the door to the cell where item i currently lies.
An annealing program improved the layout. It wrote every move it accepted into a log: items x and y swapped cells. The cost itself did not make it into the log. Recover it: what was the cost at the start and after each swap?
Input
The first line holds n, m and q: the number of cells (and items), pairs and log entries (2 ≤ n ≤ 20,000, 0 ≤ m ≤ 20,000, 1 ≤ q ≤ 20,000). The second line holds p1, …, pn (0 ≤ pj ≤ 106), the third f1, …, fn (0 ≤ fi ≤ 104). Then m lines a b w: pairs of items (a ≠ b, 1 ≤ w ≤ 104); no pair repeats, and each item is in at most 40 pairs. Then q lines x y: the swaps in log order; x and y may coincide, and then nothing changes.
Output
q + 1 integers, each on a new line: the cost of the layout at the start and after each swap.
Examples
Example 1
3 1 2 0 10 20 1 1 1 1 3 5 1 2 3 1
130 80 80
Example 2
4 3 5 0 4 9 15 2 0 1 3 1 2 3 2 4 1 1 4 2 1 2 3 3 4 1 2 4 2 4
107 111 111 122 106 122
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 8 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
Recomputing the cost from scratch after each swap is O(n + m) per log entry, and there are up to 20,000 entries: hundreds of millions of operations. What actually changes when two items swap cells?
2Hint 2
Only the terms involving x or y change: two “walk from the door” terms and the pairs of these two items. Each item is in at most 40 pairs. And what about the pair if x and y themselves form one? And what if x = y?
3The idea
This is the very operation any fast annealing rests on: the change in cost from a move is computed over the move’s neighbours, not over the whole problem. Let item x lie at distance px from the door before the swap, and y at py. Then
Δ = fx(py − px) + fy(px − py) + Σ(x, z, w), z ≠ y w(|py − pos(z)| − |px − pos(z)|) + Σ(y, z, w), z ≠ x w(|px − pos(z)| − |py − pos(z)|).
Skip the pair (x, y): after the swap the distance between them is the same |px − py|. If it is not skipped, the formula counts it with positions where one of the two has already “moved” and the other not yet, and gets it wrong. A swap of an item with itself changes nothing and should simply be skipped: the formula with x = y would also give zero, but only provided the pair (x, x) is excluded, and there is no such pair anyway.
4Walkthrough
Keep pos, where each item lies, and for each item a list of its pairs with weights. Compute the initial cost in full, once. For each log entry compute Δ by the formula, swap pos[x] and pos[y], and add Δ to the cost. The cost reaches 1015: int64 in Go, an ordinary integer in Python.
The sixth test is real. The 32 letters of War and Peace stand in one row of keys 19 mm apart; an item is “fetched” as many times as the letter occurs (divided by 100), and the pairs are neighbouring letters that occurred in the text at least 100 times. The log is all 429 moves that an annealing of this very cost accepted: it falls from 10,154,569 to 6,025,204.
4+Solution
5Complexity
O(n + m) for the initial cost and O(deg x + deg y) ≤ O(80) per log entry: O(n + m + 80q) in all.
6Common mistakes
- Recomputing the whole cost. Correct, but on large logs hundreds of times over the limit.
- The pair (x, y) in both lists. If it is not skipped, the second example breaks on the very first entry: items 1 and 2 are a pair, and 87 comes out instead of 111.
- Swapping positions before computing. If you first swap pos and then compute Δ by the “old” positions, you get zero or a doubled error: the order matters.
- 32 bits. In the seventh test the cost is about 2·1014 and does not fit in an int32.