What is wrong with my code if only subtask one is considered?? the third task in subtask 1 showed wrong answer?? rest other were correct…
Use __builtin_clz instead of log2 to get AC.
If a is 32-bit integer:
log2(a) = 31 - __builtin_clz(a)
See my solution here: 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 !!
You can also use __builtin_clz() to compute log2().
1 Like
Can you please make the definition of maxCol[i][j] more clear? I don’t understand the part “maximum element of the sub-matrix in the column”, please explain. Thanks.
“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 : https://www.codechef.com/viewsolution/10505911
@farziengineer, I was also getting TLE at subtask 3.
While querying for max value in a rectangle I was computing log every time which was taking some time. I precomputed log of all values till 5000 and accessed them from an array. And my code got accepted in time less than 1 sec. (initially it was going beyond 4sec on subtask 3).
@farziengineer, Even I wondered the same. What after seeing the FRMQ question (mentioned in the link), my views changed especially when declaring such large multi-dimensional arrays. Although for small cases I still declare the array as A[100][2] rather than A[2][100].
1 Like
Can anybody tell me please, where my solution is giving wrong ans.
Link: https://www.codechef.com/viewsolution/10517685
Thanks a lot @mishraiiit I was able to get AC using my 2D sparse table by precomputing the log values . I was breaking my head to find why it’s causing a TLE . I didn’t know that Math.log in java was so slow .
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 ! 