Checking the server
You have handed the multiplication of two matrices to an outside server, and it has returned the result. The server sometimes errs, spoiling one or two numbers, and maliciously so: in a way that neither row sums nor column sums give the error away. Recomputing the product is too slow. Check whether the result is right.
Input
The first line holds n (1 ≤ n ≤ 300). Then come three n × n matrices, A, B and C, each as n lines of n integers. The elements of A and B are from 0 to 100, the elements of C from −109 to 109.
Output
YES if A·B = C, otherwise NO.
Recomputing by the definition, 2.7·107 multiplications with n = 300, will not fit in the time limit in Python.
Examples
Example 1
2 1 2 3 4 5 6 7 8 19 22 43 50
YES
Example 2
2 1 2 3 4 5 6 7 8 20 21 43 50
NO
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Recomputing A·B is n³ multiplications. And what does multiplying a matrix by a vector cost? If AB = C, then for any vector r, A(Br) = Cr. Which vector should be taken?
2Hint 2
A vector of all ones compares row sums, and the server uses this: it spoils two cells of one row by +e and −e. Any vector chosen in advance can be fooled the same way. What about a random one?
3The idea
Freivalds’ check: a random vector r of zeros and ones, compare A(Br) with Cr: three matrix-by-vector multiplications, 3n² operations. If AB = C, the equality always holds. If not, then, as proved in the article, the check is fooled with probability at most ½, whatever the damage: for a non-zero element dij of the difference D = AB − C, at most one of the two values of rj makes (Dr)i zero. Repeating the check 30 times with independent vectors, we err with probability at most 2−30 ≈ 10−9.
The server does not know our random numbers, so no sly damage will help it. Against the vector of ones a pair +e, −e in one row is enough (the second example), and against checking both rows and columns a “rectangle” +e, −e, −e, +e in two rows and two columns (the seventh test).
4Walkthrough
Read the three matrices; 30 times: a random r, the vector Br, then for each row compare Ai·(Br) and Ci·r; at the first discrepancy, NO. If all the checks passed, YES. In Python dot products are fastest as sum(map(mul, row, vector)).
The third and fourth tests are the link graph of three of this site’s textbooks: A = B is the link matrix of 202 pages, and C = A·A the number of two-click paths between them; in the fourth one of these numbers is increased and the neighbouring one in the same row decreased.
4+Solution
5Complexity
O(kn²) with k = 30 checks, against O(n³) for recomputing.
6Common mistakes
- Row or column sums. This is a check with one fixed vector, and pairs of errors with opposite signs fool it.
- One random check. It misses an error with probability up to ½; on ten tests with errors that is almost certain failure.
- Recomputing the product. Correct, but 2.7·107 multiplications are tens of seconds in Python.