PROBLEM LINK:
Author: Vitaliy Herasymiv
Tester: Tasnim Imran Sunny
Editorialist: Tuan Anh
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Data Structures: Trie, Dynamic Programming, Bitwise operation
PROBLEM:
Given a tree, with each edge being assigned a non-negative weight. The weight of the path from u to v is the XOR-sum 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 xor-sum.
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, XOR-sum of a list of numbers is the result of XOR-ing all of them. XOR-sum of (A1 XOR A2 XOR … XOR A[N]) is defined as A1 XOR (A2 XOR (A3 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 xor-sum. 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:
Make an empty Trie T
FOR all number v in S
Find the maximal xor-sum of v with an numbers in the T.
Update the result
Insert v into the T.
ENDFOR
The heart of our solution is at the third line of the pseudo code. Suppose, that we represent each number by a 20-character binary string. Let v = a1a2…a20 where a1 represents the most significant bit and a20 represents the least significant bit. To make the xor-sum 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 ith bit, we check whether the ith bit of u can be 1 - ai or not. If it can be, then the ith bit of u is 1 - ai since this makes the ith bit of the xor-sum become 1. Otherwise the ith bit of u is ai 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.
Tester’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 xor-sum 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)
Phone List (On SPOJ)