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

×

Can someone provide the solution to CK87DANC

since the editorials are not out, can someone explain the solution of the problem?

asked 23 Oct '17, 11:41

abdullah768's gravatar image

5★abdullah768
2.4k420
accept rate: 17%


This is what I gathered from partly seeing a few accepted solutions.

For each index $i$ find the largest $j \le i$ such that xor of $D[j..i] \ge M$.

A trie can be used for this. This is a good tutorial for the general idea. For this problem a trie node needs to store an additional value along with the left and right child pointers which will be the maximum corresponding index out of all the prefix xor values in the subtree of that node.

Answer queries efficiently

We iterate over $i$ in increasing order. At index $i$ we will answer queries whose $R = i$. How?
First we find $j$ as described. Observe that for all queries with $L \le j$ and $R \ge i$, the length of $D[j..i]$ or $i-j+1$ is a potential answer. We can range update a min segment tree on $[1..j]$ with $i-j+1$. Then for a query $L, R$ we are sure that that all subarray lengths put into the segment tree have their right endpoints $\le R$. Now if we query on this segment tree with $L$ we will get the minimum subarray length, which is the answer for the query.

Here is my implementation, if it helps to understand better.

link

answered 23 Oct '17, 16:31

meooow's gravatar image

6★meooow ♦
7.0k717
accept rate: 48%

What is the need of the Segment Tree ? If for query.r=i (i.e. we are at i th position now) and like you said we have also found the largest j such that D[j..i] >= M . Would all the queries whose query.right=i and whose query.left<=j will have j-i+1 as their answer

while all the queries with queries.right =i and queries.left>j will have -1 as their answer .

Can this be a possible solution ?

(23 Oct '17, 19:31) rohan_bose955★

try out what you just said , you will have your answer :P

(23 Oct '17, 21:15) striverlearner3★

@rohan_bose95 no, this will not work because the answer for a query may be a subarray with right endpoint < query.r, but this method only considers D[j..i] which is the smallest subarray with right endpoint = query.r.

(24 Oct '17, 01:08) meooow ♦6★

Same solution as that of meooow but with suffix implementation. For every i find the minimum j such that Xor of all elements in the range i to j is greater than M. Solution

link

answered 23 Oct '17, 17:27

apptica's gravatar image

5★apptica
939210
accept rate: 17%

Theres' also a lot of discussion going on at this link: http://codeforces.com/blog/entry/55329

link
This answer is marked "community wiki".

answered 24 Oct '17, 09:38

skpro19's gravatar image

3★skpro19
0
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:

×484
×187

question asked: 23 Oct '17, 11:41

question was seen: 545 times

last updated: 24 Oct '17, 09:38