CHSQARR - Editorial

editorial
, , , , ,
15

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

16

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

17

Can anybody tell me please, where my solution is giving wrong ans.
Link: CodeChef: Practical coding for everyone

18

Similar problem from Codeforces

19

can anyone explain editorial in a precise way?

20

Check my blog

2 Likes
21

could any body please tell me why all test cases are not passed in my code ??
link

22

When the editorial for problem “Misha and Geometry” will be published ??

I can’t open a thread that’s why asking here ! :frowning:

23

the complexity formula is just a generalization. there are often many more constants to it that could have made the complexity more “complex”.

24

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

25

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

26

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?

27

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

28

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

29

@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.

30

Really liked your technique of calculating log2.

But do you think A[2][100] can be accessed faster than A[100][2]?How?

31

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

32

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

33

You can also use __builtin_clz() to compute log2().

1 Like
34

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.