FRMQ - Editorial

editorial
, , , , ,
21

And all the time i was thinking that the intended solution will be sleeker and awesome…what a disgrace
Such problems must not be allowed to appear in Long Contests… worst problem ever on CC… waste of time!!

5 Likes
22

To me Codechef long challenge is very important and seeing such a poor “code optimization” problem makes me sad. Codechef, I have high hopes from you, please take care before serving the problems. The efforts being made are great but this is one scar on the repute.

3 Likes
23

http://www.codechef.com/viewsolution/6745851

i have implemented my solution based on topcoder tutorial of sparse table algorithm during the contest! But still i got 70 points! Please have a look at it !

24

I have no idea about sparse table someone please give me some tutorial

2 Likes
25

Can you give the link to tutorial of sparse table

1 Like
26

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
27

arr[N][logN] worked for me (after lots of optimizations of course)

28
1 Like
29
30

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

31

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

32

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

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

1 Like
33

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?

34

Terima kasih dan salam kenal.
codechef Link

code Link

35

Anybody solved this problem with BIT ?

36

that’s sweet, thanks

37

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- https://www.codechef.com/viewsolution/7497214
Any help is appreciated.