CHSQARR - Editorial

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 ! :frowning:

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…

https://www.codechef.com/viewsolution/10441994

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().

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.

@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

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 .