I created 2 D table to store maximum element inside each submatrix. Using DP, I am filling this spare table in O(n*m). I am not getting TLE but I [got] WA in many cases. Please help me figure out what am I doing wrong here. Link to my solution : CodeChef: Practical coding for everyone
A lot of people have implemented 2d sparse table like this int sparse [m] [n] [logm] [logn] and they got an tle in subtask#3
Now the catch is if u would implemented like this int sparse [logm] [logn] [m] [n] then it would have passed all casses with flying colors.
Link to my submission by using 2d sparse table: CodeChef: Practical coding for everyone
Unable to view setter’s or tester’s solution. And also in the Explanation it should be: “the minimum number of operations required will be x∗a∗b−S.” instead of: “the minimum number of operations required will be x∗n∗m−S.”
I used 2D Sparse Table. I got TLE at first when using the log2() function, then I got AC when I used __builtin_clz().
https://www.codechef.com/viewsolution/10296148
I tried 2D sparse table during contest and it got TLE in subtask 3 and now I just changed the declaration of rmq array as suggested by likecs and it passed easily…
Previous solution
New solution
However, I managed to get 100 points during contest with the approach mentioned in editorial but I do think that time limit must be set in such a way that either both solutions should pass or neither of them.
Btw, it was a nice question and I really enjoyed cracking it !!
“Note that for calculating max[i][j+1]max[i][j+1] from max[i][j], we have to add a new element maxCol[i][j+1] and remove the element maxCol[i−a+1][j].” Could anybody please help me understand this statement? Why would we remove maxCol[i-a+1][j]?
One fact can be exploited for finding max in sub array that A[i][j] ≤ 1000. algo for finding maximum-of-all-subarrays-of-size-k :
- Maintain array of length thousand and a pointer to this array.
- update array with latest discovery time of each value.
- If updated value is greater than current pointing value update pointer to new value.
- If current pointer value has expired, decent down the array till you find unexpired value.
This code will pass for random generated value and very simple to code.
Solution
I used summed area tables to find sum of any submatrix in O(1) with O(n^2) preprocessing time. Wikipedia explains them well : Summed Area Table
For finding maximum element I precalculated maximum elements in every 2^a row,2^b column combinations. Like for every sub matrix of size 1,2 1,4 1,8 1,16… 2,1 2,2 2,4 2,8 2,16… 4,1 4,2 4,4 4,8… and so on. This helps to find maximum element in any submatrix in O(1) with O(k.n^2) preprocessing time.
It passed in 1.33 seconds .
Here’s the code : CodeChef: Practical coding for everyone
Can anybody tell me please, where my solution is giving wrong ans.
Link: CodeChef: Practical coding for everyone
can anyone explain editorial in a precise way?
When the editorial for problem “Misha and Geometry” will be published ??
I can’t open a thread that’s why asking here ! 
the complexity formula is just a generalization. there are often many more constants to it that could have made the complexity more “complex”.
I think that for each matrix of dimension a*b, the query complexity is O(log(a)+log(b)) and not O(1) , though I would agree that according to the given constraints O(log(a)+log(b) ) is small enough to be considered as O(1).
Its not log(a) + log(b) but its not just 1 operation either. Technically you take max of 4 values. Which is 3 comparison operations. And yes, it is small enough that it can be considered O(1).
Hey,
When you are using __builtin_clz(b) or __builtin_clz(a) isn’t it taking O(log(b)) and O(log(a)) to compute the leading zeros in the binary representation?
i too did using multiple sliding windows ,
actually log(n) sliding windows , 1x1 , 2x2, 4x4 , 8x8 ,16x16 till 512x512.
Solution : CodeChef: Practical coding for everyone
Even I used the same approach but my 2d sparse table caused TLE in subtask 3 . I think O(MNlog(M)log(N)) build time is insufficient
Submission : CodeChef: Practical coding for everyone