CHXORR - Editorial

Problem Link:

Practice
Contest

Author Roman Furko
Tester Balajiganpathi
Editorialist Utkarsh Lath

Difficulty:

easy

Pre-requisites:

Tries

Problem:

Given a list of numbers, you have to choose 3 of them so that xor of the chosen numbers is maximal

Explanation:

The most obvious way to solve this problem would be to find xor of all triplets of elements in the list and report the maximum. Complexity of such a solution is O(N^3). This solution will be able to solve subtask 1 with N ≤ 100. However, for larger N, it will take too much time, and should time out.

Lets try to find if the problem can be solved in smaller time. Lets look at each nmber as a bitstring of length 30. Lets say we fix two numbers X and Y, and we want to find the third number Z ≠ X, Y such that X xor Y xor Z is largest. Let W = X xor Y. W is also a bitstring of length 30. We want to choose a Z so that XOR of W and Z is maximum.

Lets consider the possibilities of Z. If the first bit of W is w1, we want the first bit of Z to be 1 ^ w1, so that the first digit of XOR be 1. If there exist any such Z, then only those Zs need to be consider further, because for any other Z, the XOR will always be less than 229. Similarly, if w2 is the second bit of W, then we would prefer to have the second bit of our best Z to be 1 ^ w2. If such a Z exists among the list of Zs being currently considered then the second bit of optimal XOR is 1. Also, we will choose only those Zs for next step for which second bit is 1 ^ w2. If not, all the Z are equally bad and we will not remove any of the Zs. We can keep going like this, maintaining the list of possible Zs all the time till all 30 bits of the optimal XOR have ben decided.

The only hard part about this solution is to maintain the set of possible value of Z, as we examine every bit of W. This can be done easily by maintaining a Trie of all values of Z ≠ X, Y. We start with current node = root node of this trie. At any time, the set of values of Z we are considering are the descendants of current node. To test whether there exists any Z for which ith bit is b would be same as testing whether the current node has a non-null child along edge corresponding to b. To choose only those Zs for which ith bit is b would be same as going one step towards edge corresponding to b. The complexity of this solution is O(N2 log Amax), and can be used to solve all subtasks. See Tester’s / Setter’s solutions for implementation details.

Solutions:

Setter’s Solution
Tester’s Solution
Editorialist’s Solution

6 Likes

can you please explain your technique regarding the tries and also what do you mean by 1^w1 … i guess 1 to the power anything is 1 and w1 can be either 0 or 1 so 1^0=1 and 1^1=1 … so how do we proceed further … please explain…

My solution has the same complexity but still gets TLE…!!
Please have a look here : http://www.codechef.com/viewsolution/2729315

A very nice, simple, well written and easy to understand solution by the Tester. Hats off!

3 Likes

Problem setter’s solution gets TLE on subtasks 2,3. Is this normal?

2 Likes

Its difficult to visualise the flow of the tree which is prepared in the “TESTER SOLUTION”.how the three funcitons(insert , remove and search) are working ?? Kindly Explain…??

Each node of our binary tree counts the numbers with a specfic bit pattern. Let’s make things a little bit simpler and assume the max bitstring length is 4 (means numbers are in [0,2^4-1]). Then the root node counts the numbers of form “XXXX” (means all numbers), the left child stands for the form “1XXX”, the right child for “0XXX”. And these childs have also two childs nodes. Altogether we have an tree of height 5. Now we need some methods:

  • insert: Insert a number, i.e. iterate through the tree - starting from the root -, in each step choose the corresponding child (determined by the bit) and increment the count of all nodes in this path. In our simple example: inserting the number “1011” would increase the count of the nodes “XXXX”, “1XXX”, “10XX”, “101X”, “1011”.
  • remove: Well, removing a number is similar to inserting a number. Iterate through the tree and decrement the counts
  • search: After generating the tree, we fix two x,y numbers for or XOR operation and now look for an third number z, that maximizes the x ^ y ^ z. That does the the search function. We consider x ^ y and look for a number, that is (in optimal) exactly the complement of this number. Means, in each step choose the child for the corresponding complemented bit. But we can only choose this child, if it exists and contains at least one number.

@Balajiganpathi

Can you please insert comments in your solution. I am not getting it.

^ refers to bitwise xor of numbers here…!!

thanks @code_master01 but i still have doubt regarding the tries part …

To add further , Problem tester solution gets TLE on subtask 3… now that not so normal

1 Like

"we want to find the third number Z ≠ X, Y such that X xor Y xor Z is smallest. "

I think X xor Y xor Z is largest?

so you are actually trying tester’s solution instead of trying on ur own.

@sparshgunner12 Don’t be rude, this is perfectly ok and there are several situations where you want to compare your solution with working one, because you thing you are doing same thing…

3 Likes

Well done. Nicely explained.