FRMQ - Editorial

editorial
, , , , ,
3

will 10^8 run in one second? i used to assume around 10^7 calculations per second. what should is assume as upper limit for computations in one sec.

1 Like
4

Can someone explain “Method 3”? How to use splay trees with O(N) update and O(1) query?

5

I did just the same thing and was getting 70 points.

I used and array for the sparse matrix as arr[N][logN] ,but as soon as I changed my array to arr[logN][N] ,it gave 100 Points…

What’s the reason for this?

Why did the running time decrease?

1 Like
6

Can any one give me a useful link for splay tree ?

7

The reason of arr[logN][N] getting accepted is that since x and y are increased only by a small amount, the row number tends to remain constant, and column number increases only by a small amount. So subsequent accesses tend to happen within the same memory block. This increases the number of cache hits.

7 Likes
8

This problem was kind of a disaster . Its very sad that all those people who didnt use a kind of worthless optimisation atleast from the respect of goals of codechef didn`t get the points and hence the ranking they deserved. Very sad .

3 Likes
9

I wrote the solution with sparse table but it took only 70 points. I managed to get 100 with these 2 further optimizations:

  • When you have something like (A + b) % C and b is very small compared to C, using C++ the code(a + b) % c is far slower than a += b; if(a > c) a -= c; Don’t ask me why because I don’t know, but I noticed that only this was enough to take 100 point (from more than 1s to 0.8).
  • N is O(10^5) so x can have at most 10^5 -1 different values, and y 10^5 different values. We can find the length of the two cycles ( length of x cycle = N / 7, length of y cycle = N/11, because 7 and 11 are prime numbers). Then you can find L = lcm of these 2 numbers and if L < M you can just make L queries and if sum[ i ] is the sum of answers at i-th iteration answer will be
 sum[ L ]* (M/L) + sum[ M % L]
1 Like
10

Hi i used method 1 to solve this problem. this is my code with this i got only 20pts. Can any please tell me why i got only 20pts?

1 Like
11

I think M<=10⁷ or N,M<=10⁶ would have perfectly make the M*logN solutions time out, there was no need at all for M<=10⁸ (which is supposed to be TLE on other tasks btw)

Why is nowadays every problem so much about crazy optimization?

I mean, why do we have to spend hours trying to find out whether if we (don’t) inline a function/use post-increment operator outside of while()/swap the dimensions of an array/take modulo one time less/other useless optimizations, then the running time will decrease by 0.01sec and will be inside the limit? It just doesn’t make sense in my opinion, since you can’t know, what will decrease and what will actually increase the running time. E.g. I changed N times post-increment on X to X+=N; and the program actually ran 0.10sec slower on one single test case.

2 Likes
12

@prasadram126 the O(M*N) solution is really supposed to get 20 points, you should implement the third one to get 100p

13

can anyone post a link to a resource where i can learn this approach of using sparse tables.

14

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!!

8 Likes
15

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
16

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 !

17

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

2 Likes
18

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

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?