Editorial for Baltic OI '02 P2 - Tennis Club
Submitting an official solution before solving the problem yourself is a bannable offence.
It's quite easy to recognize that this task is about reconstructing a graph from its degree sequence:
- https://mathworld.wolfram.com/DegreeSequence.html
- https://mathworld.wolfram.com/GraphicSequence.html
The important part from the above links is the following:
Hakimi (1962) and Havel (1955) showed that if a degree sequence is graphic, then there exists a graph such that the node of the highest degree is adjacent to the next highest degree vertices of , where is the maximum degree of .
Applying the above result recursively to the graph , we can conclude that the problem is solvable using the following greedy algorithm:
When implemented naively, the above algorithm can take steps in the worst case: the list of vertices is sorted times, with steps spent on each sorting. An obvious optimization is to use a better sorting algorithm, which yields steps in the worst case.
Another optimization is to take advantage of the fact that, after the first pass, the list of vertices is already mostly sorted. Leaving out the head element, which we can ignore during the next iterations, the rest of the list consists of two sorted sub-lists with known endpoints. Normally this kind of list could be re-sorted using a merge algorithm in linear time. In this case we need to do even less than a full merge, because we know that initially the list was sorted and the degree of each item in the first sub-list was reduced by one while the second sub-list did not change at all.
The above optimization does not give us better worst-case complexity if the indices have to be sorted on each output line, because for a complete or near-complete graph sorting the lists of indices would require about operations for each vertex, consuming a total of operations. However, because the indices are from a very narrow range, we can sort them in linear time using the counter-sort, and thus truly reduce the worst-case complexity to . Or, we could construct the graph into an adjacency matrix to avoid the counting step in the counter-sort.
Yet another optimization is to count the total sum of degrees when reading the data and use its parity as a quick rejection test. This does not change the worst-case complexity, but could still be handy in a real-life application if the problem source did not eliminate such inputs by definition.
Comments