FRMQ - Editorial

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

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

1 Like

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?

Terima kasih dan salam kenal.
codechef Link

code Link

Anybody solved this problem with BIT ?

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.

Read about cache

1 Like

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

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

Ok, thank you.

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

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

1 Like

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.

Can you give the link to tutorial of sparse table

1 Like

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
1 Like

thatā€™s sweet, thanks

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 .