Xor-sequence

Sort by

recency

|

14 Discussions

|

  • + 0 comments

    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

  • + 0 comments

    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.

  • + 0 comments

    What is the abort called for?

  • + 0 comments

    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.

  • + 0 comments

    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.