could any body please tell me why all test cases are not passed in my code ??
link
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
@farzi, I think if the CPU supports it, those are run in a single instruction and therefore technically O(1) but I am not 100% sure about that.
Really liked your technique of calculating log2.
But do you think A[2][100] can be accessed faster than A[100][2]?How?
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: CodeChef: Practical coding for everyone
You can also use __builtin_clz() to compute log2().
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.
@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].
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 .