PROBLEM LINK:Author: Pavel Sheftelevich DIFFICULTY:Medium PREREQUISITES:Merge sort, Fenwick tree PROBLEM:
QUICK EXPLANATION:
EXPLANATION:SUBTASK 1In the easiest subtask, $N, M \leq 20$, so we can iterate over all possible $O(N^2 \cdot M^2)$ submatrices, and for each one, compute its sum in $O(N \cdot M)$ time summing up all its elements, and check if the resulting sum is less or equal to $S$. This solution has time complexity $O(N^3 \cdot M^3)$, which is enough here. SUBTASK 2Now, we have to deal with $N, M \leq 50$, so we cannot be so naive in computing the result as in the previous subtask. However, the matrix is still small enough to iterate over all possible of its submatrices. If we only are able to decide in a constant time, if a particular submatrix has a sum of its elements less or equal to $S$, we can solve this subtask in $O(N^2 \cdot M^2)$ time iterating over all possible submatrices and making a fast check for each one of them. How to decide in a constant time if a given submatrix $B$ of $A$ has a sum of its elements less or equal to $S$? Well, we can use prefix sums here. First, let's compute $P[i][j]$ table, where $P[i][j]$ is the sum of elements in a submatrix, which has its top left corner in the first row and the first column, and its bottom right corner, in the $i^{th}$ row and in the $j^{th}$ column. Notice that we can compute the whole $P$ table in $O(N \cdot M)$ time, but $O(N^2 \cdot M^2)$ is also sufficient here. Then if we want to compute the sum of elements in a submatrix $B[i_1, j_1, i_2, j_2]$, we can use $P$ table to do that. Let $X$ be the sum of elements in $B$, then $X = P[i_2][j_2]  P[i_2][j_1  1]  P[i_1  1][j_2] + P[i_1  1][j_1  1]$. Using this trick, we are able to compute the sum of any submatrix in a constant time, which leads to a $O(N^2 \cdot M^2)$ solution. SUBTASK 3
First, let's fix some index $k$, which will stand for the rightmost column of a submatrices we search for. Next, rather than counting submatrices with sum at least $S$, we will count submatrices with sum less than $S$ and subtract them from all possibles submatrices. In other words, we are interested in the number of submatrices ending in column $k$ with sum less than $S$. How to count this amount? Well, we can use slightly modificated $P$ table defined in the solution to the second subtask here. Let $P[k]$ be the sum of elements in a submatrix with $k$ fixed as the rightmost column and the first columns as its leftmost column (of course it also has $i^{th}$ row as its top row, and $j^{th}$ row as its bottom row  both these rows are fixed). Now, for a fixed $k$, we want to compute how many values $x < k$ are there, such that $P[k]  P[x] < S$. Notice that if we have all values of $P[y]$ for $y < k$ sorted in ascending order, we can just find the smallest index $x$ in this sorted order, for which $P[k]  P[x] < S$, and then all submatrices corresponding to indexes greater than $x$ in the sorted order, also have the sum of elements smaller than $S$. This last task can be solved beautifully with merge sort as Sergey did while he was testing the problem. Please refer to his implementation, because it explains the best how code a merge sort based solution. This solution is very similar to counting inversions in an array using merge sort, the base idea is the same here  first we divide the array of values $P[y]$ into two halves, for which we solve the problems recursively. Then, for each index from the sorted right half, i.e. the value of $P[k]$, we count the number of indexes $x$ of elements in the sorted left half, for which $P[k]  P[x] < S$. Since both halves are sorted, we can do this in linear time. After that, we merge both halves into one sorted array as in merge sort. Some participants uses different techniques, like for example the Fenwick Tree. Any data structure sufficient to count the submatrices as described above is perfect here. After we solve the above subproblem for all pairs of rows, we have the result. The total complexity of this method, as intended, is $O(N^2 \cdot M \cdot \log M)$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 25 Oct '15, 13:10

For those who are unable to access the solutions, try the links below(The links above redirect to a default page) : Author's Solution : http://www.codechef.com/download/Solutions/LTIME29/Setter/SVNTR.cpp Tester's Solution : http://www.codechef.com/download/Solutions/LTIME29/Tester/SVNTR.cpp answered 31 Oct '15, 20:41

@gowdasunil That is wrong. Calculate p[i2][j2]p1[i2][j1]p[i1][j2]. You will see that submatrix (<1,1>,<i1,j1>) is subtracted twice. So we need to add it. Try drawing a matrix on paper, you will get the catch. answered 26 Oct '15, 09:01

Weak test cases !! Even the SUBTASK 3 runs in O(N^{2}.M^{2}) complexity. answered 25 Oct '15, 14:09

i think correct idea be X=p[i2][j2]p[i2][j1]p[i1][j2] p[i1][j1] ? answered 26 Oct '15, 00:21

I can't see author's solutions. After following to link I see "access denied". answered 26 Oct '15, 05:15

True. SUBTASK 3 passes with a slow solution: https://www.codechef.com/viewsolution/8636909 answered 26 Oct '15, 08:56

So, apparently fast $O(N^2M^2)$ solutions were able to pass the last subtask, while my $O(M^2Nlog{N})$ wasn't. Requiring constant optimisation in a short contest isn't a good idea. answered 26 Oct '15, 22:57
