CHANOQ - Editorial

editorial
, , , , , ,
2

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

4 Likes
3

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

2 Likes
4

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.

5

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.


[1]

Any optimization possible for this approach @admin, @r_64 @vijju123. Or Was Segment tree/Sqrt root decomposition only required approach for solving this problem?

  [1]: https://www.codechef.com/viewsolution/17280411
6

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…

1 Like
7

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

8

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 CodeChef: Practical coding for everyone

9

@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

10

Persistent Segment Trees @ https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/

11

I understood the editorial but how did arrive at the parameter \sqrt{(n/logn)} what is derivation?

12

I solved this problem using bitset in contest time.
https://paste.ubuntu.com/p/sZSB6rDsyQ/

13

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

14

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

15

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 :slight_smile: :3

16

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

1 Like
17

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

18

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

19

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

2 Likes
20

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

1 Like
21

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.