I want to know the explanation of this problem :- CodeChef: Practical coding for everyone
The video explanation of this video is not much clear and I want to know if there is any other way to solve this problem.
Can anyone help me.
Yes , mine too !!!
I don’t know about the video explanation but I will explain this problem on my own.
First you need to know that we can easily get the sum of any submatrix of the matrix in constant time using a precomputation (for more details, please reply).
Next, we should focus on finding the matrices. You can notice that if we fix the top left corner of the submatrix and then keep increasing the side length of it, the value of average will always increase. So, it will be good if we fix the top left corner of the square sub-matrix and then binary search for the minimum length on beyond which, the value of average is not less than K.
How to proceed with binary search.
Once we fix the top left corner as i and j, we can binary search for L (the side length of sub-matrix).
Binary search is very intuitive here because we know that the average increases with an increase in the side length. So, we need to find the side length, the average at which is the lower bound to K. Run a simple binary search on the side length L. Maintain two pointers, namely l and r which will denote that the lower bound of K lies between these two. Then, find the mid element and get the sum of the square submatrix with i and j as the top left corner and mid as the length.
If the average (\frac{sum}{mid\cdot mid}) is not less than K, we know that at least mid is our answer and we can proceed to finding some answer less than mid (i.e the left half). Else we move to the right half of the range.
Time complexity within the test case loop will be O(n^2logn) (n^2 for fixing the top left corner and logn for searching for the side length).
For implementation details, please refer to this solution.
For any clarifications or any corrections, please reply :).
EDIT : You may refer to this lower bound binary search implementation for learning.
My approach is exactly the same. I think this was kind of a standard approach.
Hi Vishal. I would like to know more about getting the sum of any submatrix in constant time. Could you kindly elaborate on this?
You can create a new 2D array of size n * m named “dp”. In this array, dp[i][j] = sum of all elements in the submatrix 0,0 to i,j. Now using the technique of prefix sums, you can compute the sum in constant time.
1 Like
Let pre[i][j] denote the sum of the matrix starting from (1,1) (1-base indexing) and ending at (i,j). You can use the following transition to calculate pre[i][j] for all (i,j).
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]
Where a[i][j] is the element of the original matrix.
Also, for computing the sum of a matrix starting and (a,b) (top left corner) and ending at (c,d) (bottom right corner), a similar transition can be used.
sum = pre[c][d]-pre[a-1][d]-pre[c][b-1]+pre[a-1][b-1]
3 Likes
Thank you Vishal.
can you please tell me that why my solution is 75% accepted of worthy matrix problem
solution link:-CodeChef: Practical coding for everyone
Why are you restraining N and M to 10000 only? N\cdot M is no greater than 10^6 but N and M both can be as high has 10^6. It’s better to use aux[\>][\>] as a vector<vector<ll>>, which you can resize later.
I wonder how your code is passing even that many test cases, because each of the three subtasks has either n\ge10000 or m\ge10000. If you use assert(n<N&&m<M), then you get this (line 40) verdict.
Also there was an error in binary search function. It’s basically like if you have received
sumq\lt sum, you will go into the right half, i.e. do l = mid+1 else you note that mid is our new answer and then move to the left half, i.e. do r = mid - 1. But you were returning right at the point you got sumq == sum.
2 Likes
thank you so much for your help 