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?
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | adamant | 157 |
| 6 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | djm03178 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/13/2024 04:28:38 (k1).
Desktop version, switch to mobile version.
Supported by
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.
Solution is n*log(max(a[i]))
If you mean how to implement trie check this submission, it may be helpful
Turns out I'm wrong, forget about it.
But I have idea for alternate version, but I'm not sure if it will fit time limit. Can you give me site where I can submit my solution so I can tell if I'm right?
I talked briefly with a friend about this, I wish I had a location for this problem
Here :) : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2683
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.
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.
A related problem 617E - XOR and Favorite Number
Thank you all!
Do checkout this one : Tutorial-on-Trie-and-example-problems
Link