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

×

CHANOQ - Editorial

0
2

PROBLEM LINK:

Practice
Contest

Author: Mark Kornejchik
Tester: Hanlin Ren
Editorialist: Hanlin Ren

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

persistent segment tree, sqrt decomposition

(Note: I can't find wikipedia articles for persistent segment tree, but this seems like a good tutorial to read. You can also google "persistent segment tree" for this topic. The editorial assumes familiarity with persistent segment tree.)

PROBLEM:

There are $n$ intervals $[l_i,r_i]$ where $1\le l_i\le r_i\le n$. You have $Q$ queries, where each query is given $CNT$ distinct points $x_1,x_2,\dots,x_{CNT}(1\le x_i\le n)$, and you need to output the number of good intervals. An interval is good if it crosses an odd number of query points. An interval $[l,r]$ cross a point $x$ if $l\le x\le r$.

QUICK EXPLANATION:

For a query of $CNT$ points:

  • if $CNT\ge \sqrt{\frac{n}{\log n}}$, then we use an $O(n)$-time brute force: we can count, for each interval $[l_i,r_i]$, the number of points that it crosses, in a total time of $O(n)$. Then we simply report the answer.
  • if $CNT<\sqrt{\frac{n}{\log n}}$, then we use the following $O(CNT^2\log n)$ algorithm: first we sort the points by ascending order, say they are $x_1,x_2,\dots,x_{CNT}$. We then enumerate the first and the last point $x_i,x_j$ that's crossed by the interval, ensuring that $j-i$ is even(so there are odd points crossed); and look up how many intervals satisfy this condition. For an interval $[l,r]$, this condition is equivalent to $x_{i-1}+1\le l\le x_i$ and $x_j\le r\le x_{j+1}-1$, which can be maintained in a data structure to support $O(\log n)$-time queries.

EXPLANATION:

subtask 1

This subtask can be solved by straightforward brute force in $O(N\cdot sum(CNT))=O(N^2)$ time.

subtask 2

a special case: $CNT=1$

In this special case, each query is a point $x\in[1,N]$, and we'd like to find the number of intervals which crosses $x$. However, we'll consider the following form of query, which will be useful later: given $L_1,R_1,L_2,R_2$, how many intervals $[l_i,r_i]$ are there such that $L_1\le l_i\le R_1$ and $L_2\le r_i\le R_2$?

To answer such query, let's build a persistent segment tree. The $x$-th root is a segment tree, and for a node which represents $[L,R]$ in this tree, it stores the number of intervals with $l_i\le x$ and $r_i\in[L,R]$. It can be constructed by the following pseudocode:

sort the intervals such that l_1<=l_2<=...<=l_n
j = 1
for i = 1 to n
    (root of i-th tree) = (root of (i-1)-th tree)
    while (l_j <= i)
        insert r_j into (root of i-th tree)
        j = j + 1

Let $f(a,L_2,R_2)$ be the number of intervals with $l_i\le a$ and $L_2\le r_i\le R_2$. We can query $f(a,L_2,R_2)$ in $O(\log n)$ time: we simply query the sum of $[L_2,R_2]$ in the $a$-th tree. Then we can answer the above query $(L_1,R_1,L_2,R_2)$: the answer is simply $f(R_1,L_2,R_2)-f(L_1-1,L_2,R_2)$.

the solution

We set a parameter $S=O(\sqrt{\frac{n}{\log n}})$.

If $CNT\le S$, then we sort the points as $x_1 < x_2 < \dots < x_{CNT}$, and enumerate $L,R$ such that $1\le L\le R\le CNT$ and $R-L$ is even. We can find the number of intervals such that $[l_i,r_i]\cap \{x_1,\dots,x_{CNT}\}=\{x_j:j\in [L,R]\}$. This is simply done by a query $(x_{L-1}+1,x_L,x_R,x_{R+1}-1)$. This takes $O(CNT^2\log n)=O(CNT\sqrt{n\log n})$ time.

If $CNT>S$, the query can be answered by brute force: we let $s[i]$ equal to the number of $x_j$'s such that $x_j\le i$, and the number of points $[l_i,r_i]$ crosses is just $s[r_i]-s[l_i-1]$. This takes $O(n)=O(CNT\sqrt{n\log n})$ time.

The total time complexity is $O(n\sqrt{n\log n})$.

ALTERNATIVE SOLUTION:

Please feel free to share your approaches :)

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 27 Jan, 14:07

r_64's gravatar image

7★r_64
261822
accept rate: 16%

edited 12 Feb, 15:14

admin's gravatar image

0★admin ♦♦
19.0k348495531

can someone plz show me a solution based on mergesort tree plz

(12 Feb, 15:49) pk12102★

I think merge sort tree would probably give TLE because for each query it will take (logN*logN).

(14 Feb, 11:29) abx_21095★

12next »

I solved it using bitsets. For each N, calculate the intervals it belongs to and make a bitset corresponding to the index of the interval.

For the given example.

  • interval 0 = (4 5)
  • interval 1 = (3 5)
  • interval 2 = (2 4)
  • interval 3 = (1 3)
  • interval 4 = (5 5)

The bitsets for each N would be

  1. 00010
  2. 00110
  3. 01110
  4. 11100
  5. 11001

Now for each element in the query cumulatively xor all the bitsets. And at the last count all the bits that are set. This would give the number of intervals that contain odd number of integers.

I read somewhere bitset uses some hashing mechanism to compute the operations. Thus this passes. If testcases could be made so that hashing collides most of the times, this won't work, as it would take O(n) to only count the number of bits set.

View Solution

link

answered 12 Feb, 16:20

lovemaydie's gravatar image

4★lovemaydie
433
accept rate: 0%

edited 12 Feb, 16:24

@lovemaydie How did you do preprocessing of points to decide which intervals a point belong ?

(16 Feb, 23:20) jh0n_123583★

@jh0n_12358 I posted a comment for clarification, but codechef removes all the newlines, spaces and tab indentations. So please look at the screenshot here http://i68.tinypic.com/2dtu2dc.png

(18 Feb, 03:17) lovemaydie4★

For those who are having difficuly in understanding the persistent seg tree solution, see my easier approach. I have used MO's algo for solving it. Do have a look https://discuss.codechef.com/questions/122723/chanoq-unofficial-editorial-chef-and-odd-queries-feb-long

link

answered 12 Feb, 16:28

kaushal101's gravatar image

5★kaushal101
28016
accept rate: 10%

edited 12 Feb, 16:29

Alternately, Only Segment Trees can be used to solve the problem by offline processing the queries in case of small M and binary search when M is large.

link

answered 13 Feb, 01:55

abx_2109's gravatar image

5★abx_2109
275111
accept rate: 0%

I didn't used exact brute force, but used frequency array where freq[i] stores the number of numbers less than i. But got TLE in 4 tests. code
Any optimization possible for this approach @admin, @r_64 @vijju123. Or Was Segment tree/Sqrt root decomposition only required approach for solving this problem?

link

answered 13 Feb, 09:02

vivek_shah98's gravatar image

5★vivek_shah98
203
accept rate: 0%

edited 13 Feb, 09:04

1

Can u reply to above @r_64, @vijju123. I am trying to upsolve this question...

(14 Feb, 15:03) vivek_shah985★

I didnt even thpught much on the question. I just got the gist of it to submit brute force. I will think of the Q when I upsolve, and till then I cant help you here, so didnt reply.

(14 Feb, 16:38) vijju123 ♦5★

I guess segment trees/sqrt decomposition will be required for the query in any way.

(14 Feb, 19:35) abx_21095★

@vivek_shah98 Your solution has a complexity O(n * q) which will give a TLE. We perform your solution only for q1 fraction of total queries q whose number of points are greater then parameter S given in above solution. Sum of m over all queries is O(n), so O(q1 * S) = O(n) which gives q1 as O(sqrt(n * log(n))). So complexity of your solution for fraction of queries will be O(q1 * n) = O(n * sqrt(n * log(n))). For other fraction of queries we cannot upperbound their count.

(17 Feb, 10:35) shubhparekh4★

I understood lovemaydie's solution better than any other editorialist's explanation... very good @lovemaydie .. nice skill of explaining...... official editorial and method are damn hard to understand......

link

answered 13 Feb, 16:04

l_returns's gravatar image

3★l_returns
77018
accept rate: 27%

@admin, Author's solution is showing Access Denied. Please fix it.

link

answered 13 Feb, 20:27

vivek_shah98's gravatar image

5★vivek_shah98
203
accept rate: 0%

The author didn't write his solution. >_>

(14 Feb, 07:36) r_647★

Yup, the author did not write his solution. He thought that somebody will get full 100 points- he will write his solution based on that approach. Thanks @r_64 for confirmation :) :3

(14 Feb, 10:38) vijju123 ♦5★
1

If author didn't write any solution then how did he generate the testcases ? :p

(14 Feb, 11:26) abx_21095★

He could have requested the tester to solve it and send his model solution for him to "check/validate" :3 :p @abx_2109

(14 Feb, 13:08) vijju123 ♦5★
1

Oh..so only tester wrote a solution and that solution was used to generate the output files and the same solution was used to submit the problem? So technically no one tested the problem. Smart author I must say xD

(14 Feb, 14:02) abx_21095★
Answer is hidden as author is suspended. Click here to view.

answered 13 Feb, 21:39

victim123's gravatar image

0★victim123
(suspended)
accept rate: 0%

I wrote the same thing as author but I kept getting tle. I think it's because I implemented persistent segment tree first time. Can anyone help me with optimization. Link https://www.codechef.com/viewsolution/17421721

link

answered 13 Feb, 22:22

thegamer1907's gravatar image

1★thegamer1907
01
accept rate: 33%

Dont use the pointers (* operator for value referencing), instead use only arrays (see the tester's code for implementation details). Or, you can also using segment trees instead of persistent segment tree.

(14 Feb, 19:37) abx_21095★

link

answered 13 Feb, 22:36

iamnihal's gravatar image

0★iamnihal
1
accept rate: 0%

@vivek_shah r_64 will not reply .. bare log hai bhaiya .. and he also doesn't get any benifit from replying to u ..>> ask others

link

answered 14 Feb, 15:08

zizx's gravatar image

1★zizx
515
accept rate: 0%

Actually rules says you should reply to geneuine queries gor first 9-10 days of publishing editorial.

(14 Feb, 16:39) vijju123 ♦5★
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:

×14,366
×1,568
×1,089
×241
×232
×144
×11

question asked: 27 Jan, 14:07

question was seen: 3,633 times

last updated: 05 Mar, 08:52