plz explain JUNE LONG CHALLENGE CHSQARR by sparse table mathod?

editorial
1

plz explain the soluiton of JUNE LONG CHALLENGE CHSQARR by sparse table mathod

1 Like
2

This problem can be reduced into trying out sub-matrices of different sizes and then applying sliding window method and calculating the max value and sum of every sub-matrix. Now if we do that the complexity for each sub-matrix check is (sub-matrix length * sub-matrix width) which becomes O(matrix lengthmatrix width) in the worst case. And again for the sliding window process the complexity is O(matrix lengthmatrix width) , so the overall complexity is O(matrix lengthmatrix widthmatrix length*matrix width).

for n,m as much as 1000 this process isn’t even worth trying. So we need to do some optimization.

For calculating sum we can simply follow 2D cumulative sum approach which gives the result in O(1).

Now for calculating maximum element what should we do ? We can do better than Brute-Force checking by forming a 2D segment tree that reduces the complexity to O(nmlog(n)*log(m)). But even this is not enough and causes TLE( It caused me TLE :frowning: )

Now since the matrix is static(i.e. not updating) we can do better. Instead of segment tree we can use a 2D sparse table. This initialization takes O(nmlog(n)*log(m)) time and per query time is O(1).

Now how can we construct a 2D sparse table ? This link gives all that you need

3 Likes
3

You need to figure out the sum and maximum value in all sub-matrices of size a x b for each query. Sum can be pre-computed. For maximum value, use sliding window algorithm ( Sliding Window Maximum (Maximum of all subarrays of size K) - GeeksforGeeks ) for each query. The overall complexity reduces to O( QNM). Using segment tree to compute maximum values makes complexity O( QNM*(log(N)+ log( M))), therefore you get TLE.

AC sol: CodeChef: Practical coding for everyone

1 Like
4

@robin_0_chef can you share me your segment tree approach? I presume u created a segment tree of segment trees of each row of the matrix?

1 Like
5

Hey try this article Given an n x n square matrix, find sum of all sub-squares of size k x k - GeeksforGeeks

After reading and understanding the concept behind this one, you will be able to solve the question.
Instead of kk, you have to find maximum and sum for ab.(I assume that you know about how to find maximum in array, just extend it for 2-d array).
Happy Coding and cheers…:slight_smile:

6

@atulshanbhag I used the idea of quad tree while implementing the segment tree approach.
Here you can see my solution :slight_smile: The reason it is TLE is due to the fact that O(1) vs O(logn) per query :confused:

You can get some more insights from here :slight_smile:

7

@robin_0_chef yes i did read about it… you have used quad tree approach. basically a segment tree of segment tree is the same as a quad tree… will try your approach too… thanks for the link :smiley:

8

@rohitangira my code which i submitted during contest uses the sliding window technique. i precomputed the sums of all sub-matrices sum[i][j] for the sub matrix defined by (0,0) to (i,j), complexity being O(MN). and then each query requires O(MN) using sliding window technique.

9

I have explained this in my blog

10

your code looks decent can u explain ??