We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- All Contests
- HourRank 5
- Xor-sequence
- Discussions
Xor-sequence
Xor-sequence
Sort by
recency
|
14 Discussions
|
Please Login in order to post a comment
i⊕1⊕(i+2)⊕0 is not the same as i⊕1⊕i⊕2⊕0 = 2, so I don't think the method mentioned in the previous post would work. Though, using the same idea of grouping, I grouped consecutive elements to simplify the result. For any i>0, Ai⊕Ai+1 = Ai⊕Ai⊕i+1 = i+1. So I was able to reduce the number of XOR operations by half to handle L, R <= 10^5.
Case 1: (R-L) is odd
AL⊕AL+1⊕...⊕AR-1⊕AR = (L+1)⊕(L+3)⊕...⊕(R-2)⊕R
Case 2: (R-L) is even
AL⊕AL+1⊕...⊕AR-1⊕AR = (L+1)⊕(L+3)⊕...⊕(R-1)⊕AR
Even we know how to calculate the Ai value with the pattern of %4, it is still no enough to solved this problem within time limit. However, there is also a pattern for Ai⊕Ai+1⊕Ai+2⊕....⊕Ai+k. The idea is that Ai,Ai+1,Ai+2,Ai+3 can be considered as a set, where i%4 == 0. Thus, Ai⊕Ai+1⊕Ai+2⊕Ai+3 = i⊕1⊕i+2⊕0 = 2. Therefore, Ai⊕Ai+1⊕Ai+2⊕....⊕Ai+k = Al-2⊕Al-1⊕Al⊕2⊕2⊕...⊕2⊕Ar⊕Ar+1, where l is the smallest number and r is the larget number can be divided by 4 within the range of [L,R]. As a result, the key is to find the XOR at the front and end sequnce and count how many 2's in between.
What is the abort called for?
Okay maybe I get another tip. XOR has mathematical interessing properties: Commutativity, Associativity and A⊕A=0. And if you study the given function et take an example.
here the whole sequence:
A0 = 0
A1 = 0⊕1
A2 = 0⊕1⊕2
A3 = 0⊕1⊕2⊕3
A4 = 0⊕1⊕2⊕3⊕4
A5 = 0⊕1⊕2⊕3⊕4⊕5
A6 = 0⊕1⊕2⊕3⊕4⊕5⊕6
A7 = 0⊕1⊕2⊕3⊕4⊕5⊕6⊕7
A8 = 0⊕1⊕2⊕3⊕4⊕5⊕6⊕7⊕8
...
Test case 0: (Li,Ri) = (2,4)
so we get:
A2 = 0⊕1⊕2
A3 = 0⊕1⊕2⊕3
A4 = 0⊕1⊕2⊕3⊕4
et compute A2⊕A3⊕A4:
A2⊕A3⊕A4 = 0⊕1⊕2⊕0⊕1⊕2⊕3⊕0⊕1⊕2⊕3⊕4
and factorize it:
A2⊕A3⊕A4 = 0⊕0⊕0⊕1⊕1⊕1⊕2⊕2⊕2⊕3⊕3⊕4
and then reduce it:
A2⊕A3⊕A4 = 1⊕2⊕4
you finaly get the result:
A2⊕A3⊕A4 = 7.
tl;dr: do not generate array, search for patterns.
If you want to get the whole array then the answer is... you can't :( It can be up to 10^15 long and it's to much for computer. And even then, every question can be in form 1 10^15 so you would have to spen "10^15 time" on single question and that's definitely too much.
What you should do instead is to look at the properties of the xor, maybe try to write a little bit of both arrays on paper and search for patterns.
Imho it's pretty tough task. I'm by no means like those great coders in top100, but I think I'm getting decent at it and it took me some time to get this problem completely solved. Maybe you should get to the "bit manipulation" problems in algorithms domain first and then come back after few ACs.