Merge edits without a server
Several people edit a shared document, each in their own copy, without a server. The document is a sequence of elements, and each element has its own id, a pair (c, r): a counter and the number of the copy where the element was created. Of two ids, the greater is the one with the greater c, and with equal c the one with the greater r. A new element's id is always greater than the ids of all elements its copy knew of at the moment of insertion.
The operations are these. I c r lc lr t inserts the element with id (c, r) and value t right after the element (lc, lr); the id (0, 0) means the start of the document. D c r deletes the element (c, r). Operations arrive at a copy in any order in which an element appears before it is mentioned. The order of insertions at one place is set so that all copies arrive at one document: if several elements were inserted after the same element, the one with the greater id comes first among them, together with everything later inserted after it.
Print the document that results after all operations. One of the tests is a real style edit of a chapter of this site's basic course, divided between three editors: an element is a word or a run of spaces, and its value is the word's number in the dictionary.
Input
The first line holds the number of operations n (1 ≤ n ≤ 2·105). Then n operations in the order received. All ids are integers from 0 to 109, element values integers from 1 to 106. Each element is inserted once and deleted at most once.
Output
The values of the document's elements that are not deleted, in order, separated by spaces.
In the first sample copy 1 types 10, 20, 30, and copy 2, already knowing about 10, types 40, 50 right after 10. The id (3, 2) of the element 40 is greater than the id (2, 1) of 20, so 40 and everything inserted after it goes before 20. Then 20 is deleted. The second sample is the same operations in a different order, and the document is the same.
Examples
Example 1
6 I 1 1 0 0 10 I 2 1 1 1 20 I 3 1 2 1 30 I 3 2 1 1 40 I 4 2 3 2 50 D 2 1
10 40 50 30
Example 2
6 I 1 1 0 0 10 I 3 2 1 1 40 I 2 1 1 1 20 I 4 2 3 2 50 D 2 1 I 3 1 2 1 30
10 40 50 30
Limits
- Time · Python
- 8000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 6 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
Inserting “right after the left neighbour” will not work: the result depends on the order in which operations arrive, and that differs between copies. What lies after the left neighbour at the moment of insertion, and how do you tell which of those elements to skip?
2The idea
This is RGA, the replicated growable array. Insert e after x like this: stand on x and, while the next element has an id greater than e's, move to it; then insert e right after the current one. Why is this right? The elements with ids greater than e's that lie after x are insertions after x concurrent with e that come before it by the rule, together with everything inserted after them later: those have even greater ids, since their copy already knew of their predecessors. The first element with an id smaller than e's must go after e: it is either a concurrent insertion after x that gives way to e, or an element that lay after x before e was inserted, and in the copy where e was created it also ended up after e.
A deletion shifts nothing: the element becomes a tombstone, stays in the chain and still serves as a neighbour for other copies' insertions that may refer to it. Tombstones are skipped in the output.
3Walkthrough
Keep the document as a linked list in a dictionary: id → next id, plus a dictionary of values and a set of deleted ids. An insertion is hops along the list from the left neighbour, a deletion is a mark, the output is a pass from the start. Ids are compared as pairs, first the counter, then the copy.
On the third test, the real edits of three editors, the document converges to the very style edit one person made: 16,684 elements. There are no conflicts because the editors changed different words; where they change the same word differently, RGA keeps both variants side by side, and a person has to choose between them.
3+Solution
4Complexity
Each insertion passes the elements inserted after its neighbour with greater ids; in human edits there are almost none, and an insertion costs O(1) on average. In the worst case, many concurrent insertions at one place, the pass is longer, but it is still bounded by the number of such insertions. Memory is O(n): deleted elements do not disappear.
5Common mistakes
- Inserting right after the neighbour. The order of two concurrent insertions at one place then depends on the order of delivery: in the second sample the answer changes.
- Deleting for real. If a deleted element is thrown out of the list, another copy's insertion that arrives later and refers to it loses its place.
- A position instead of an id. Keeping the document as an array and searching for the neighbour by scanning is O(n) per operation; the sixth test is eighty thousand insertions in a row.