Parallel pairs
The event log is arranged as in the problem “Vector stamps”: P processes perform events one after another, and an event can receive a message and then knows everything the sending event knew. Event a happened before b if one can get from a to b along the next events of processes and along messages; if neither is before the other, the events are concurrent.
How many pairs of concurrent events are there in total? A pair is unordered: {a, b} counts once. One of the tests is this site’s git history, where a commit is an event of its branch and a merge receives a “message” from the commit being merged.
Input
The first line holds P and E (1 ≤ P ≤ 30, 1 ≤ E ≤ 5·104). Then E lines: the process number p, the number k of messages received, and the numbers of the k sending events, all smaller than the number of the current event; the total of k is at most 105.
Output
A single number: the number of pairs of concurrent events.
In the first example five pairs are concurrent: event 5, a new event of process 1 that nobody learned about, is concurrent with events 2, 3, 4 and 6; in addition, events 1 and 2 are concurrent. In the second example the processes do not exchange messages, and every pair of events of different processes is concurrent.
Examples
Example 1
3 6 1 0 2 0 2 1 1 3 1 3 1 0 3 0
5
Example 2
2 4 1 0 2 0 1 0 2 0
4
Limits
- Time · Python
- 10000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 7 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
Enumerating all pairs is more than a billion with fifty thousand events. Take an event e of process p and another process q. Which events of q are before e, which after, and how are they arranged along q?
2The idea
Compute vector clocks as in “Vector stamps”. The events of process q that are before e are the first VCe[q] events of q: knowing the j-th event of a chain means knowing all before it too. The events of q that are after e are those that know e, that is, those with at least e’s number within p in position p. Along process q this position only grows, so those knowing e form a tail of the chain of q, whose start is found by binary search. Everything between the first VCe[q] events and the tail is concurrent with e.
3Walkthrough
For each pair of processes (p, q), write out how much each event of q knows about p: a non-decreasing list. For the i-th event e of process p, find in it the first position with a value of at least i; the number of events of q concurrent with e is that position minus VCe[q]. The sum over all e and q ≠ p counts each concurrent pair twice, once from each side, so divide by two. Pairs within one process are never concurrent.
Instead of binary search, two pointers work too: on moving to the next event of p, the boundary of the tail in q only moves forward. In this site’s git history there are 31,873 concurrent pairs out of 790,653, about 4%: branches are short-lived and merged into the main one often.
3+Solution
4Complexity
O(E · P) for the vectors and O(E · P · log E) for the count (with two pointers, O(E · P)). The answer reaches over a billion, as in the fifth test the processes do not exchange messages at all, so a 64-bit counter is needed.
5Common mistakes
- Equal Lamport numbers. Concurrent events can have any Lamport numbers, and equal numbers occur only for concurrent events, but far from all of them. The answer comes out too small; the first example catches this.
- Enumerating pairs with vectors. Correct, but O(E² · P), tens of billions of operations.
- A pair twice. The sum over events sees each pair from both sides; do not forget to divide.
Algorithms behind it
O(1) per event for Lamport, O(n) for vectors
2 problems
SRT
Algorithm
Binary search
Finds the “no → yes” boundary in ordered data in log₂ n checks.
O(log n)
2 problems