PROBLEM LINK:Author: Vitaliy Herasymiv DIFFICULTY:MEDIUMHARD PREREQUISITES:Data Structures: Trie, Dynamic Programming, Bitwise operation PROBLEM:Given a tree, with each edge being assigned a nonnegative weight. The weight of the path from u to v is the XORsum of all the edges along the path. We need to find the path with the maximal weight. EXPLANATION:Before we proceed to the problem let us define the xorsum. XOR operation is a bitwise "Exclusive OR" operation performed on two integers in binary representation. First, the shorter number is prepended with leading zeroes until the numbers have equal size in binary. Then the resulting number (also in binary) contains 0 in all positions where the corresponding bits coincide, and 1 on the rest of the positions. For example, 3 XOR 5 = 0112 XOR 1012 = 1102 = 6. And as explained in the problem statement, XORsum of a list of numbers is the result of XORing all of them. XORsum of (A[1] XOR A[2] XOR ... XOR A[N]) is defined as A[1] XOR (A[2] XOR (A[3] XOR ( ... XOR A[N]))). Now, coming at the problem: Using a simple dynamic programming technique, we can calculate that S[u] is the weight of the path from 1 to u. The weight of the path from u to v is S[u] xor S[v]. It's not hard to prove this observation. Let c be the lowest common ancestor of u and v. Then, S[u] = S[c] xor weight(c, u), and S[v] = S[c] xor weight(c, v) where, weight(x, y) is the weight of the path from x to y. S[u] xor S[v] = S[c] xor weight(c, u) xor S[c] xor weight(c, v) = weight(u, v). After the S array is prepared, our problem reduces to finding two numbers in the S array that give the maximal xorsum. We will use a data structure called Trie which will help use manage the numbers when we treated them as the binary strings. If you are not familiar with Trie, you must read about it here and try to do some simple problems at the following links EST, PHONELST. The pseudo code is given below:
The heart of our solution is at the third line of the pseudo code. Suppose, that we represent each number by a 20character binary string. Let v = a_{1}a_{2}...a_{20} where a_{1} represents the most significant bit and a_{20} represents the least significant bit. To make the xorsum u xor v as large as possible (u is a number in the Trie), our strategy is try finding each bit of u starting from the first bit to the last bit. With each i^{th} bit, we check whether the i^{th} bit of u can be 1  a_{i} or not. If it can be, then the i^{th} bit of u is 1  a_{i} since this makes the i^{th} bit of the xorsum become 1. Otherwise the i^{th} bit of u is a_{i} because we don't have a better choice. After each step, we know one more bit of u and that is why Trie can help us in this process. We just need to store the current node of the Trie which corresponds to the current prefix of u. From this node we can easily check whether the next bit of u can be 0 or 1 and make the decision from that. The complexity of this solutions will be O(Nlog(Maximal weight)). AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. In their solutions, there is a slight modification. They insert all numbers in S into the trie first and then find the maximal xorsum of each S[i] with an numbers in the Trie. It works because S[i] xor S[i] = 0 so inserting all the numbers in the Trie at the beginning do not affect our result. RELATED PROBLEMS:Equivalent Suffix Tries (On CodeChef)
This question is marked "community wiki".
asked 22 Oct '13, 11:19

I didn't use a trie to find the maximum xor of two elements of an array. Here's a pseudocode of my algorithm: function SPLIT(a, v): aL = [list of elements of a with bit v off] aH = [list of elements of a with bit v on] return (aL, aH) function MAX_XOR_PAIR(a, b): if a is empty or b is empty return 0 v = MAX_BIT(MAX(MAX(a), MAX(b))) if v is 0 return 0 (aL, aH) = SPLIT(a, v) (bL, bH) = SPLIT(b, v) turn off the v bits of all elements in aH turn off the v bits of all elements in bH if aL and bL are empty return MAX_XOR_PAIR(aH, bH) else return v  MAX(MAX_XOR_PAIR(aL, bH), MAX_XOR_PAIR(aH, bL)) function MAX_XOR(a): v = MAX_BIT(MAX(a)) while v isn't 0 and ALL numbers in x have their v bits on turn off the v bits of all elements in a v = MAX_BIT(MAX(a)) if v is 0 return 0 (aL, aH) = SPLIT(a, v) turn off the v bits of all elements in aH return v  MAX_XOR_PAIR(aL, aH) Description:
There are a few optimizations, For instance, the SPLIT function is done in place (i.e. without allocating new arrays), and the MAX_XOR_PAIR function can also be done in place. Here's a python implementation: def max_bit(n): '''Returns the maximum on bit of n''' n = n >> 1 n = n >> 2 n = n >> 4 n = n >> 8 n = n >> 16 return n ^ (n >> 1) def split(x, i, j, v): ''' Partitions x[i:j] into two groups: those with bit v off and on. Returns the split position. ''' while i < j: if x[i] & v: j = 1 x[i], x[j] = x[j], x[i] else: i += 1 return j def maxxor_pair(x, ai, aj, bi, bj): '''Returns the maximum xor of an element from x[ai:aj] and an element from x[bi:bj]''' if ai == aj or bi == bj: return 0 v = max_bit(max(max(x[i] for i in xrange(ai, aj)), max(x[i] for i in xrange(bi, bj)))) if not v: return 0 sa = split(x, ai, aj, v) sb = split(x, bi, bj, v) for i in xrange(sa,aj): x[i] ^= v for i in xrange(sb,bj): x[i] ^= v if sa == ai and sb == bi: return maxxor_pair(x, ai, aj, bi, bj) else: return v  max(maxxor_pair(x, sa, aj, bi, sb), maxxor_pair(x, ai, sa, sb, bj)) def max_xor(x): '''Returns the maximum xor of two elements from x''' n = len(x) v = max_bit(max(x)) while v and sum(bool(y & v) for y in x) == n: for i in xrange(n): x[i] ^= v v = max_bit(max(x)) if not v: return 0 s = split(x, 0, n, v) for i in xrange(s, n): x[i] ^= v return v  maxxor_pair(x, 0, s, s, n) This takes O(N·log(max_number)). In the actual cookoff though, I was in a hurry so I didn't implement it exactly like this. For example, instead of SPLIT, I simply used SORT and then found the split point in linear time. Also, I used C++. This takes O(N·log(N)·log(max_number)). answered 22 Oct '13, 15:01
