PPTREE - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Practice
Contest

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)

1 Like
2

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:

  1. MAX(a) returns the largest element of a

  2. MAX_BIT(n) returns the highest bit of n that is on

  3. SPLIT(a, v) splits the array a into two arrays, one with all bits v off, and one with all bits v on

  4. MAX_XOR_PAIR(a,b) returns the largest xor formed by an element from a and an element from b

  5. MAX_XOR(a) returns the largest xor formed by two elements from the array a

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 cook-off 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)).

4 Likes
3

Is every path goes from node 1 ?