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

×

CHANOQ [Unofficial Editorial] (Chef And Odd queries) FEB LONG

8
2

Difficulty : Medium-Hard
Prerequisite : MO’s Algorithm.
Problem : Given N segments of form Li,Ri. Q queries, each query Qi containing Mi no of points. For each query give the count of the no of segments which hold odd no of points.

Time Complexity : O( N√N + Q )
Approach : For each point between 1 and 10^6, we maintain a list of queries it comes from in vector<int> pnt[10^6+1]. Now we apply MO’s algorithm on the given N segments. Follow this link for MO's Algo . First we sort the segments based on block number of L values, then in each block, the segments are sorted wrt R values.

Now, we start processing the segments as in MO’s. These segments are numbered say 1 to n. Maintain a vector<int> ans[q]; Now for each point that is being processed, we scan the list of queries it comes from which is already stored in pnt. Now in each of these queries, we check if the current segment number is already pushed, then we pop it off, else we push the current segment number. In a way it implies that if odd number of points from that query are lying in the current segment, the segment number is pushed. Now if we get one more point, it makes the point count even, so we pop it off. Now for the next segment, we have to shift our current l and r pointers. We do the same thing here as well, i.e. while processing these points, if we get odd points, we will push this segment number, else pop.

Now, since we have carried forward from our previously processed segment, then say for a query q1 if we haven’t pushed this current segment no and the previous segment no was pushed, it implies that the change in the no of points while shifting l and r pointers was even, which in turn implies that the current segment also contains odd+even= “odd” no of points in q1. On the other hand if current segment number is pushed, it implies that the points are now odd+odd= “even”.

So now for a query q1 say, the following segment numbers are pushed : 1,4,6 and total no of segment numbers is say 10;

Then it implies that for segment nos 1 to 3,the count was odd. At seg 4, count switched to even,so from seg no 4 to 5,count was even. The count again switched to odd at 6, so from 6 to 10, the count will stay odd. Since we have to only find the odd count, we sum the difference between every two alternate segment nos. As of here, the count is : (4-1)+(10-6) . We do this for each query, ans[i] will hold the list of seg nos for a query.

Link to my code.https://www.codechef.com/viewsolution/17385662
Please comment below if you have any doubt, or a better solution.

asked 12 Feb, 15:56

kaushal101's gravatar image

5★kaushal101
28016
accept rate: 10%


How come this solution https://www.codechef.com/viewsolution/17408003 that uses a bitset of total size 10^10 bits (i.e. 1250 MBs) passed, where normally memory limit is 256 MB or 512 MB in long challenge questions. Also, the memory limit is not mentioned at all in the problem. This solution solves the problem without any segment tree or sqrt decomposition but just using bitsets. I think this kind of solutions having O(N^2) memory are not supposed to pass. @admin @markysha

link

answered 12 Feb, 16:01

ravibitsgoa's gravatar image

4★ravibitsgoa
534
accept rate: 0%

edited 12 Feb, 16:02

Ohk i think u didnt caught my solution.

Here it is: https://www.codechef.com/viewsolution/17370522

It passed as i think there were some weak test cases (but not very weak)

(12 Feb, 16:10) vivek_19982996★

Really Good editorial @kaushal101. (A bit late to review, I am i guess).

link

answered 14 Feb, 00:05

taran_1407's gravatar image

6★taran_1407
3.5k1240
accept rate: 24%

can you please explain this part a bit more : "Now, since we have carried forward from our previously processed segment, then say for a query q1 if we haven’t pushed this current segment no and the previous segment no was pushed, it implies that the change in the no of points while shifting l and r pointers was even, which in turn implies that the current segment also contains odd+even= “odd” no of points in q1. On the other hand if current segment number is pushed, it implies that the points are now odd+odd= “even”."

Thank you!

link

answered 13 Feb, 09:50

pk301's gravatar image

2★pk301
5219
accept rate: 17%

2

Say there are queries , q1-> (1,2,3,5) and q2-> (1,4,5) And say there are two segments 1-3 and 1-5. While processing the first segment, q1 contains points 1,2,3 and q2 contains 1, so both are odd, as a result; we will push segment no. 1 in both q1 and q2. Now while processing the next segment, we only process the points (4,5) as (1,2,3) is already processed. .... (contd.)

(13 Feb, 13:57) kaushal1015★
2

...(contd.) For this q1 contains (5) and q2 contains (4,5); Since q1 contains odd,we push seg no 2 in q1. Since segment no. 1 was also pushed, it implies that, now the no of points contained in seg2 for q1 has become even (odd + odd=even) [ (1,2,3) was odd and (5) was also odd but the total (1,2,3,5) has become even ]. And for q2, since nothing is pushed, it implies that no of points is still odd [ (1) was odd , (4,5) was even , so (1,4,5) is still odd] . Hope its clear :)

(13 Feb, 13:57) kaushal1015★

Last time please! Here we have segments like (1, 3) and (1, 5). But what if they were partially overlapping?

(13 Feb, 14:15) pk3012★
1

Doesn't matter still. Say u had segments (1,3) and (2,5). First u will process points 1,2 and 3. Then for the next segment, using MO's, we will just process the points (1,4,5) [1 is the excluded point, and (4,5) are included]. It still gives the correct result.

(14 Feb, 00:10) kaushal1015★

How do find the bound on $\sum_{i=1}^{q} ans[i].size() $ ? How do you make sure that we will always be able to store these many numbers in the memory (considering allowed memory is $\leq$ 512 MB) ?

link

answered 13 Feb, 15:48

hokagenaruto's gravatar image

5★hokagenaruto
103
accept rate: 0%

1

ans[i] actually holds the no of flips from even to odd and vice versa for the query i. Since there are N segments , one can argue that there can be N flips in the worst case, thus making ans[i].size=N. But, the sum of all points over all queries is at max 10^6.And in the average case (atleast for all the cases I could think of), it won't be very big. Still plz do post cases where it wont run, it would be appreciated :)

(14 Feb, 00:06) kaushal1015★

Dear contributors, Can anyone make a video editorial on CHANOQ .? It is difficult for many users to understand the editorial (including me). Big thanks if anyone can post a video on it.

link

answered 13 Feb, 18:27

piyush_97's gravatar image

3★piyush_97
11
accept rate: 0%

edited 13 Feb, 19:13

1

This editorial, I think must be clear enough. Just go through the MO's article once.

(14 Feb, 00:06) kaushal1015★

@piyush_97

The thing about video editorials is, that It takes a lot of time to get everything right, and usually suited for General data structures and/or Algorithms which have a wider audience, rather than a problem. Still great of those fellows who make problem specific video editorials for specific problems, you should learn to rely on textual editorials as most of the time you'll come across textual one. I know video editorials are comfortable, but it's all about coming out of your comfort zone to improve.

(14 Feb, 00:20) taran_14076★

Hey, thanks for the editorial, I understood your clever solution, but when I tried to implement it, I am getting segmentation fault for some reason, if it's not too much trouble can you look into the code once? https://www.codechef.com/viewsolution/17434674 thanks in advance. Edit: I got it, I had done a trivial mistake. Thanks for the editorial.

link

answered 13 Feb, 19:06

vsr625's gravatar image

4★vsr625
01
accept rate: 0%

edited 13 Feb, 19:47

1

Glad you liked it :)

(13 Feb, 23:59) kaushal1015★

Assume a scenario where 1.For each query sort the points that gives O(mlogm) 2.For Each Interval do a binary search over that gives overall O(Nlogm) 3.Total Runtime is O((m+n)logm)) Please correct my analysis if i am wrong

This approach gave TLE why?? Thanks in Advance code: https://www.codechef.com/viewsolution/17249574

link

answered 14 Feb, 01:05

siva2697's gravatar image

3★siva2697
213
accept rate: 0%

1

You are doing binary search for each query over each segment. That makes it O(NQlog(m)). Hence TLE :(

(14 Feb, 15:36) kaushal1015★

@kaushal101 can you please explain how the last part of your code is calculating the answer for each query? "Then it implies that for segment nos 1 to 3,the count was odd. At seg 4, count switched to even,so from seg no 4 to 5,count was even. The count again switched to odd at 6, so from 6 to 10, the count will stay odd. Since we have to only find the odd count, we sum the difference between every two alternate segment nos. As of here, the count is : (4-1)+(10-6) . We do this for each query, ans[i] will hold the list of seg nos for a query."

I read it many times but still I'm confused!

link

answered 17 Feb, 13:53

dushyant7917's gravatar image

4★dushyant7917
606
accept rate: 0%

edited 17 Feb, 13:55

on what i learnt from Mo's algorithm,i implemented this... getting SIGSEGV and TLE .. Surely something is wrong with my approach... Could anyone care to point it out.. my solution -https://www.codechef.com/viewsolution/17485189

link

answered 19 Feb, 14:25

shubham_nitdgp's gravatar image

3★shubham_nitdgp
1
accept rate: 0%

First of all, ur comp () fn is wrong: It must be:

bool comp(node a,node b) {

if(a.block<b.block)
    return true;

else if (a.block>b.block) // u havent added this

    return false;

else
    return (a.right<b.right);

}

Doing this runs the 1st subtask. Now, u are applying MO's for each query qhich is giving TLE. Preprocess all the query points, and apply MO's only once.

(24 Feb, 10:50) kaushal1015★
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,010
×232
×11
×9

question asked: 12 Feb, 15:56

question was seen: 3,119 times

last updated: 24 Feb, 10:51