PROBLEM LINK: Practice, Contest
CATEGORY: MEDIUM
PRE-REQUISITES: hashing, dynamic programming, ad-hoc, two-pointer
EXPLAINATION:
As constraints must have specified this problem could be solved in O(n^3) complexity. A brute force solution to the problem is to consider all the possible matrices and check whether there sum modulo A gives B or not. But, its complexity is O(n^4). Now, continuing with the same idea, if we can eliminate a single loop and calculate the number of matrices in O(1) instead of O(n) (as the final loop does), we have got the solution. The solution goes as follows:
Let i and j denote two rows in the matrix such that i <= j. Also, let k denote a column in the matrix. Now, let total denote the sum of all elements between row i and row j from column 1 till the column k. Let newVal store the value of total modulo A.
Now, if we have the count of matrices which had their total modulo A equal to newVal – B, then that only is the number of matrices upto column k (and having elements between row i and row j) whose sum of elements modulo A is equal to B.
The problem here arises is how to store the count of such matrices. A simple solution is to create a hash and store the number of matrices corresponding to the index (answer).
NOTE: You will have to use an array hash, not a map (stl) as it will take log(n) time and will not pass the time limit.
C++ CODE:
Link
Author: Naman Taneja
Tester: Prayank Mathur
Editorialist: Naman Taneja