I recently solved two problems, one is this based on sparse matrix implementation: FRMQ Problem. In this(see editorial), if we create a matrix of size a[log N][N], it gives an AC, else it gives a TLE. Again, I did this question: CARLOS Problem, in which I created a DP matrix with size as dp[201][200001], the same convention as in the previous question to avoid TLE, but got a TLE. When I converted the DP array to column major, I got an AC, with dp[200001][201]. I do not understand why this happened.
The reason is caching. Our computers(even servers) have a cache size of few MB’s. This means that to access some element from memory is faster if it is already present in cache than fetching it from the memory location. Most it follows the “least recently used” principle(You can google that for more details).
Thus program execution sometimes depends on the caching behaviour when we declare large array sizes (about 10^6 and above) as then the cache may not be able to hold all array values. Thus the order in which you execute the loops and access the memory locations matters.
In FRMQ question, the loops are like here.
Thus creating array like a[logn][n] helps because of the order in which the array is processed. Declaring array like a[n][logn] is not effective here.
Similarly you can see that for your question CARLOS as well.
1 Like
Thanks man. I remember it was your comment of FRMQ editorial because of which I knew that I had to declare the matrix that way. Thanks! 
If you feel your question is answered, mark it as correct 