PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: souradeep1999
Tester & Editorialist: iceknight1093
DIFFICULTY:
3054
PREREQUISITES:
Familiarity with bitwise XOR, careful case analysis
PROBLEM:
Given a complete graph on N vertices and two of its vertices u and v, find the maximum bitwise XOR of a path from u to v, and any one shortest path that attains this maximum.
EXPLANATION:
The bitwise XOR operation is associative, so the order in which our path visits vertices doesn’t really matter — we only need to ensure that no vertex is visited more than once; and that u and v are visited.
This means we only care about subsets of vertices — their order can be fixed afterwards.
In fact, this observation is enough to solve subtask 1.
N \leq 20, so simply check every subset of vertices that contains both u and v, and take the best one (maximum bitwise XOR, then minimum size).
Let N be a (k+1)-bit integer, i.e, 2^k is the highest power of 2 in its binary representation.
Clearly, the maximum possible XOR attainable is 2^{k+1} - 1; so we’d like to figure out:
- Whether it’s possible to reach this
- The shortest path to reach it
Time for a bit of case analysis!
Let M = 2^{k+1} - 1. Then,
- If u\oplus v = M, we’re done with a length-2 path
- If not, let’s check for a length-3 path.
For this, we’d need a w such that u\oplus v \oplus w = M, or w = M\oplus u\oplus v.
If this w is valid (i.e, is \leq N and equals neither u nor v), we’re done.
Otherwise, there are a couple of points of failure; so let’s see what happens.
If w \leq N, then we run into issues only if w = u or w = v.
Without loss of generality, let w = u.
Then, along with u\oplus v\oplus w = M, we’ll have v = M (which also means that N = M).
So, all we need to do is find two vertices x and y (distinct from u and v) such that x\oplus y = w; then we can take the path u\to x\to y \to v.
This is fairly easy because N = M and we have only two ‘bad’ vertices; for example either the pair (1, w\oplus 1) or the pair (2, w\oplus 2) will work.
So far, we’ve always been able to attain a maximum of M; and have used at most 4 vertices (including u and v) to do so.
Notice that this is enough to solve subtask 2; since N = 2^{k+1} - 1 = M is guaranteed here.
Now, let’s look at the remaining case when we can’t reach M using \leq 3 vertices, i.e, w \gt N.
We want to select a minimum-sized subset of integers from 1 to N (excluding u and v), such that their XOR equals w.
Note that w\gt N, which means w has 2^{k-1} set in its binary representation.
In particular, this means that the subset we choose should certainly include an integer \geq 2^k.
Suppose N = 2^k + r, where 0 \leq r \lt 2^k.
Then, if r is large enough, finding a pair of valid vertices whose XOR is w is not hard.
In particular, if r \geq 2 then it can be shown that at least one of the pairs (2^k, 2^k \oplus w), (2^k+1, (2^k + 1)\oplus w), (2^k+2, (2^k+2)\oplus w) will work, so path length = 4 in these cases.
This leaves us with r = 0 and r = 1 to deal with.
r = 0
When r = 0, we have N = 2^k.
Note that since u, v \leq N and w \gt N, we can’t have u = 2^k or v = 2^k once we’re in this case — that means u, v \lt N.
Let’s check if a size-4 subset is possible.
For this, recall from earlier that we must choose something with 2^k set; and our only option is to choose 2^k itself.
So, check if (2^k, w\oplus 2^k) works.
If it does, great, we’re done in 4 moves.
Otherwise, since we know u, v \neq 2^k, we only failed because either u or v equals 2^k \oplus w. WIthout loss of generality, let it be u.
Along with u\oplus v \oplus w = M, we have v = 2^k-1.
Now that u and v are fixed, a subset of size 5 works: (at least) one of (2^k, 1, u\oplus 1) or (2^k, 2, u\oplus 2) will work.
r = 1
Just as we did in the r = 0 case, let’s check if a subset of size 4 works.
There are only two possibilities for the pair here: (2^k, 2^k\oplus w) and (2^k+1, (2^k+1)\oplus w).
Check both, and if one of them works we’re done.
If they both fail, we have two possibilities: u, v \lt N, or (u, v) = (2^k, 2^k+1).
The u, v \lt N case is similar to how it was in r = 0, so the answer equals 5 there.
The (u,v) = (2^k, 2^k+1) case is a bit more interesting: it’s the only case when we can’t achieve M as the maximum!
This is because u\oplus v = 1 and there are no more vertices with 2^k set that we can choose from.
So, in this case alone, the maximum XOR is in fact 2^k-1, and can be achieved with a subset of size 3.
This takes care of all the cases.
Some of the discussion above doesn’t work when N is very small, because having too few vertices to choose from constraints freedom a bit.
The safest way to do this is to just bruteforce for small enough N, and apply the casework for larger ones.
The casework above definitely works for N \geq 8, so bruteforcing when N \leq 7 is good enough.
Implementing this might seem painful with all the cases we have, but there’s a fairly simple way to implement the solution:
- First, do a brute for small N.
- Then, check if the maximum can be M (which is almost always the case).
- For this,
- Checking if 2 or 3 vertices are enough is trivial
- Checking if 4 vertices are enough (i.e, \{u, v, x, y\}) can be done in \mathcal{O}(N): iterate over all choices of x, which also fixes y and then their validity can be checked.
- Next, check if 5 vertices are enough.
This can also be done in \mathcal{O}(N) time by noting that whenever the answer is 5, there’s always a solution that picks either vertex 1 or 2.
So, fix one of these and then run the \mathcal{O}(N) solution for four vertices
- If all the above fail, we’re in the special case where the answer is \lt M, and that can be solved using three vertices as mentioned above.
This way, you only need to write a handful of loops and if statements.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define ordered_set tree<int, nuint_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N=100005;
#define M 1000000007
#define BINF 1e16
#define init(arr,val) memset(arr,val,sizeof(arr))
#define MAXN 10000005
#define deb(xx) cout << #xx << " " << xx << "\n";
const int LG = 22;
bool isPath(vector<int> arr, int n, int u, int v) {
for(auto i : arr) {
if(i < 1 or i > n) return false;
if(i == u or i == v) return false;
}
return true;
}
void solve() {
int n, q;
cin >> n >> q;
if(n <= 7) {
vector<vector<vector<int>>> path(n + 1, vector<vector<int>>(n + 1));
vector<vector<int>> V(n + 1, vector<int> (n + 1, 0));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i == j) continue;
vector<int> a;
int c = 0;
for(int mask = 1; mask < (1LL << n); mask++) {
vector<int> arr;
arr.push_back(i);
for(int l = 0; l < n; l++) {
if((mask & (1LL << l)) > 0) {
if((l + 1) == i or (l + 1) == j) continue;
arr.push_back(l + 1);
}
}
arr.push_back(j);
int len = 0;
for(auto l : arr) {
len = len ^ l;
}
if(len > c) {
c = len;
a = arr;
V[i][j] = len;
} else if (len == c) {
if(arr.size() < a.size()) {
c = len;
a = arr;
V[i][j] = len;
}
}
}
path[i][j] = a;
}
}
while(q--) {
int u, v;
cin >> u >> v;
vector<int> arr = path[u][v];
cout << V[u][v] << ' ' << arr.size() << endl;
for(auto i : arr) {
cout << i << ' ';
}
cout << endl;
}
return ;
}
int x = log2(n);
int len = (1LL << (x + 1)) - 1;
while(q--) {
int u, v;
cin >> u >> v;
int u1 = u, v1 = v;
if(u > v) {
swap(u, v);
}
if(n == ((1LL << x) + 1) and u == (1LL << x) and v == ((1LL << x) + 1)) {
cout << (1LL << x) - 1 << ' ' << 3 << endl;
cout << u1 << ' ' << ((1LL << x) - 2) << ' ' << v1 << endl;
continue ;
}
int c = u ^ v;
if(c == len) {
cout << (1LL << (x + 1)) - 1 << ' ' << 2 << endl;
cout << u1 << ' ' << v1 << endl;
continue ;
}
c = len ^ u ^ v;
if(c <= n) {
if(c == u or c == v) {
if(isPath({1, 1 ^ u}, n, u, v)) {
cout << (1LL << (x + 1)) - 1 << ' ' << 4 << endl;
cout << u1 << ' ' << 1 << ' ' << (1 ^ u) << ' ' << v1 << endl;
} else {
cout << (1LL << (x + 1)) - 1 << ' ' << 4 << endl;
cout << u1 << ' ' << 2 << ' ' << (2 ^ u) << ' ' << v1 << endl;
}
} else {
cout << (1LL << (x + 1)) - 1 << ' ' << 3 << endl;
cout << u1 << ' ' << c << ' ' << v1 << endl;
}
} else {
int r = n - (1LL << x);
if(r >= 2) {
for(int i = 0; i <= 2; i++) {
if(isPath({(1LL << x) + i, ((1LL << x) + i) ^ c}, n, u, v)) {
cout << (1LL << (x + 1)) - 1 << ' ' << 4 << endl;
cout << u1 << ' ' << (1LL << x) + i << ' ' << (((1LL << x) + i) ^ c) << ' ' << v1 << endl;
break ;
}
}
} else if (r == 1) {
int f = 0;
for(int i = 0; i <= 1; i++) {
if(isPath({(1LL << x) + i, ((1LL << x) + i) ^ c}, n, u, v)) {
f = 1;
cout << (1LL << (x + 1)) - 1 << ' ' << 4 << endl;
cout << u1 << ' ' << (1LL << x) + i << ' ' << (((1LL << x) + i) ^ c) << ' ' << v1 << endl;
break ;
}
}
if(f == 1) {
continue ;
}
cout << (1LL << (x + 1)) - 1 << ' ' << 5 << endl;
cout << u1 << ' ' << (1LL << x) + 1 << ' ' << 2 << ' ' << (1LL << x) - 3 << ' ' << v1 << endl;
} else {
int f = 0;
if(isPath({1LL << x, (1LL << x) ^ c}, n, u, v)) {
f = 1;
cout << (1LL << (x + 1)) - 1 << ' ' << 4 << endl;
cout << u1 << ' ' << (1LL << x) << ' ' << ((1LL << x) ^ c) << ' ' << v1 << endl;
}
if(f == 1) {
continue;
}
if(isPath({1LL << x, 1, 1 ^ u}, n, u, v)) {
cout << (1LL << (x + 1)) - 1 << ' ' << 5 << endl;
cout << u1 << ' ' << (1LL << x) << ' ' << 1 << ' ' << (1 ^ u) << ' ' << v1 << endl;
} else {
cout << (1LL << (x + 1)) - 1 << ' ' << 5 << endl;
cout << u1 << ' ' << (1LL << x) << ' ' << 2 << ' ' << (2 ^ u) << ' ' << v1 << endl;
}
}
}
}
}
#undef int
int main() {
#define int long long int
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("optput.txt", "w", stdout);
#endif
// int T;
// cin >> T;
// for(int tc = 1; tc <= T; tc++){
// cout << "Case #" << tc << ": ";
solve();
// }
return 0;
}
Editorialist's code (Python)
n, q = map(int, input().split())
mx = 1
while mx < n: mx = mx*2 + 1
def solve(u, v):
if n <= 10:
u -= 1
v -= 1
mxxor, ans = -1, 0
for mask in range(1 << n):
if ~mask & ((1 << u) | (1 << v)): continue
cur = 0
for i in range(n):
if mask & (1 << i): cur ^= i+1
if cur > mxxor: mxxor, ans = cur, mask
elif cur == mxxor:
if bin(ans).count('1') > bin(mask).count('1'): ans = mask
print(mxxor, bin(ans).count('1'))
print(u+1, end = ' ')
for i in range(n):
if i == u or i == v: continue
if ans & (1 << i): print(i+1, end = ' ')
print(v+1)
return
# Length 2
if u^v == mx:
print(mx, 2)
print(u, v)
return
# Length 3
w = mx^u^v
if w <= n and w != u and w != v:
print(mx, 3)
print(u, w, v)
return
# Length 4
for x in range(1, n+1):
y = w^x
if min(x, y) > 0 and max(x, y) <= n and len(set([u, v, x, y])) == 4:
print(mx, 4)
print(u, x, y, v)
return
# Length 5
# One vertex can always be 1 or 2; then run the loop for 4
for z in [1, 2]:
for x in range(1, n+1):
y = w^x^z
if min(x, y) > 0 and max(x, y) <= n and len(set([u, v, x, y, z])) == 5:
print(mx, 5)
print(u, x, z, y, v)
return
# Length 3, special case ans < mx
print(n-2, 3)
print(u, (n-2)^1, v)
return
for _ in range(q):
u, v = map(int, input().split())
solve(u, v)