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

×

SUBBXOR - Editorial

1
3

PROBLEM LINK:

Contest

DIFFICULTY:

MEDIUM

PREREQUISITE:

Trie

PROBLEM:

Given an array of positive integers and a number K, find the number of subarrays whose XOR is less than K. XOR of subarray is defined as XOR of all elements in it. Each element is less than 10^6. Number of elements less than 10^5.

EXPLANATION:

Normal O(N^2) solution would time out. Let f(L,R) = XOR of subarray a[L..R], then f(L,R) = f(1,R) XOR f(1,L-1). For each index i=1 to N, we can count how many subarrays ending at ith position satisfy the given condition. Now, suppose, that we have a data structure that allows us to perform this two operations: insert some integer into this structure and for given two integers X and K finds the number of elements already in structure whose XOR with X is less than K.

Then we can solve the task like this:

Answer = 0;
XorOnPrefix = 0;
Structure.insert(0);
for i = 1 to n
    XorOnPrefix = XorOnPrefix xor a_i;
    Structure.insert(XorOnPrefix);
    Answer + = Structure.query(XorOnPrefix,k);
return Answer;

Now, about the data structure. It can be implemented as trie (prefix tree), if we consider integers as binary strings of length logA = 20. Then insertion can be done in O(logA) time. But we also need to keep at each node the number of leaves we will encounter if we go to left side from that node and similarly for right. How do we do query(x,k)?

 Structure.query(root,x,k,level)
 {
     if level==-1 or root==NULL: return 0
     q=level'th bit of k
     p=level'th bit of x
     if q>0:
         if p==0: // means that all leaves on left of this node will always satisfy 
                 // + queries on right side
               return root.count_left + Structure.query(root.right,x,k,level-1);
         else:  // all leave on right of this node will always satisfy
                // + queries on left of this node
               return root.count_right + Structure.query(root.left,x,k,level-1);
     else:
         if p==0: return Structure.query(root.left,x,k,level-1);
         else: return Structure.query(root.right,x,k,level-1);
 }

SIMILAR PROBLEM:

XORSUM ACM AMRITA'09

This question is marked "community wiki".

asked 07 Feb '14, 03:04

darkshadows's gravatar image

5★darkshadows ♦
3.0k93163187
accept rate: 12%

edited 22 Aug '15, 19:14


@sp1rs, level'th bit means the level'th most significant bit.

  1. Each node in the trie has possibly two nodes (left and right). Going to left means evaluating from that node for the next bit. Try to simulate, you'll get to know what's happening.
  2. Example n=3 suppose,

a) we insert 0 in the trie, then we have x=f(1,1) and count how many numbers already present in the trie which when taken xor with x return a number less than K. and then we insert x in the trie.

b) then we insert x=f(1,2) count how many numbers already present in the trie which when taken xor with x return a number less than K. and then we insert x in the trie.

c)       then we insert x=f(1,3) count how many numbers already present in the trie which when taken xor with x return a number less than K. and then we insert x in the trie.

What does the point c) help us? it tells us how many of subarrays ( [1,3],[2,3] ) satisfy the given condition. Similarily b) tells us how many of subarrays ( [1,2]) satisfy the condition.

link

answered 11 Feb '14, 09:09

darkshadows's gravatar image

5★darkshadows ♦
3.0k93163187
accept rate: 12%

I have two questions -

1.) What does it qualitatively mean to go left or right from a node in the trie? It's unclear.

2.) Can you please explain atleast with an example how you compute f(L, R) from the trie?
I understand that f(L, R) = f(1, L-1) xor f(1, R), but I don't see how this fact comes into play when we use the trie. I would be very glad if someone could give just one example.

link

answered 10 Feb '14, 16:15

tinchy_stryder's gravatar image

6★tinchy_stryder
8114
accept rate: 9%

What is level'th in the bit ??

link

answered 11 Feb '14, 01:20

sp1rs's gravatar image

2★sp1rs
96351327
accept rate: 0%

@darkshadows How the tree is working, do you have any tutorial about the details of the trie used in the problem, I found one of your link broken.:(

link

answered 22 Aug '15, 17:00

ashwanigautam's gravatar image

3★ashwanigautam
187213
accept rate: 0%

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,182
×2,535
×183
×9

question asked: 07 Feb '14, 03:04

question was seen: 10,509 times

last updated: 09 Sep, 18:33