PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Alex Danilyuk
Tester: Harris Leung
Editorialist: Pratiyush Mishra, Jakub Safin
DIFFICULTY:
Hard
PREREQUISITES:
Degree sequences, dynamic programming
PROBLEM:
Given a sequence D_1, D_2, \ldots, D_N, construct a connected simple graph on N vertices such that the degree of i is at most D_i and the XOR of all degrees is 0.
EXPLANATION:
Let’s sort the sequence D in non-increasing order. Then, the degree sequence d_1, d_2, \ldots, d_N is best made in non-increasing order too - any other valid sequence can be sorted by repeatedly swapping d_x and d_y (x \lt y, d_x \lt d_y) which keeps the sequence valid.
One necessary condition for a valid degree sequence is that \sum d_i must be even, known as the handshaking lemma. As long as the XOR of all d_i has bit 0 equal to zero, this is immediately fulfilled.
Connectedness
The obvious necessary condition here is d_i \gt 0 for each i and \sum d_i \ge 2(N-1). If we have a simple non-connected graph with a degree sequence satisfying this condition, we can make it connected while keeping degrees unchanged.
Since the graph is non-connected and contains at least N-1 edges, there must be a cycle in some connected component (CC) c_1. Let’s remove one edge u-v from this cycle, which doesn’t break its CC. There must be an edge outside this CC since there are no isolated vertices; let’s remove one such edge w-s, which might break a CC different from c_1 into two, denoted by c_2 and c_3. We add edges a-w and b-s, which connects CCs c_2 and c_3 to c_1. The graph remains simple since c_1 \neq c_2,c_3.
If c_2 = c_3, the second added edge creates a cycle and we just connected two CCs into one. Otherwise we broke a CC and then connected three CCs into one. Either way, the number of CCs decreases by one and we can repeat the process until there’s just one CC. In fact, we can use it in construction - find a not necessarily connected solution satisfying these inequalities and convert it in O(NM) time to a connected solution.
Simpleness: Erdős-Gallai theorem
The necessary and sufficient condition for existence of a simple graph with our degree sequence d_1, d_2, \ldots, d_N with even sum is that for each k (1 \le k \le N),
\sum_{i=1}^k d_i = L_k \le R_k = k(k-1) + \sum_{i=k+1}^N \min(k,d_i) \,.
(If we were allowed to make parallel edges but no loops, d_1 \le \sum_{i=2}^N d_i would be the only condition. It’s also immediately fulfilled by XOR zero since a \oplus b \ge a-b.)
When we move from k to k+1, the left side increases by d_{k+1}, the first term on the right side increases by 2k and the second term decreases at most by d_{k+1}. Once d_{k+1} \le k holds for the first time, it’ll hold for any larger k and the difference R_k-L_k will be non-decreasing, so we only need to check the conditions up to this k and can ignore greater values of k. This helps a lot in graphs that have very few high-degree vertices.
The condition for k=1 simply says d_1 \le N-1, so we can ignore it. The condition for k=2 is d_1+d_2 \le 2N-2-n_1 if n_1 \le N-2. For k=3 and n_1+n_2 \le N-3, the condition’s d_1+d_2+d_3 \le 3N-3-2n_1-n_2. With the observation above, it’ll turn out that we won’t need to directly evaluate the conditions for any higher k, but we only need the guarantee that when they’re all fulfilled, a solution exists.
Simpleness + construction: Havel–Hakimi algorithm
In short, we construct a simple graph with degree sequence d_1, d_2, \ldots, d_N from a graph with N-1 vertices and degree sequence d_2-1, \ldots, d_{d_1+1}-1, d_{d_1+2}, \ldots, d_N (d_1 \le N-1) by connecting vertex 1 to vertices 2, \ldots, d_1+1. The only catch is that the smaller degree sequence needs to be sorted in non-increasing order again, but if the original sequence was sorted, then re-sorting is easy. This construction takes O(N^2) time.
Looking for a sparse graph
If we have a valid degree sequence and subtract the same number s from some two degrees d_i and d_j, such that the sequence doesn’t need to get reordered, then Erdos-Gallai conditions for k \ge \min(i,j) will still hold, because L_k decreases by s and R_k decreases by at most s. Specifically, for i=1, we obtain a valid graph.
Intuition should tell us that we want to make the resulting graph quite sparse, especially by decreasing large degrees. The only lower limit comes from connectedness, otherwise we can even see that when the sum of degrees is O(N), then Erdos-Gallai conditions for k \gg O(\sqrt{N}) are automatically fulfilled.
Consider any (not necessarily valid) degree sequence with XOR zero. To avoid reordering the sequence, let’s try subtracting 1 from some elements greater than 1; if there are multiple elements with the same value, we subtract from the last one. Can we do it while keeping the zero XOR?
- If the sum of degrees is \le 2(N-2), then we stop. In particular, this includes d_2 = 1, so d_2 \ge 2 from now on.
- If there are at least two odd degrees greater than 1, we subtract 1 from each.
- If there are only even degrees greater than 1, we find the lowest set bit (LSB) in each of them. Consider the lowest value of this LSB. Since the XOR was zero, there must be an even number of degrees with this lowest LSB; degrees 1 don’t change anything since it’s LSB of even numbers, and all degrees with greater LSB have that bit set to 0. Therefore, we can find two degrees with bit b \gt 0 as the LSB and subtract 1 from each. This doesn’t change the XOR.
- Finally, if there’s exactly one odd degree greater than 1, we can subtract 1 from that (changing XOR to 1), do the same thing as above, which creates two odd numbers, and subtract 1 from either of them to fix the XOR.
We’re always only subtracting 2 or 4. That’s great news - from an even sum of degrees \ge 2(N-2), we can always reach exactly 2(N-2) or 2N, all while keeping the conditions for XOR and connectedness! What about Erdos-Gallai conditions?
- Let’s assume that a condition for some k is violated. Then L_k \gt k(k-1)+N-k and at the same time from sum of degrees, L_k \le 2N-(N-k), so N+k \gt k^2-2k+N must hold. This is obviously impossible for k \ge 3, we already know that k=1 is never violated and for k=2, it’s only possible if L_k = 2N-(N-k), which means sum of degrees 2N with d_3 = 1.
- In addition, if d_1 and d_2 are even, we can still subtract 2. Since XOR is zero, we only need to deal with the case d_1=2a+1, d_2=2a and 2N=(2a+1)+(2a)+(N-2), so a=(N+1)/4.
- If D_4 \ge 2, we can change d_3 and d_4 to 2; this doesn’t change XOR, fixes the condition for k=2, and since d_3 \le 2, we already know that conditions for greater k will also hold.
Note that when we were subtracting 4, this wouldn’t be allowed if we were changing (3,2) \rightarrow (2,2) \rightarrow (1,1) \rightarrow (1,0), but in such a case, there wouldn’t be any other degrees \ge 2 (their LSB would have to be \ge 2 so we’d be able to find two with the same LSB) and there are no such sequences with XOR zero and sum \gt 2N.
The special case
The only case we haven’t solved is D_4 = 1. However, there are only O(N^2) possible degree sequences there, since D_3 uniquely determined by D_1 and D_2, and we don’t need to check conditions for k \ge 4 if those for k=2 and k=3 hold. We can deal with it using brute force - find one valid degree sequence or determine that none exist.
Initial sequence
In all other cases, we described a way to find a valid degree sequence. We just need to find one that satisfies the conditions for connectedness and XOR. (If there are no such sequences, there’s obviously no solution.)
Let’s employ dynamic programming. If we picked d_1, \ldots, d_i and got XOR x, the largest possible sum is dp_{i,x}. We try all values d_{i+1} \le D_{i+1}, all values of x and update dp_{i+1,\cdot}.
Since the largest bit in x is (at most) the largest bit in N-1, we can’t have x \ge 2(N-1). Still, the time complexity is O(N^2 + N\sum D_i) = O(N^3), so we need to speed it up when \sum D_i \gg N.
- In such a case, let’s start by using only the highest set bit from each D_i in d_i.
- Then for each bit b \gt 0 from highest to lowest, if there’s an odd number of degrees equal to 2^b, we change one of them to 2^{b-1}. Once we’re done, all bits except bit 0 occur an even number of times, so the XOR is 0 or 1.
- If the XOR is 1 and there’s an even degree d_i \lt D_i, we can add 1 to d_i.
- If D_1 = d_1, then D_1 = 2^b. Otherwise d_1 = 1 since all degrees created so far were powers of 2.
- With D_1 = d_1 = 2^b and b \gt 1, we have d_2 = d_1 because of XOR, and we can decrease the last two degrees equal to 2^b by 1 and 2 respectively. This fixes the XOR from 1 to 0.
- The only failure cases we have here are with d_1 \le 2, so \sum d_i \le 2N.
In the first step, we have 2d_i \gt D_i, so \sum d_i \ge (N + \sum D_i) / 2. In the second step, for each b such that 1 \lt 2^b \lt N, we subtract at most 2^{b-1} from \sum d_i, which is at most N-2 in total. Finally we subtract at most 3. We end up with \sum d_i \ge (\sum D_i - N - 2) / 2. If \sum D_i \ge 5N+4, then \sum d_i \gt 2N, which means we don’t reach either failure case and found a sequence we can use as our initial sequence.
If \sum D_i \lt 5N+4, we just use the DP approach, which is now fast enough.
Decreasing degrees quickly
Getting a degree sequence with sum \le 2N has been described above, but the straightforward approach decreases the sum by 2 or 4 in O(N) time. We could customise the lookup for large \sum D_i (which was already quite custom) to produce a degree sequence with reasonably small sum, but we can also implement it efficiently in general.
We’re always picking two degrees \gt 1 based on their LSB. Let’s group those elements based on LSB - there are O(\log N) groups. We always pick two elements with the same LSB and change them, or change an odd element. This way, we decrease the sum of degrees by 2 or 4 in O(\log N) time, just because we need to look up an LSB with two elements. New LSB can be precalculated O(N \log N).
The next speedup comes from the observation that we don’t need to always subtract 1 but if the LSB of any two elements is the b-th bit, then subtracting anything \le 2^b still keeps XOR unchanged; we only used the lowest LSB to find two elements. We get three possible situations if we find two such elements:
- we can’t subtract exactly 2^b because the sum of degrees would drop below 2(N-1); in this case, we just subtract what we can and we’re done
- we can’t subtract exactly 2^b because it’d create degrees 0, so we subtract {2^b}-1, creating two elements equal to 1
- we subtract exactly 2^b from both chosen elements; this just sets their b-th bits to zero
The first situation can only happen once, the second only O(N) times and the last one decreases the sum by 2^{b+1} after O(b) LSB lookup. Since O(2^b) \ge O(b), the LSB lookup can only take O(\sum D_i) amortised time. Once there are no two elements \gt 1 with the same LSB, there are O(\log N) elements \gt 1 so \sum d_i is O(N \log N) and the rest of the subtracting always takes at most O(N \log^2 N) time.
We didn’t bother with keeping the degree sequence non-increasing here, but since we already know that this’ll give a valid sequence, and unlike Erdos-Gallai theorem or graph construction, it doesn’t directly rely on sortedness, we can just sort the resulting valid sequence.
Summary
- If D_4 = 1, use brute force to find a degree sequence for a valid solution - or report that there’s no solution.
- Otherwise, find a degree sequence with positive elements, XOR zero and sum \ge 2(N-2) - or report that there’s no solution. Then convert it into a degree sequence for a valid solution by subtracting from degrees.
- Construct a graph with this valid degree sequence.
- Make this graph connected.
TIME COMPLEXITY:
Since we always construct a sparse graph, each of the key steps can be done in O(N^2).