PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: chroot_
Tester: kaori1
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Familiarity with bitwise arithmetic, pigeonhole principle
PROBLEM:
You are given a tree, with vertex i having the value A_u written on it.
Process Q queries:
- Update the value of a vertex.
- Given u and v, find the minimum value of \left\lfloor \frac{A_x + A_y}{2} \right\rfloor - (A_x\ \& \ A_y) of values of some two vertices x and y lying on the path from u to v.
EXPLANATION:
\left\lfloor \frac{x + y}{2} \right\rfloor - (x\ \& \ y) is a bit unwieldy to work with, so let’s simplify it a bit.
There is a (perhaps well-known) identity relating bitwise AND and addition:
x+y = (x\oplus y) + 2\cdot (x\ \&\ y) (where \oplus denotes bitwise XOR)
Dividing by 2 and bringing it to the form we have by taking floor, it can be seen that
Further, observe that \left\lfloor \frac{x\oplus y}{2} \right\rfloor = \left\lfloor \frac{x}{2}\oplus \frac{y}{2}\right\rfloor, since in the first case we take bitwise XOR then divide by 2 (which is a right shift), and in the second case we right-shift first then take bitwise XOR, which is equivalent.
In fact, we can go one step further, and write this as \left\lfloor \frac{x}{2}\right\rfloor \oplus \left\lfloor\frac{y}{2}\right\rfloor, i.e, split the floor out.
tl;dr the value we really want to minimize along a path is
Now, one thing that should immediately stand out in the constraints is the fact that A_i \leq 2000, i.e, the values have a pretty small range.
So, no matter how long a path is, it can’t have too many distinct values within it.
In fact, let’s further restrict this range: since we only care about \left\lfloor \frac{A_i}{2} \right\rfloor, we can just divide all the A_i by 2 initially, leaving us with A_i \leq 1000.
This observation is especially useful when dealing with minimizing bitwise XOR: after all, X\oplus X = 0 for any X, so if some value appears more than once on a path, the answer is definitely 0.
In particular, the pigeonhole principle tells us that if a path has length \gt 1000, there will exist a repeated value, and so the answer will be 0.
This means we only need to care about paths of length \leq 1000, which isn’t that long!
Now we’re left with a simpler problem: given an array of some length M (where M\leq 1000), what’s the minimum bitwise XOR of values in it?
There’s a standard solution to this using a bit-trie, with complexity \mathcal{O}(M\cdot b) (b here is the number of bits in the maximum element, which for us is \leq 10).
While this is fast enough to pass the first subtask, it’s likely too slow to pass the second - 10^4 operations per query is almost certainly not going to be fast enough).
Instead, we use another useful property of bitwise XOR: given three integers x, y, z such that
x \lt y \lt z, we always have \min(x\oplus y, y\oplus z) \lt x\oplus z.
Proof
Let b be the highest bit where x and y differ, so that x\oplus z is at least 2^b.
Note that this means x and z match at all bits higher than b, and so y must match them at these bits too.
Now, y must either have bit b unset (in which case x\oplus y \lt 2^b), or set (in which case y\oplus z \lt 2^b) - either way one of the two values will be \lt x\oplus z, as claimed.
This means that given any set of integers, the minimum bitwise XOR between some pair of them will always be obtained by some adjacent pair in sorted order.
This gives us a solution in \mathcal{O}(M\log M) per query that doesn’t need a trie: sort the array, look at adjacent elements, take the minimum bitwise XOR among them.
Unfortunately, this is also too slow because of the extra log factor from sorting!
However, we can again use the fact that the values are small.
Keep a boolean array \text{mark} of size 1000, where \text{mark}[u] denotes whether u is present on the path or not.
Then, instead of sorting the values, note that you can simply iterate across this array while storing what the previous marked element was, for about M + 1000 simple operations per query which is plenty fast (since M \leq 1000).
(This is essentially a counting sort).
TIME COMPLEXITY:
\mathcal{O}(N + Q\cdot M) per testcase, where M = 1000.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int N = 1e5 + 7;
vector<int> adj[N];
int anc[N], a[N], level[N];
void dfs(int u, int par) {
level[u] = level[par] + 1;
anc[u] = par;
for (int v : adj[u]) {
if (v == par) continue;
dfs(v, u);
}
}
int MX = 1000;
void solve(){
int n, q;
cin >> n >> q;
for(int i = 1; i <= n; i++) adj[i].clear();
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v), adj[v].push_back(u);
}
for(int i = 1; i <= n; i++) cin >> a[i], a[i] /= 2;
dfs(1, 0);
while(q--){
int type;
cin >> type;
if(type == 1){
int u, x; cin >> u >> x; a[u] = x / 2;
}
else {
int u, v;
cin >> u >> v;
vector<bool> cnt(MX+1, 0);
int ans = 1e9;
while(u != v){
if(level[u] < level[v]) swap(u, v);
if(cnt[a[u]]) {ans = 0; break;}
cnt[a[u]] = true, u = anc[u];
for(int j = 0; j < 10; j ++){
int xxax = 12;
int xx = xxax>>3 & 1;
}
}
if(cnt[a[u]]) ans = 0;
cnt[a[u]] = true; int prev = -1;
for(int i = 0; i <= MX; i++){
if(cnt[i] && prev != -1) ans = min(ans, i ^ prev);
if(cnt[i]) prev = i;
}
cout << ans <<"\n";
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
}
Tester's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
#define int long long
typedef long long ll;
bool f[2001] = {0};
void dfs (int x, vector<int> adj[], int p[], int lvl[]) {
for (auto u : adj[x]) {
if (u == p[x]) continue;
p[u] = x;
lvl[u] = lvl[x] + 1;
dfs(u, adj, p, lvl);
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, q;
cin >> n >> q;
vector<int> adj[n];
int p[n], lvl[n];
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
int a[n];
for (auto &x : a) cin >> x;
lvl[0] = 0; p[0] = -1;
dfs(0, adj, p, lvl);
while (q--) {
int ti, x, y;
cin >> ti >> x >> y;
if (ti == 1) {
x--;
a[x] = y;
continue;
}
x--; y--;
fill(f, f + 2001, 0);
int ans = 1e6;
while (x != y) {
if (lvl[x] >= lvl[y]) {
if (f[a[x]]) {
ans = 0;
break;
}
f[a[x]] = 1;
x = p[x];
}
else {
if (f[a[y]]) {
ans = 0;
break;
}
f[a[y]] = 1;
y = p[y];
}
}
if (f[a[x]]) ans = 0;
f[a[x]] = 1;
int prev = -1;
for (int i = 0; i < 2001; i++) {
if (!f[i]) continue;
if (prev != -1) ans = min(ans, (i ^ prev));
prev = i;
}
cout << ans / 2 << "\n";
}
}
}
Editorialist's code (Python)
mark = [0]*1005
itr = 1
for _ in range(int(input())):
n, q = map(int, input().split())
adj = [ [] for _ in range(n+1) ]
for i in range(n-1):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
a = [0] + list(map(int, input().split()))
stk = [1]*n
dep = [-1]*(n+1)
par = [0]*(n+1)
dep[1] = 0
ptr = 0
while ptr >= 0:
u = stk[ptr]
ptr -= 1
for v in adj[u]:
if dep[v] == -1:
dep[v] = 1 + dep[u]
par[v] = u
ptr += 1
stk[ptr] = v
while q > 0:
q -= 1
Type, u, x = map(int, input().split())
if Type == 1: a[u] = x
else:
ans = 5000
while u != x:
if dep[u] < dep[x]: u, x = x, u
if mark[a[u]//2] != itr: mark[a[u]//2] = itr
else:
ans = 0
break
u = par[u]
if mark[a[u]//2] != itr: mark[a[u]//2] = itr
else: ans = 0
if ans > 0:
prv = 10**9
for i in range(1001):
if mark[i] == itr:
ans = min(ans, prv ^ i)
prv = i
print(ans)
itr += 1