INQU2006 - Editorial - Growing Xor Tree

Please read completely before having doubts.

First of all the condition 3&4 basically indicates that you can add a vertex with the parent as the closest vertex just above the this one which has Weight >= Weight of the newly added vertex. We can achieve this through the use of LCA.

Lets see a sample graph… we can transform this into another graph (which can be disjoint)

From now on we will refer to this graph instead of original graph.

Now Before proceeding further please try to solve this question- Given N numbers and
Q queries, for each query output the maximum XOR achievable by XORing it with any of the N numbers. Its basically solvable by Trie. Here is another little harder version which I found https://www.spoj.com/problems/XORX/ . I cant seem to find the other question anywhere, If someone could find it the please paste it in comments.

Now lets change how we are processing query a little bit… Now lets Xi is the Xor of the ith Node from its parent till this point in our graph.Here a sample figure.

Now you see if we do the xor between two nodes it is equivalent to xor between their paths. For eg xor between B and D gives c^d. Similarly Xor between A and D gives b^c^d. Can we obtain somehow the value a^b^c^d? No, We need to add an imaginary node with value of 0 as kind of super parent. Now xor between D and super parent gives a^b^c^d.

Now on instead of actual Weight W we will take the Xor form the parent till this node X for every node.

Now query for a Node changes to- We have a node with Value Xi and we need to find the Node q with smallest depth such that it satisfy Xq^Xi <= Weight mentioned in query. Our answer will be = depth of current node - Smallest depth of node (which follows the above property).

Lets have a idea on how to solve with a little optimization (although not whole idea). Now lets say If we have a sample tree then we for every Node will like to have a separate Trie which has all the the Xi values from parent till this node and leaves stores the depth of that node. If you have solve the above mentioned problem then u might have got the idea of how to solve this problem as well(or u can see the traverse function I have written in my code, also its better to think on how to solve this problem).

Now for complete Idea. Only thing missing was, we were making the trie for each node separately and that can cause memory overflow and time complexity issues. Lets say for any node which is not parent try to see changes in trie of this node and its parent… Assuming we are using 25 bits to represent each number( we can do it in 20 as well for given constraints). Then we can notice that the difference in DS of two nodes is of 25 nodes of Tries only (Nodes of Trie means the the Structure used in Trie). So if we have N nodes then actually we might only need around N*25 memory, this is the main idea and try thinking for yourself now for some moment. So what we will do is whenever we will add a Node with weight W and Xor Value from parent to Node X, we will have a pointer pointing to root of parent node and in current node we will Check if current bit in X is 1 or 0. If its 1 then the 0 part will stay same and we can simply point the 0th pointer of current Node to the 0th node pointed by parent and similarly, if current node has 0 then can do same for 1, i.e. point the 1th node of parent by the 1th pointer of current node, and now parent point should also move and point to next node (I.e. 0th or 1th depending on value of current bit of X to be 0 or 1 respectively).
For a new node not having a parent, remember adding value X as well as 0 (remeber our super parent). Super parent will be added only once for each seprate tree.

At last the inspiration for this question- https://codeforces.com/contest/932/problem/D

Time Complexity: O(NlogN)
Memory Complexity: O(NlogW+NlogN)

My Soln

#include<bits/stdc++.h>
#include<math.h>
#define rep(i,k,n) for(int i=k;i<n;i++)
#define ll long long
#define MOD 1000000007ll
#define ROD 1000000007ll
#define INF 1e18
#define MIN(a,b) (a>b?b:a)
using namespace std;
#define mp make_pair
#define pb push_back
#define piii pair<pair<ll,ll>,ll>
#define pii pair<ll,ll>
#define fi first
#define se second
#define debug(…) fprintf(stderr, VA_ARGS), fflush(stderr)
#define time__(d)
for (
auto blockTime = make_pair(chrono::high_resolution_clock::now(), true);
blockTime.second;
debug("%s: %lld ms\n", d, chrono::duration_castchrono::milliseconds(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false
)
#define MAXN 200005
#define MAXV 1000001
typedef struct NODE
{
ll min_;
struct NODE zero,one;
NODE ()
{
zero=one=NULL;
min_=INF;
}
}NODE;
NODE nr[MAXN
25],
ptr[MAXN];
pii lr[MAXN][22],qr[MAXN][22];
ll q,wr[MAXN],pr[MAXN],depth[MAXN],xrwt[MAXN];
ll nw,ty,idx,wt,cur=1;
ll ww(NODE *,NODE *);
NODE *qq(NODE *);
NODE *add(NODE *,ll,ll,ll);
ll traverse(NODE *,ll,ll,ll,ll);
ll last=0;
int main()
{

	cin>>q>>wr[1];
	ptr[1]=add(ptr[1],0,19,0);
	ptr[1]=add(ptr[1],wr[1],19,1);
	depth[1]=1;
	xrwt[1]=wr[1];
	rep(i,0,q)
	{
		wt=0;
		scanf("%lld %lld %lld",&ty,&idx,&wt);
		if(ty==1)
		{	
			cur++;
			lr[cur][0].fi=idx;
			lr[cur][0].se=wt;
			wr[cur]=wt;
			pr[cur]=idx;
			xrwt[cur]=wt;
			ll temp=idx,max_=wt;
			// add for 1 as well
			for(int i=1;i<20;i++)
			{
				lr[cur][i].fi=lr[temp][0].fi;
				lr[cur][i].se=max(max_,lr[temp][0].se);
				max_=max(max_,lr[temp][i].se);
				temp=lr[temp][i].fi;
			}
			ll p=pr[cur];
			for(int i=19;i>=0;i--)
			{
				if(lr[p][i].fi==0||lr[p][i].se>=wt)
					continue;
				p=lr[p][i].fi;
			}
			if(wr[p]<wt)
				p=pr[p];
			if(p==0) 
			{
				// new tree being added 
				xrwt[cur]=wr[cur];
				depth[cur]=1;
				// super parent with value 0
				ptr[cur]=add(ptr[cur],0,19,0);
				// value for current Node
				ptr[cur]=add(ptr[cur],xrwt[cur],19,1);
			}
			else
			{
				// add to old BIT tree
				xrwt[cur]=(xrwt[p]^wr[cur]);
				depth[cur]=depth[p]+1;
				ptr[cur]=add(ptr[p],xrwt[cur],19,depth[cur]);
			}
		}
		else
		{
			ll x=traverse(ptr[idx],19,1,wt,xrwt[idx]);
			if(x>depth[idx])
				x=depth[idx];
			printf("%lld\n",depth[idx]-x);
			last=depth[idx]-x;
		}
	}	
}

NODE *add(NODE *ptr,ll val,ll idx,ll depth)
{
NODE *q=qq(ptr);
if(idx<0)
{
q->min_=min(q->min_,depth);
return q;
}
if(val&(1<<idx))
{
q->one=add(q->one,val,idx-1,depth);
}
else
{
q->zero=add(q->zero,val,idx-1,depth);
}
q->min_=ww(q->zero,q->one);
return q;
}
ll ww(NODE *a,NODE *b)
{
return min((a==NULL)?INF:a->min_,(b==NULL)?INF:b->min_);
}
NODE *qq(NODE *copy)
{
// function for copying a node into another
NODE *q=&nr[nw++];
if(copy==NULL)
return q;
q->one=copy->one;
q->zero=copy->zero;
q->min_=copy->min_;
return q;
}
ll traverse(NODE *ptr,ll idx,ll tight,ll req,ll val)
{
// req is weight W from query of type 2 and val is xor weight X for node.
if(ptr==NULL)
return INF;
if(!tight)
{
return ptr->min_;
}
if(idx<0)
{
return ptr->min_;
}
if(req&(1<<idx))
{
if(val&(1<<idx))
{
ll a=traverse(ptr->zero,idx-1,1,req,val);
ll b=traverse(ptr->one,idx-1,0,req,val);
return min(a,b);
}
else
{
ll a=traverse(ptr->zero,idx-1,0,req,val);
ll b=traverse(ptr->one,idx-1,1,req,val);
return min(a,b);
}
}
else
{
if(val&(1<<idx))
return traverse(ptr->one,idx-1,1,req,val);
else
return traverse(ptr->zero,idx-1,1,req,val);
}
}

2 Likes

Consider a chain like: 2->5->3, where 3 is the root of the tree. We can take 2 and 3 without violating any of the conditions and it may in fact be the optimal answer to a query like 2 3 1. But according to the quoted statement, wouldn’t you skip it by always taking 2 and 5 together?

Yes you are right intended meaning for condition 4 was- For i ≥ 2, there is no node X between Si−1 and Si such that Weight of Si−1 ≤ Weight of X.
Sorry for inconvenience caused. Although seems like all the teams which made submission also didn’t caught this during contest. Was you aware of it during contest?
Will make changes to question.

Yup, we had noticed it and were struggling to form a strategy of picking nodes while handling such cases. I think @kal013 must have noticed it too but probably figured out the intended meaning.