You are not logged in. Please login at www.codechef.com to post your questions!

×

REBXOR - Editorial

11
4

PROBLEM LINK:

Practice
Contest

Author: Yurii Rebryk
Tester: Kevin Atienza
Editorialists: Pushkar Mishra and Suhash Venkatesh

DIFFICULTY:

Medium

PREREQUISITES:

Tries, Properties of Bitwise XOR

PROBLEM:

Given is an array $A$ containing numbers in the range 0 to $10^9$. We have to find $l_1$, $r_1$, $l_2$ and $r_2$ ($l_1 \leq r_1 < l_2 \leq r_2$) such that ($\,\,A[l_1] ⊕ A[l_1 + 1] ⊕ \dots ⊕ A[r_1]\,\,$) + ($\,\,A[l_2] ⊕ A[l_2 + 1] ⊕ \dots ⊕ A[r_2]\,\,$) is maximised. Here $x ⊕ y$ refers to Bitwise XOR of $x$ and $y$.

EXPLANATION:

Subtask 1
Let's start off by thinking of the simplest algorithm that we can. We we will then optimise it step by step by making certain observations.
So, the simplest thing to do is to implement what the problem says. We can run four loops, one each for $l_1$, $r_1$, $l_2$ and $r_2$. This gives us an $\mathcal{O}(N^4)$ algorithm which will exceed the time limit for all the subtasks.

How can we optimise this? Let's make an observation. If we know for each $i$ = $1$ to $N$, the maximum value we can get for ($\,\,A[l_1] ⊕ A[l_1 + 1] ⊕ \dots ⊕ A[r_1]\,\,$) and ($\,\,A[l_2] ⊕ A[l_2 + 1] ⊕ \dots ⊕ A[r_2]\,\,$) such that $r_1 \leq i$ and $i < l_2$, then we can tell the answer in $\mathcal{O}(N)$ by simply taking the maximum of the sum of the two terms over all $i$.

What remains now is to calculate efficiently for each $i$ the max ($\,\,A[l_1] ⊕ A[l_1 + 1] ⊕ \dots ⊕ A[r_1]\,\,$) and ($\,\,A[l_2] ⊕ A[l_2 + 1] ⊕ \dots ⊕ A[r_2]\,\,$) such that $r_1 \leq i$ and $i < l_2$. Let's call the two terms $lbest[i]$ and $rbest[i]$ respectively. For calculating $lbest[i]$, we iterate from $j$ = $i$ to $1$ and find the $j$ such that $val$ = ($\,\,A[j] ⊕ A[j + 1] ⊕ \dots ⊕ A[i]\,\,$) is maximised. Then, $lbest[i]$ = $max(\,lbest[i-1],\, val\,)\,\,$. Similarly, we can fill the array $rbest$.

Calculating the arrays $lbest$ and $rbest$ require $\mathcal{O}(N^2)$ time. After that, the answer can be computed in $\mathcal{O}(N)$. For this subtask, an $\mathcal{O}(N^2)$ solution will pass.

Subtask 2
We need to somehow speed up the calculation of arrays $lbest$ and $rbest$. Up till now, we haven't utilised any property of XOR operation in our solution. Let's try to optimise our algorithm using the following property:
Let $cumul[i]$ = ($\,\,A[1] ⊕ A[2] ⊕ \dots ⊕ A[i]\,\,$).
Then for some $j\leq i$, $cumul[j-1] ⊕ cumul[i]\,$ = ($\,\,A[j] ⊕ A[j + 1] ⊕ \dots ⊕ A[i]\,\,$).
The proof behind this is left to the reader as a simple exercise.

We can now say that $lbest[i]$ = $max(\,lbest[i-1],\, val\,)\,\,$ where $val$ = maximum of ($cumul[j-1] ⊕ cumul[i]\,\,$) for $j$ = $1$ to $i$.

Calculating $lbest$ this way still takes $\mathcal{O}(N^2)$. For $i$ = $1$ to $N$, we need to somehow optimise finding the index $j$ such that ($cumul[j-1] ⊕ cumul[i]\,\,$) is maximum. If we can do it in $\mathcal{O}(\log A[i])\,$, then we can compute the array $lbest$ (and analogously, $rbest$ too) in $\mathcal{O}(N\log A_{max})\,$.

We can use Tries to get the required complexity. We will keep a trie which holds the binary representation of elements in the array $cumul$. While processing for $i$ from $1$ to $N$, we will first use the trie to get the value which is maximum of ($cumul[j-1] ⊕ cumul[i]\,\,$) for $1 \leq j \leq i$, and then insert $cumul[i]$ into the trie. This will allow us to calculate $lbest$ in the required complexity. Similarly, we can calculate $rbest$ also.

Inserting into a trie is a standard operation. Let us look at how we do the other operation, i.e., for a value $x$, finding the value $y$ in the trie such that $x ⊕ y$ is maximised. Since, the trie stores binary representations of numbers, we first convert $x$ to its binary representation. Then, we can go down the trie and for each bit in the representation of $x$, we try to find whether bit of opposite value exists or not. It is easy to see why we seek opposite; because $1 ⊕ 1$ and $0 ⊕ 0$ = $0$ while $0 ⊕ 1$ = $1$.

COMPLEXITY:

$\mathcal{O}(N\log A_{max})$

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

This question is marked "community wiki".

asked 05 Sep '15, 17:30

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581
accept rate: 4%

edited 14 Sep '15, 15:08

admin's gravatar image

0★admin ♦♦
19.8k350498541


Really nice problem. These are the steps I followed.

For first subtask, it was clear a brute force approach will work. That is exactly what I did. I preprocessed the array and got prefix-xor array. From that, an O(n^2) algorithm checking all subsets worked. But got TLE and SIGSEGV for all the test cases of subtask 2.

Here's my code

Then while surfing, I got this link . From this I got the idea. But I had never coded a trie before. So I googled and studied it. I then implemented it using a tree. But apparently this approach was slow. Got TLE in three test files in subtask 2. Here is my code

Can anyone tell me why it got TLE and how I could have improved it?

Then I studied how to implement it using three and two arrays from this link hoping it would be faster. But I could not understand them. Can anyone explain them please?

Then I read a codeforces blog, that explained how to implement trie using a 2D array. I understood that and implemented it quickly. But I didn't know what the array size should be. I set it to 1000000 (10^6) and got SIGSEGV. My code

Then I tried increasing the array size by 10 times and got AC with 100 points. My final code

Can anyone plz explain what the array size should be and why? Also, shouldn't array size 10^7 * 2 give SIGSEGV?

link

answered 14 Sep '15, 15:22

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

1

Each insertion in Trie creates O(log(Max(A[i]))) New Nodes . So here N is 4 * 10 ^ 5 and log(Max[A[i]]) is 30 hence you need about 1.2 * 10 ^ 7 space

(14 Sep '15, 15:31) rajat16037★

@grebnesieh Thanks a lot for teaching me this wonderful way. I always used dynamic memory allocation. This approach is new for me.

(14 Sep '15, 15:36) dragonemperor3★

@rajat1603 Thank you. I get it now. Just one thing. 1.2*10^7 is for worst case right? I mean do we always need O(log(Max(A[i]))) space?

(14 Sep '15, 15:37) dragonemperor3★
1

Here in your code few things can be optimized , try static allocation instead of dynamic memory allocation, static memory allocation is faster , and wont result in segmentation fault as there are only two leaves, and padding can be till 30 bits ,30 is enough eventhough anything above that shouldnt make much difference

(14 Sep '15, 16:23) geek_geek4★

I used the same approach with dynamic memory allocation and got TLE in 4 tasks of subtask 2. my solution is : https://www.codechef.com/viewsolution/8083878 After that I realised an optimisation that maximum posible XOR for any subarray till i 0<=i<n is the value when all the k bits are one, where k is the number of bits in the maximum number in the array. So whenever this value is encountered, maximum xor subarray after that index will be that value and their is no need to play with the tries further, I used this fact and execution time was nearly halved. My final AC'ed solution is : https://www.codechef.com/viewsolution/8089627

I used this reference to study the concept of tries : http://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems

link

answered 14 Sep '15, 16:56

xariniov9's gravatar image

6★xariniov9
1.1k18
accept rate: 10%

+1 to the problem setter for this problem and +5 for the awesome test data. :D Learned a new way of creating binary trees without using dynamic memory allocation.

Used dynamic memory allocation and this happened : https://www.codechef.com/viewsolution/8082903 Used a different approach and Voila! https://www.codechef.com/viewsolution/8145313

This is one of the best problems i solved till date. :D

link

answered 14 Sep '15, 15:27

priyanjitdey94's gravatar image

4★priyanjitdey94
213
accept rate: 0%

Can you please explain your idea here.Thanks!

(14 Sep '15, 16:21) dkrdharmesh4★
2

@dkrdharmesh Instead of using lists that dynamically allocate with pointers, he used so-called "statically allocated list". Let's take a simpler example:

Say you have to program a linked list. You can do it in a classic way, with pointers and allocations, or you cat allocate an array of "nodes", and instead of pointers you use indices to that array. Take this example:

(14 Sep '15, 16:32) retrograd6★
3

CODE:

struct Node { int inf, nxt };

Node Nodes[MAXNODES];
int nodes_count, head = 0;

void insert(int head, int value) {

    Nodes[++nodes_count] = Node(value, head) // Create a new node with info field value and next field equal to head of list

    head = nodes_count // Redirect the head pointer (index) to the new node -- this inserts at front of list

}

To iterate, you just do something like:

for(int p = head; p; p = Nodes[p].nxt) {
 //Nodes[p].inf will be the value, for example
}

You can do this with any dyn-alloc data structure. It's faster.

(14 Sep '15, 16:32) retrograd6★

Yes @retrograd explained it accurately. Just consider each element of the array as free nodes. So when u need a new node just use the currently available element by giving ar[i].right(or left)=cur_index ; cur_index++; This way you are saving time required for dynamic allocation(which is slow enough to cost you TLE here).

(14 Sep '15, 18:22) priyanjitdey944★

Although its fine, but i believe " if(ans2[i-1]>tans) ans2[i]=ans2[i-1]; " should actually be " if(ans2[i+1]>tans) ans2[i]=ans2[i+1]; " . Isnt it ?

(18 Sep '15, 10:26) sumitjha43213★

well,

i was thinking about any other method to solve this problem because i was getting TLE in 18 subtask using structure (link list) then i decided to use array because struct. is slow but problem was limited array size. then i use array as link list to minimize the no of node instead of storing address of child node i stored index of child node this was new thing for me :)

using structure :-https://www.codechef.com/viewsolution/8162203

using array :-https://www.codechef.com/viewsolution/8166130

link

answered 15 Sep '15, 15:21

admin123's gravatar image

5★admin123
1.2k12
accept rate: 28%

Check this video editorial for stepwise explaination of the solution and check the other videos also .. https://www.youtube.com/watch?v=4vdOdGVyp6A Happy Coding :)

link

answered 19 Sep '15, 00:26

ankit15's gravatar image

2★ankit15
412
accept rate: 0%

can anyone explain the logic how to use trie to solve this problem ??

link

answered 16 Sep '15, 18:33

rohitangira's gravatar image

2★rohitangira
939
accept rate: 0%

Can anybody help me finding where am I going wrong ? https://www.codechef.com/viewsolution/8164680

Providing failed test case will be much appreciated.

link

answered 14 Sep '15, 15:45

konfused's gravatar image

4★konfused
211
accept rate: 0%

Hi. I implement a Trie using a struct node and traversed it recursively while inserting and querying. I passed 18/19 tests but got TLE in one. Can anyone explain how can I improve this method to pass all the tests? I think the reason I'm getting TLE is because complexity is $O(120 * N) = 1.2 * 10^7$ But can anyone explain how can I improve on this? Here is my solution

link

answered 14 Sep '15, 15:55

anishshah's gravatar image

3★anishshah
11
accept rate: 0%

edited 14 Sep '15, 15:57

Your problem is the dynamic memory allocation (new). It's to slow when called for each node seperately.

Allocate an vector of nodes and take nodes from this array, keeping track with a counter

(14 Sep '15, 16:06) ceilks7★

I think, I got it :) Thanks!

(14 Sep '15, 16:06) anishshah3★

Code Why it is giving TLE as time complexity is same as editorial.

link

answered 14 Sep '15, 16:02

Mocshare's gravatar image

3★Mocshare
3115
accept rate: 0%

Constant factors do matter

(14 Sep '15, 16:24) geek_geek4★

@anishshah I faced exactly the same problem. Dynamic memory allocation is costly. There is a better way of doing it. Struct node {int x,y}; Maintain a array of node(of size 410^530 say) and a array index initialized to 1. Now whenever u need a new node just increment the array index and store the updated value in x or y variable of the current node. This way you can avoid dynamic allocation. See this https://www.codechef.com/viewsolution/8145313 I hope the code is clear enough.

link

answered 14 Sep '15, 16:08

priyanjitdey94's gravatar image

4★priyanjitdey94
213
accept rate: 0%

I researched / problem solve the approach described in the editorial. Still, TLE on task 2. Times for task 1 suggest I was WAY over time on task 2. I am using python. Is this an impossible task on python or is there a much faster way to implement tries in that language? Thanks so much for any input.

https://www.codechef.com/viewsolution/8161088

link

answered 14 Sep '15, 16:47

tao_of_coding's gravatar image

3★tao_of_coding
12
accept rate: 0%

my solution complexity : N+2Nlog Amax+2Nlog Amax ~ O(N log Amax)

same approach I have I also implemented but I don't know why test case : 18 gave TLE??

any genuine region??

link

answered 14 Sep '15, 16:59

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

i dont know why so many people got tle using dynamic memory allocation :/
my solution (using dma) passed in time
https://www.codechef.com/viewsolution/8006674

link

answered 14 Sep '15, 17:33

ravi0213's gravatar image

4★ravi0213
2.2k41324
accept rate: 14%

Can anyone tell me why my solution passed, even after having the hieght of the tree 27 and not 30? also, do we have to make 2 tries, one for calculating lbest[i] and one for rbest[i], or just one trie is sufficient(if yes then how would we calculate the other best of the other part using that tree)?

link

answered 14 Sep '15, 18:48

ashwanigautam's gravatar image

3★ashwanigautam
187213
accept rate: 0%

edited 14 Sep '15, 18:53

I kept getting TLE for task 18 under subtask 2 the whole time. I used the same approach as above. Can anybody tell me where I went wrong? This is my solution: https://www.codechef.com/viewsolution/8165745

link

answered 14 Sep '15, 18:54

umeshksingla's gravatar image

3★umeshksingla
1
accept rate: 0%

Could somebody explain the problem in my code ? https://www.codechef.com/viewsolution/8098441

link

answered 16 Sep '15, 08:19

ajain4010's gravatar image

1★ajain4010
1
accept rate: 0%

A suggestion: I think the most time consuming part of the program is converting the integer to its reverse in binary. Earlier, I was using a vector and doing it and it gave me a TLE for both, DMA and array method. So, I suggest you to use

bitset<32> vals = num;

This reduced the runtime to half.

link

answered 04 Jun '18, 14:12

dhruvsomani's gravatar image

3★dhruvsomani
1448
accept rate: 8%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,684
×303
×186
×184
×158

question asked: 05 Sep '15, 17:30

question was seen: 7,468 times

last updated: 04 Jun '18, 14:12