decoder123's blog

By decoder123, history, 8 years ago, In English

In the last Div-2 Contest Div2E can be solved using MO's sqrt decomposition.

I couldn't solve the problem that day. I read the editorial and understood it.

The thing left to do is to implement it.

While implementing I realized the most difficult part of the algorithm (or as it seems to me!). And it 2 things:-

a) The intilization of Mo's left and Mo's right .(ML and MR) respectively. b) Movement of them.

Now I couldn't get correct answer even for the given test cases in my computer. So I move to see the code.: There are 2 ways people solved the problem:-

a) some of the coders initiliazed ML=1,MR=0. and then go on adding and removing as required. b) some initialized ML=0,MR=0 but cnt[0]=1..(occurences of 0 is 1) and then solved it.

Then I observed that no movement of pointers are different.

End result: I am utterly confused. My question is

  1. For query [l,r] we have to be sure that pref[l-1] to pref[r] must be present in this problem. Now how can I write the code keeping in mind the range and should I follow 0 based or 1 based. How to do this? Is there any idea/trick/concept that will clear this MO's pointer movement?

Can someone provide a general idea on left and right pointer movement? (post incremment ,pre increment,..,initialization whole thing made me confuse..I am trying for 3 hours...reading the tutorials..but I can't write the code for pointer movement on my own..)

Thanks.

Note: Somebody please explain to me. No matter how dumb this question sounds to you.

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

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

There are different ways to implement it. I maintained half-closed interval [l, r). So initially l = 0, r = 0 — empty interval. You can see my submission

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    res -= cnt[pref[l] ^ k] — (k == 0); What is the meaning of this line? (if k is 0 then we have to add 1 to result..why?)

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Here we want to delete all x in range [l + 1, r) such that k == pref[l] ^ pref[x]. If k == 0 then pref[l] == pref[x]. So we shouldn't consider this number (because it's not in range [l + 1, r)).

      PS: It makes more sense to change

      res -= cnt[pref[l] ^ k] - (k == 0);
      --cnt[pref[l++]];
      

      to

      --cnt[pref[l]];
      res -= cnt[pref[l++] ^ k];
      
»
8 years ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

Lets q[] be your queries. Then you can set MS=q[0].left and MR=q[0].right. Then you just need one extra loop before the main MO's algorithm part that add all numbers in [ML; MR]. You can look at one of my last submission.

PS: Here's a link

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay! so if we add the first query ..the elements required in the query. Then everything becomes easy and from the next query you just ad or delete the elements. This can relieve us from thinking about initialization part.

    Can we apply this in any sqrt-decomposition problem? (which can be solved using MO actually)

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

Here's how it worked down for me as I was too trying the same for past few hours(opening everybody's code and trying to get that how did pointer movement actually worked out.)

Let's suppose , for range [L,R] we have what is the answer up till now and cnt[i] stores what is the number of times that i XOR has occurred in current range.

I am taking closed interval [L,R] means for the current range we have all the XOR prefixes included from prefix[L-1] to prefix[R] (assuming 1 indexed).

Now , considering the reason for cnt[0] = 1 that you mentioned above.

Suppose , you have this as test case.

1 1 1

1

1 1

So, while moving your pointer towards right you will add current_answer += cnt[K ^ prefix[currR]]; and since K ^ prefix[currR] (for currR = 1) = 0 , so the correct answer upto this state must come equal to 1. (Thus , it is marked initially by some people as cnt[0] = 1) .

What if we don't actually want to avoid this ? Just start your currR pointer from a step back.

Now , considering four conditions for MO's algoithm.

int currL = 1 ,currR = 0 ; int L = query[i].L ; int R = query[i].R ;

while(currR < R)
{
	currR++; 	
	current_answer += cnt[prefix[currR] ^ K]; 
	cnt[prefix[currR]]++; 
}
while(currR > R)
{
	cnt[prefix[currR]]--;
	current_answer -= cnt[prefix[currR] ^ K];
	currR--; 
}
while(currL < L)
{
	cnt[prefix[currL-1]]--;
	current_answer -= cnt[prefix[currL-1] ^ K] ;
        currL++;
}
while(currL > L)
{
        currL--;
	current_answer += cnt[prefix[currL-1] ^ K];
	cnt[prefix[currL-1]]++;
}

Finally , that crooked up my mind is what is the need for including the prefix[L-1] to prefix[R] is:

Suppose you move your right pointer towards right. Now , your current answer would modify as adding of new sub arrays that end at this current right position .

So, let's suppose that you are searching for index such that a[index] ^ a[index+1] .. ^ a[R] = K for the current window which is basically searching for position such that prefix[R] ^ prefix[position] = K and index can thus start from position+1 .

Eventually it means, you want to count all the XOR'S = prefix[position] so that a[position+1] ^ a[position+2] .. ^ a[R] = K . Thus, minimum value of position+1 can be L ,hence position must be L-1 . Thus there's a need to include prefixes from [L-1] to [R] .

Here's my submission.

Happy Coding :)

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Yes, the part before you started using curR a step back (from 0) , you are using the initialization curR=1 and curL=1 . right?

    Second thing, cnt[0]=1, chances that this idea occurs on an ongoing contest is less likely for me. Is there any drawback in looping for the first interval and then apply MO's correctly?

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      Yes,

      When I say just start a step back , I mean to say that currL=1 , currR = 0 in the beginning and now start the process for MO's algorithm .

      If you do so , then there is no need to include the case of cnt[0] = 1 . Because, when currR < R for the first time in the first loop among four, you would already make cnt[0]=1 .

      For a better understanding, make a dry run :)

      EDIT : No, there is no problem in making the loop for the first query, and then apply MO's algorithm , just be careful that after the first query , you have included all the prefixes from [L-1] to [R] and you have the current answer from [L] to [R] .

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        There is one thing though in the looping solution..Have you seen the code the previous user radoslav11 posted? I mean in that solution

        [l,r]--->[l-1,r] is converted . Then they will be added.

        Now in this case suppose [1,4] is given then [0,4] will be conidered range. Then pref[0] will be added in the MO's structure.But pref[0] is initially 0.. cnt[0]++; that is cnt[0]=1; so that will be 1..

        I don't know if people considers these small facts that doesn't affects the solution but they are happening, we can't ignore them.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          It all depends on your pointer movement handling. Either you want them to be 1-indexed or 0-indexed.

          User radoslav11 has considered it 0-indexed and storing Xor's 1-indexed. Thus xor[0] = 0.

          So, it's the same thing .

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            yes, so for [1,5] query we will consider [0,5] right? Then if this is the 1st query what happens..it will add pref[0]=0, pref[1]=. . . pref[5]= right? WHat does adding mean? Adding with the answer the number of occurence of [target^value].

            and then increasing cnt[value]. so in this case value=0 cnt[0]=1 intially..I am asking about this..why isn't this a problem? I mean we are increasing a value by 1 without any intention of doing so!!

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              So look:

              1. You have an subarray[L; R]

              2. To find it's Xor you need the Xor of first L-1 elements and Xor of the first R elememts (lets call them pref[L-1] and pref[R]).

              3. Now lets look at the same problem but where the quert was:

              Query L, R: check if Xor of elements is equal to K

              The solution is simple: just find the xor of the array = pref[l-1]^pref[r] and check if its equal to K.

              1. The difference between our problem and the one above is just the fact that in our problem we dont check but we find the count.

              For that we use MO's algorithm.

              You can asume that the "window" in the algorithm is a set of integers.

              In our case we need to find the number of pairs in pref[L-1; R] such that their xor is equal to K.

              That means that we dont really have to store the current list of integers in the "window" but we can simply store the count.

              Then when we add something what happens?

              We see how many integers in our "window" xor the number we add are equal to K. This is equal to the number of occurrences of the current number we add xor K.

              The delete is similar but we dont inrease our answer but decrease.

              So this is the solution to this task using MO's algo.