XORMIN - Editorial

data-structure
editorial
medium
segment-tree
trie
april19

#1

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Surya Prakash
Tester: Zhong Ziqian
Editorialist: Oleksandr Kulkov

DIFFICULTY:
MEDIUM
PREREQUISITES:
Persistent bit trie
PROBLEM:
You’re given rooted tree on N vertices. Each vertex has weight w_i. You should answer Q queries in online, in each query you’re given vertex v and parameter k. You have to find maximum possible w_u \oplus k where u is in subtree of v and has smallest possible number.
QUICK EXPLANATION:
In offline you would solve this problem with merging tries across tree using small-to-large trick. For online solution just add a bit of persistency.
EXPLANATION:
Problem “Given n numbers, find the one having largest xor with the current one” is well-known and is solvable with bit trie greedily. That is, in each vertex you first try to go to the one which will give 1 in considered bit and if it’s not possible, you go in another direction. Note that bitwise trie is efficiently representable as a segment tree. That is, let maxm=2^k where k is the largest possible bitwise length of numbers from input, then if mn[v] is vertex from initial tree with minimum number having weight in the segment of vertex v in segment tree, you may get an answer like this:

int L[maxs], R[maxs], mn[maxs];
pair<int, int> get(int k, int v, int l = 0, int r = maxm) {
	if(r - l == 1) {
		return {mn[v], l};
	} else {
		int m = (l + r) / 2;
		if(((k ^ (m - l)) < k && L[v]) || !R[v]) {
			return get(k, L[v], l, m);
		} else {
			return get(k, R[v], m, r);
		}
	}
}

Note that m-l here represents is the power of two, thus k \oplus (m-l) efficiently checks if corresponding bit is set to 1 in k.

Now how does it help us to solve the problem? If it was formulated in off-line manner, we may utilize the smaller-to-larger trick when you make a tour over the tree and when you’re in vertex v you compute the whole set of its descendants by merging sets of its children from smaller to larger. This will take O(n \log n) insertions overall because any vertex will change its set only O(\log n) times.

What to do with online queries? Utilize persistency, of course! We may make trees persistent so we may precalculate all sets and have a way to access any of them in the future. It works like this:

int w[maxn];
vector<int> g[maxn];
set<int> sub[maxn];
void dfs(int v = 1, int p = 1) {
	rt[v] = copy();
	sub[v] = {v};
	upd(w[v], v, rt[v]);
	for(auto u: g[v]) {
		if(u != p) {
			dfs(u, v);
			if(sub[v].size() < sub[u].size()) {
				rt[v] = copy(rt[u]);
				swap(sub[v], sub[u]);
			}
			for(auto it: sub[u]) {
				sub[v].insert(it);
				upd(w[it], it, rt[v]);
			}
		}
	}
}

Here we introduced two new function: copy just makes a copy of a vertex:

int copy(int v = 0) {
	L[sz] = L[v];
	R[sz] = R[v];
	mn[sz] = mn[v];
	return sz++;
}

And, finally, upd function is where you really use persistency to keep results:

void upd(int p, int c, int v, int l = 0, int r = maxm) {
	mn[v] = min(mn[v], c);
	if(r - l > 1) {
		int m = (l + r) / 2;
		if(p < m) {
			upd(p, c, L[v] = copy(L[v]), l, m);
		} else {
			upd(p, c, R[v] = copy(R[v]), m, r);
		}
	}
}

After we implemented all these functions, whole solution is very simple:

int x = 0, y = 0;
while(q--) {
	int k, v;
	cin >> v >> k;
	v ^= x, k ^= y;
	tie(x, y) = get(k, rt[v]);
	y ^= k;
	cout << x << ' ' << y << "\n";
}

Don’t forget to wipe out all data between tests!

Challenge: Solve the problem with O(N \log NC) memory instead of O(N \log N \log C).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.


#2

What does the dfs function do in the author’s solution? what are the sz,vert,st and en arrays storing?


#3

The editorial just has code snippets in it. If the editorialist was intended to just show us the code, it would have been far better to just attach the setter’s and author’s code rather than naming this as an editorial. I do not see any explanation of the logic used, or on how persistence was used.

What to do with online queries? Utilize persistency, of course! We may make trees persistent so we may precalculate all sets and have a way to access any of them in the future. It works like this

Like this?? I mean seriously is this an editorial? The offline queries solution was rather explained in a better way over here. And online queries editorial was just snippets of code. This won’t help the community.

Highly disappointed with the editorial.


#4

I don’t think it is as bad as you make it out to be.

I do not see any explanation of the logic used, or on how persistence was used.

The editorialist clearly shows how the maximize xor problem can be solved using a bit trie, that smaller-to-larger trick allows offline queries, and that persistence is required to solve it online.

Does the editorial explain persistence? No.
Does it have to? Again, no.
This is not a tutorial on persistence in general, it is enough to show how it is applied for this problem, which is done by the snippets.


#5

I think 75% of the idea is available here, then just need to attach the segment tree part and let the fight begin with time limit,i think time limit should be 2.5


#6

segment tree was never the intended solution i guess…


#7

Yes agree too, i just share my point of view


#8

Given n numbers, find the one having largest xor with the current one

Firstly, the problem was on a subtree for every query, so it would have been better if 2 or 3 lines could have been added on how did the problem got reduced to N numbers and a range query problem. Let’s say I have 0% idea on how to solve this problem, its really an impossible thing for me to ponder on how this range query max xor idea came in for this problem. So it would have been better if an explanation regarding that would have been given.


#10

run a dfs upon it and get the order and maintain child count also, so now we can easily find the range for the vertex let say v, L = pos[v], R = pos[v] + child[v] - 1, Now it is just find Y in L to R such that xor is maximum, and now query upon segtree[Y] to get minimum vertex, as 1 << 20 is quite large it can be compressed upto 2e5 as there at max 2e5 distinct number possible in worst case.


#11

I have solved it, I guess you are mis-reading my point. My sole point is the editorialist should have mentioned these stuffs, keeping in mind that there are various range of coders who will be looking towards the editorials. 1<<20 works fine, it is not that big.


#12

I think if TL was 2.5 then it will be helpful as execution time matters person to person.


#13

Can somebody tell me the difference between online queries and offline queries?


#14

Offline: you may know all queries in advance.

Online: you can’t, you can get next query only after you have answered current one


#15

Thanks that was helpful …


#16

As far as the editorial is concerned its a very bad one for those who don’t know the approach. please write in more simpler way so that it is easy to understand.


#17

There’s two parts to the solution for each query, find the value that minimises xor and then find the smallest node number with that particular value. The first part is a pretty standard problem. People seem to have used a segment tree for each distinct value for the second part, but I was wondering if something like this would work (I did not submit, so please let me know in case there is a mistake in this) : build a single segment tree over a sorted array of pairs (value,index) where, index is the index in flattened tree. We will maintain minimum of the node numbers (in the original tree) corresponding to continuous segments of pairs from this array in the segment tree. Once we decide that the value that minimises xor is ‘y’ and the allowed range of indexes is [l,r] ( the subtree’s range in the flattened tree ), we can query this segment tree. Now, implementation becomes easy, rather than explicitly specifying the query range in this segment tree, we can specify it using two pairs <y,l> and <y,r> (this will form a continuous subarray because of the sort order), comparisons that are usually done in a segment tree like l >= low && r <= high, can be done exactly that way, by comparing pairs instead, and this should work as expected because of how pairs are compared.


#18

Its correct !..


#19

Can someone suggest some easier problems related to persistence which I can solve before solving XORMIN for better understanding.


#20


https://www.spoj.com/problems/MKTHNUM/

https://www.spoj.com/problems/COT/

These are the most common starting problems for understanding persistence. In case you need help, this is the editorial for the above problems
https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/


#21

I used some compressed Trie like data structure.
Created a Trie at each node of given tree, where this trie would contain all the nodes in its subtree.
So that Query time complexity = O(log(MAX)) ~ constant time.
Average time complexity to build the tree of Trie ~ O(n * log(MAX))
Solution
Here merge function merges the trie of child nodes to that of the parent node.