I submitted the problem using segment trees but got 70 points only...then i saw the inherent pattern in the queries..that were being generated by the formulae...by the corresponding N values... and came with a faster dp approach but still got 70 points.... finally i wrote a sparse table...for quering in O(1) ...but still got 70 points... people got AC using sparse table...where did i go wrong? here is my solution http://www.codechef.com/viewsolution/6754646 asked 13 Apr '15, 18:27

First of all, you have stuff like "(b+11)%(t);" there. % operation is very slow; try to rewrite it using subtraction instead. Also you may change M[maxi][17] to M[17][maxi] to avoid large jumps over memory. answered 13 Apr '15, 18:34

For performance improvements, you need to use int M[17][maxi]. This makes your code much faster. answered 13 Apr '15, 18:32
Can you explain why?
(14 Apr '15, 01:03)
2
Simple answer: slow RAM, fast CPU and CPU caches. The problem is, that current CPUs are much faster than RAM  see this article for more information about the CPURAM gap. As a result, a CPU access to RAM costs a lot of CPU cycles. To reduce this problem, current CPUs have several levels of caches, which usually work best, when accessing memory addresses, that are close to each other. You can try a simple example. Try running this program and measure its execution time:
Then switch indices used to access the array  change In the first version, you access the array (or matrix) rowbyrow. As each row is stored as a continuous memory block, you start with the lowest memory address and continue up to the highest memory address assigned to the array. This type of access is cachefriendly. On the other hand, in the second version you access the array column by column, which means skipping to a distant memory address in each iteration. As for the original question, one of the problems could also be the
(14 Apr '15, 03:13)

i can't understand the purpose behind asking this question... ? First of all giving 70 points just for writing a classic segment tree solution... and even worse..100 points for just optimising the sparse table solution.. ! answered 14 Apr '15, 13:21

@karanaggarwal : yes i tried solving it using maths...first i found the pattern in queries... no matter what the initial x and y were the query pattern repeated after N1 for x and after N for y when x=(x+7)%(t1) and y=(y+11)%t; that means the queries will repeat exactly after N(N1) queries...so if M was greater than N(N1).. q=N(N1) i calculated only the sum of N(N1) queries and multipled it M/q times...and processed the remaining M%q queries... also queries for x depended on N in such way that if(N%7==1)...then x repeated after N/7 times... and queries for y depended on N in such way that if(N%11==0)...then y repeated after N/11 times... so the q term would be (number of time x repeated) * (no. of times y repeated)... and then using above dp approach...but it still fell apart when the N was neither N%7==1 or N%11==0 thats why i used sparse tables answered 13 Apr '15, 18:48

Plz post the editorial ..of this problem ..