You are given an array of integers, and are asked a lot of queries (at most 10^8) like give two indices find the maximum of all the integers in the array whose index lies between those two.
EXPLANATION:
The generation of the queries as given in the question is
x = x + 7 (mod N - 1)
y = y + 11 (mod N)
l = min(x, y)
r = max(x, y)
You need to find maximum of a[i] such that l <= i <= r.
The generation of (l, r) pairs is like a pseudo random procedure, so its very very hard task to find a pattern in that. Now as we got (l, r) for each query the finding maximum is quite a standard task of range queries.
There are a lot of ways to find range queries. Some of them are
O(1) per Update and O(N) per query : Using an array, we can update each element in O(1) and when queried iterate through all elements from l to r.
O(log N) per Update and O(log N) per query : There are a lot of ways to do this. We can use Segment trees, Binary index trees, etc.
O(N) per Update and O(1) per query : We can use Sparse Table to solve this case.
The methods used for 2 and 3 are very standard and their explanation can be found at a lot of places.
Some useful links for solving Range Queries using Method 2 are
I expect to see a lot of comments like âI wrote a correct solution but got TL, why?!â below
What was the reason for giving such constraints? There are no idea at all in given task, only problem is because of constraints. If you want to prevent logN solutions from passing - much lower constraints are enough; if you want to make task challenging and teach people to write well-optimized code - you may set TL even stricter (0.75 is still not hard to reach)⌠This problem is already awful even with 1 second, so why to stop at it?
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.
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 .
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 But people who canât solve a problem - donât deserve higher rankings.
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) cis far slower thana += 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
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.
