I implemented the solution using sparse table but still got 70 points. Using a small change of Sparse_table[maxi][18] to Sparse_table[18][maxi] got me 100 points.
Can anybody explain me how this change leads to faster calculation?
But its wrong… The question should not be like this. By just changing the rows and columns you get AC. Codechef should not give such problems in the long contest. Very bad…
@navneet1v2313 imo that’s what long contest are for. You have enough time to profile your solution.
It is NOT wrong. You should know about cache memory. It is not a question about “just changing the rows and columns you get AC”.
2 Likes
@alexvaleanu Many Thanks for the link, still, how does transposing the array speed up cache hit? just curious to learn, and would appreciate your answer
@njr07121977 I believe it is because of the memory layout. When u declare something like int arr[10][1000] and loop over it, a new memory access is carried out once every 1000 times for 10 times . However , for arr[1000][10] the program makes memory access after every 10 operations for a thousand times . It doesn’t seem much but apparently it does make a difference 
@alexvaleanu: but a question based on such kind of algorithms is not suited to codechef where the main focus is on algorithms…