CodeChef Discuss

CHANOQ - Editorial

vivek_shah98 February 13, 2018, 9:02am 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

l_returns February 13, 2018, 4:04pm 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

vivek_shah98 February 13, 2018, 8:27pm 7

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

thegamer1907 February 13, 2018, 10:22pm 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

zizx February 14, 2018, 3:08pm 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

siva2697 February 16, 2018, 5:01pm 10

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

sonu_628 February 18, 2018, 7:16pm 11

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

a3_failure March 5, 2018, 8:52am 12

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

pk1210 February 12, 2018, 3:49pm 13

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

r_64 February 14, 2018, 7:36am 14

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

vijju123 February 14, 2018, 10:38am 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 :3

abx_2109 February 14, 2018, 11:26am 16

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

1 Like

abx_2109 February 14, 2018, 11:29am 17

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

vijju123 February 14, 2018, 1:08pm 18

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

abx_2109 February 14, 2018, 2:02pm 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

vivek_shah98 February 14, 2018, 3:03pm 20

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

1 Like

vijju123 February 14, 2018, 4:38pm 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.

vijju123 February 14, 2018, 4:39pm 22

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

abx_2109 February 14, 2018, 7:35pm 23

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

abx_2109 February 14, 2018, 7:37pm 24

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.