PROBLEM LINK:Author: Vasya Antoniuk DIFFICULTY:medium PREREQUISITES:partial sums, dequeue, dynamic programming PROBLEM:You are given 2D matrix $A[n][m]$. The matrix will be called good if there exists a submatrix (continuous rectangular block of matrix) of dimensions $a \times b$ whose all of its elements are equal. In a single operation, you can increase any element of the matrix by 1. Find out minimum number of operations required to make the matrix good. QUICK EXPLANATION:For finding sum of a submatrix, you can use partial sums. EXPLANATION:Let us consider some $a \times b$ dimension submatrix. Let $x$ be the largest element in the submatrix. Let $S$ be the total sum of elements in the submatrix. For making all the elements equal in minimum number of operations, we should aim to make all the elements equal to $x$. So, the minimum number of operations required will be $x * n * m  S$. So, we have to find the sum and maximum element in all the possible submatrices of dimension $a \times b$. For finding sum of all submatrices of sizes $a \times b$, we can use maintain partial sum submatrix. For that, we maintain another array, $sum[n][m]$, where $sum[i][j]$ will denote the sum of elements of the submatrix with left top end coordinate being $(1, 1)$ and right bottom coordinate being $(i, j)$. After computing $sum$ matrix, we can find the sum of any submatrix. Now let us learn about how to find maximum element in all submatrices of sizes $a \times b$. Let $maxCol[i][j]$ be the maximum element of the submatrix in the column starting at $(i, j  b + 1)$ and ending at $(i, j)$ (i.e. of column of length $b$). Assume that we have computed $maxCol$ array efficiently, let us find how we can use this to calculate maximum of $a \times b$ submatrix. Let $max[i][j]$ denote the maximum value of submatrix of $A$ ending at $(i, j)$ (bottom right point), and of dimensions $a \times b$. Note that $max[i][j]$ is maximum of $maxCol[i  a + 1][j], maxCol[i  a + 2][j], \dots, maxCol[i][j]$. Note that for calculating $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]$. That means, that we have to maintain maximum of a constant size subarray of an array, i.e. at each step, maintain maximum with inserting and deleting one element at each step. Note that we can compute $maxCol$ in similar way. This can be done either maintaining a multiset (balanced binary search tree) of $K$ elements, in which insertion/deletion and finding maximum can be done in $\mathcal{O}(log(n))$ time. Sadly this method is slower for passing largest subtask. You can find a $\mathcal{O}(n)$ solution for it by using doubly ended queue (aka deque). Please see this link for its very detailed explanation. Time Complexity:$\mathcal{O}(n m)$ for finding both $maxCol$ and $max$ matrices. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 12 Jun '16, 11:18

You can also use a 2d version of the spare table to compute the maximum. With MNlogMlogN computation you can answer a max query on a any given submatrix in O(1). Basically apply RMQ on every row of the matrix, then along the columns of the output of the first RMQ. answered 15 Jun '16, 16:26
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).
(15 Jun '16, 17:14)
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).
(15 Jun '16, 17:41)
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?
(15 Jun '16, 17:46)
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 : https://www.codechef.com/viewsolution/10438764
(15 Jun '16, 18:13)
@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.
(15 Jun '16, 19:03)
@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).
(16 Jun '16, 03:24)
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 .
(16 Jun '16, 18:43)
showing 5 of 7
show all

Here is a link to my Solution using 2D sparse tables. For those who got TLE in some test cases/full subtask3 using this, here are a few optimisations:
I hope it helps. answered 15 Jun '16, 18:07
Really liked your technique of calculating log2.
(15 Jun '16, 20:02)
2
You can also use __builtin_clz() to compute log2().
(15 Jun '16, 23:18)
2
@farziengineer, Even I wondered the same. What after seeing the FRMQ question (mentioned in the link), my views changed especially when declaring such large multidimensional arrays. Although for small cases I still declare the array as A[100][2] rather than A[2][100].
(16 Jun '16, 04:39)

The method described above to find the maximum value in all possible subarrays of K is also called Sliding Window Maximum. Though this method pretty much passes all the subtask within time, I am not able to understand why is the combination of Sparse Table + Sliding Window Maximum failing to pass the Subtask # 3. I precomputed the Sparse Table for each row, that is O(nmlogm), where n is the number of rows and m is the size of each row. So, now I can get minimum for each subarray(of any size, let say a) of each row in O(1), and then I apply Sliding window there to find minimum for each row, in O(b), where b is the number of rows in target submatrix. So total time complexity becomes O(nmlogm + 4QMN) where as, if use two sliding windows in each query it becomes O(5QMN), how does the double sliding window pass and sparse+sliding window isn't passing? 2MN is required to calculate sum matrix, MN is required for finding answer, and 2MN for two sliding windows for each submatrix. This is only possible when logM>Q, but since Q can be 50 but logM is maximum 10, why isn't the Sparse Table solution passing. Please correct me if I am wrong somewhere. This is my Sparse Table Solution.
link
This answer is marked "community wiki".
answered 15 Jun '16, 15:30
the complexity formula is just a generalization. there are often many more constants to it that could have made the complexity more "complex".
(15 Jun '16, 16:14)
i too did using multiple sliding windows , actually log(n) sliding windows , 1x1 , 2x2, 4x4 , 8x8 ,16x16 till 512x512.
(15 Jun '16, 17:59)

I have used 2d version of sparse table for maximum element in sub matrix and precompute sum in o(2*n) which is O(n) time. but i cant pass third sub task can anyone tell me where i go wrong or how can i do better than this. https://www.codechef.com/viewsolution/10499476 thanks in advance!!. answered 15 Jun '16, 17:15
Use builtin_clz instead of log2 to get AC. If a is 32bit integer: log2(a) = 31  builtin_clz(a) See my solution here: https://www.codechef.com/viewsolution/10296148
(15 Jun '16, 20:49)

you should find sum in o(1) using summed area table.. and optimize 2d version of your sparse matrix. answered 15 Jun '16, 17:50

I used multiple sliding window for getting the maximum element in submatrix.
answered 15 Jun '16, 17:59

I created 2 D table to store maximum element inside each submatrix. Using DP, I am filling this spare table in O(n*m). I am not getting TLE but I [got] WA in many cases. Please help me figure out what am I doing wrong here. Link to my solution : https://www.codechef.com/viewsolution/10506486 answered 15 Jun '16, 18:35

A lot of people have implemented 2d sparse table like this int sparse [m] [n] [logm] [logn] and they got an tle in subtask#3 Now the catch is if u would implemented like this int sparse [logm] [logn] [m] [n] then it would have passed all casses with flying colors. Link to my submission by using 2d sparse table: https://www.codechef.com/viewsolution/10464323 answered 15 Jun '16, 18:38

Unable to view setter's or tester's solution. And also in the Explanation it should be: "the minimum number of operations required will be x∗a∗b−S." instead of: "the minimum number of operations required will be x∗n∗m−S." answered 15 Jun '16, 18:49

I used 2D Sparse Table. I got TLE at first when using the log2() function, then I got AC when I used __builtin_clz(). https://www.codechef.com/viewsolution/10296148 answered 15 Jun '16, 19:16

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 !! answered 15 Jun '16, 21:15

"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[ia+1][j]? answered 16 Jun '16, 00:42

One fact can be exploited for finding max in sub array that A[i][j] ≤ 1000. algo for finding maximumofallsubarraysofsizek :
This code will pass for random generated value and very simple to code. Solution answered 16 Jun '16, 01:12

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 answered 16 Jun '16, 02:08

Can anybody tell me please, where my solution is giving wrong ans. Link: https://www.codechef.com/viewsolution/10517685 answered 16 Jun '16, 16:24

When the editorial for problem "Misha and Geometry" will be published ?? I can't open a thread that's why asking here ! :( answered 20 Jun '16, 21:58

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
Can you please make the definition of maxCol[i][j] more clear? I don't understand the part "maximum element of the submatrix in the column", please explain. Thanks.