FRMQ - Editorial

editorial
, , , , ,
19

segment tree is the best to be understood if someone knows DIVIDE AND CONQUER METHOD.I finally gt it

20

can i get some better explanation for sparse table ,it’s difficult to understand,plz explain or give some link by which it can understand more easily

21

https://www.youtube.com/watch?v=0rCFkuQS968

Found an MIT lecture on this. Complexity: { O(N) (update),O(1) (query) }

1 Like
22

i used segment tree to solve this question but in last two test cases i am getting runtime error can anyone explain me why i am getting runtime error link text
i think so my solution is well optimized and i don’t know for which test cases i am getting runtime error if i increased the size of array around 10^7 then i am getting tle please anyone explain me why i am getting runtime error and tle if i increase the size of array?

23

Terima kasih dan salam kenal.
codechef Link

code Link

24

Anybody solved this problem with BIT ?

25

I solved the problem using segment tree which takes O(logn) time.I got only 70 points,for the last sub-task I am getting a TLE.Can someone please help me?
solution- CodeChef: Practical coding for everyone
Any help is appreciated.

26

Read about cache

1 Like
27

http://digital.cs.usu.edu/~allan/DS/Notes/Ch22.pdf

28

It have been fixed now; when edotorial was published, there was “We can use Splay Tree to solve this case.” in case 3.

29

Ok, thank you.

30

On the other hand, such “worthless optimization” may give you one more solved problem at regional contest or even world finals. For me it happened 10-15 times during trainings already. I don’t think that this problem is good, for me picking such constants looks like easy way to make problem “harder” and simply get more money for it :smiley: But people who can’t solve a problem - don’t deserve higher rankings.

2 Likes
31

order of 10^8 operations per second is a good approximation on an upper bound.

1 Like
32

thanks, upper bound for codechef increased,

but i feel its risky in competitions where you can make one submission or you get penalty for wrong one.

33

Can you give the link to tutorial of sparse table

1 Like
34

just by changing a[n][logn] to a[logn][n] the solution gets passed… It doesn’t make any sense for us to spend hours on end to think of such optimizations… a constraint of m<=10^7 would have easily sufficed in this problem -_-

1 Like
35
1 Like
36
37

that’s sweet, thanks

38

Use normal sparse[N][logN] ,no need to use sparse[logN][N] .Precompute all log2 value and stop using useless mod task , use this if l>=n-1 l%=n-1…You will get full points .