PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Recursion (or math), Graphs (?)
PROBLEM:
Given N, a set of pairs of integers \{(A_i, B_i) \mid 1 \leq i \leq K\} is called good if:
- 1 \leq A_i \lt B_i \leq N
- It’s possible to sort every permutation P of \{1, \ldots, N\} by using only swaps of the form (A_i, B_i).
Across all possible good sets, find the minimum possible value of \sum_{i=1}^K (A_i\oplus B_i).
EXPLANATION:
The obvious first step is to try and understand when a set of pairs is good.
More specifically, when are we able to sort every permutation using a certain set of swaps?
To understand this, it’s helpful to analyze a singular case: suppose we have some permutation P, and we want to just swap the values at indices x and y without affecting any other values. When is this possible?
The answer to this is straightforward: this is possible if and only if we have a sequence of swaps (x, x_1), (x_1, x_2), (x_2, x_3), \ldots, (x_m, y).
That is, we need a “path” from x to y using swaps.
Why?
First off, it’s easy to see that if we’re able to move the value at index x (which we’ll call P_x) to index y, such a path must surely exist: just trace the swaps that move P_x till it reaches y.
On the other hand, suppose such a path does exist. Then, we have the following:
- First, use the swaps (x,x_1), (x_1, x_2), \ldots, (x_m, y) in order.
This will place P_x at index y, and place P_{x_i} at index x_{i-1} (where we treat x_0 = x and x_{m+1} = y).- Next, use the swaps (x_{m-1}, x_m), (x_{m-2}, x_{m-1}), \ldots, (x, x_1) in order.
Essentially, we ‘reverse’ the path we first followed.
This will send the value P_y all the way back to index x, while placing everything else in the middle back in their original positions.
Now, we need to be able to sort every permutation.
This means that the swaps should allow for a “path” for every pair (x, y); since if even one such path is missing, it won’t be possible to sort the permutation that has all elements in place except for the missing pair being swapped.
Since we’re talking about paths here, it’s a bit nicer to think in terms of graphs.
We have with us N vertices, and each swap corresponds to an edge in the graph.
We want the edges to be such that there’s a path between each pair of vertices.
This just means the graph must be connected!
So, quite simply, a set of swaps is good if the graph corresponding to it is connected.
Now that we can characterize good sets, let’s try to minimize \sum_{i=1}^K (A_i\oplus B_i).
Essentially, this says that including (A_i, B_i) has a cost of (A_i\oplus B_i).
So, we have several edges, and we’re trying to find the smallest cost of choosing some of them such that the resulting graph is connected.
This is exactly what the minimum spanning tree of the graph is!
Our goal is thus to compute the weight of a minimum spanning tree on the complete graph on vertices \{1, 2, \ldots, N\}, with the weight of edge (u, v) being u\oplus v.
One way to do this is as follows.
Let k be the largest integer such that 2^k \leq N.
Observe that no matter what, we need an edge between some vertex in [1, 2^k-1] and some vertex in [2^k, N] to connect them.
This edge will have a weight of at least 2^k, since the k-th bit will be set in the XOR.
Specifically, it can be seen that:
- If N = 2^k, the lowest possible weight is 2^k+1, obtained by joining 1 and 2^k.
- If N \gt 2^k, the lowest weight is 2^k, obtained by joining 1 and 2^k+1.
Suppose we include this minimal weight edge in the answer.
We then need to connect the parts [1, 2^k-1] and [2^k, N] among themselves.
Observe that it’s always optimal to solve these two parts separately, i.e. we’ll never need to take another edge connecting them.
This is because the weight of any connecting edge is at least 2^k, while the weight of every edge within each of the parts is \lt 2^k (in [1, 2^k-1] all elements don’t have 2^k set, while in [2^k, N] all elements have 2^k set so the XOR of any pair will have it unset).
Kruskal’s algorithm tells us that the greedy strategy of choosing edges in ascending order of their weights is optimal for an MST, which is why we’ll never need to pick a second edge of weight \geq 2^k.
We now have to solve for the parts [1, 2^k-1] and [2^k, N].
[1, 2^k-1] can be solved recursively since it’s also just a segment of consecutive values starting at 1.
[2^k, N] on the other hand works slightly differently.
Every number here has the 2^k bit set, so for the purposes of XOR this bit can be ignored entirely.
This means solving for [2^k, N] is equivalent to solving for [0, N - 2^k].
How to solve for [0, N - 2^k], or more generally, for some [0, R]?
It’s not hard to see that the same greedy algorithm works: choose the highest power of 2 not exceeding R, take the minimum weight edge involving this power, and then split into two.
The difference is that if 2^m \leq R is the largest power of 2 available, the weight of the chosen edge will always be just 2^m, since we can pair 0 with 2^m (note that when the left endpoint was 1, the value 0 wasn’t available to us).
This gives rise to the following recursive solution.
Define f_1(N) to be the minimum cost of an MST connecting \{1, 2, \ldots, N\}.
Define f_0(N) to be the minimum cost of an MST connecting \{0, 1, 2, \ldots, N\}.
Then, if 2^k \leq N is the largest power of 2, we have:
- f_0(N) = 2^k + f_0(2^k-1) + f_0(N-2^k)
- f_1(N) = 2^k + [N = 2^k] + f_1(2^k-1) + f_0(N - 2^k)
Here, the expression [N = 2^k] evaluates to 1 if N = 2^k and 0 otherwise.
Now, if implemented directly, this will run in \mathcal{O}(N) time.
However, observe that certain parts of both recursions are recomputed over and over again - specifically, the values f_0(2^k-1) and f_1(2^k-1) for 0 \leq k \lt 30.
So, precompute and store all possible values of these two functions. After than, note that in each recursive call we only have one branch rather than two (because one of the two branches is always a previously stored value).
Further, the branch we do recurse into at least halves N because we subtract the largest power of 2 from it; so after at most \mathcal{O}(\log N) steps we’ll end up stopping.
So, simply caching the values of f_0(2^k-1) and f_1(2^k-1) makes the above recursion run in \mathcal{O}(\log N) time, which is fast enough!
TIME COMPLEXITY:
\mathcal{O}(\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
from functools import lru_cache
@lru_cache(maxsize=None) # for each caching of results
def calc(l, r):
if l >= r: return 0
if l+1 == r: return l^r
pw = 1
while 2*pw <= r: pw *= 2
if r == pw: return pw+l + calc(l, r-1)
else: return pw + calc(l, pw-1) + calc(0, r-pw)
for _ in range(int(input())):
n = int(input())
print(calc(1, n))