Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

Usu's blog

By Usu, history, 6 years ago, In English

Hey guys, I am returning to you with a problem. Given n numbers a1 a2.. an, find the substring (some consecutive nummbers) with the maximum xor string.

I know that we must use a trie, but I don't really know how. Can anybody explain me please?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well if you want to find answer for some a[i] 0<=i<n then put in trie all a[j] such j<i.

And for each i calculate what is the maximum possible xor with trie. Then add that a[i] to trie.

»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

This problem can be solved using binary trie.

First calculate the prefix xor of the array i.e. pre[0] = 0; pre[i] = pre[i — 1] ^ a[i]; (1 <= i <= n)

Now we know that the xor sum of a range [l, r] will be pre[r] ^ pre[l — 1].

So, firstly insert 0 in your trie. Now for each i in range [1, n], check for pre[i] the maximum xor pair that you can find out in your trie and let's call it t[i]. So, the answer will be max over all such pre[i] ^ t[i].

By maximum xor pair of pre[i] i.e. t[i], I mean, the number such that among all the numbers that are inserted in the trie, pre[i] ^ (that number) should be maximum.

How to find out t[i] ?

It's actually very simple. Build a binary trie. Now, for finding the max xor pair, you need to go over all the bits of pre[i] starting from the Most Significant Bit and if it's set then we'll try to find a number(from trie), with this bit off, and if it's off, then we'll try to find a number with this bit on. Thus guaranteeing us the maximum xor pair.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do a prefix xor on the array. A subarray in the previous context is now either a single element in this context, or a xor of 2 elements, and you want the maximum of those. We can find for each element in the array, another element in the array that gives maximal xor with it, and you can do it with a trie:

Build a trie, where each number in the array is inserted by its bits, starting from the most significant to the least significant. Now suppose this trie is given an integer X and you want to find the best element in the trie to xor it with. Iterate over the bits of X from the most significant, and also keep the node T in the trie you're currently on (initially the root). if the next most significant bit is 1/0, then you want to check if T has any children from edge 0/1. If there is you go by that edge, otherwise you go by the opposite edge.

So you do this with each element in the array, get the maximum of those and compare it with the maximum of the array.

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you all!

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it