1
$\begingroup$

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In other words, return the result of expression (A x B) mod 10 == C.

For example:

$\qquad A = \begin{bmatrix} 0 & 5 & 8 \\ 1 & 4 & 9 \\ 2 & 3 & 3 \end{bmatrix}\qquad B = \begin{bmatrix} 3 & 5 & 0 \\ 1 & 2 & 6 \\ 3 & 7 & 0 \end{bmatrix}\qquad C = \begin{bmatrix} 9 & 6 & 0 \\ 4 & 6 & 4 \\ 8 & 7 & 8 \end{bmatrix}$

return: TRUE

If

$\qquad C = \begin{bmatrix} 1 & 6 & 0 \\ 4 & 6 & 4 \\ 8 & 7 & 8 \end{bmatrix}$

return: FALSE, since the element C(1, 1) must be 9.

Time limit is 1s, pretty strict. Please gives me some idea how to solve the problem efficiently; is it possible time $O(N^2)$?

$\endgroup$
  • $\begingroup$ Note that a time limit in seconds and $O(\dots)$ are incomparable measures, with the answers probably wildly different. What is your priority? (For example, a time limit for any fixed $N$ can be realised by employing recursive matrix multiplication algorithms and storing all (preprocessed) products up to a certain size.) $\endgroup$ – Raphael Aug 12 '14 at 6:06
  • 2
    $\begingroup$ Have you considered Freivalds' algorithm? It's probabilistic but will give the right answer with probability at least $1-2^{-k}$ in time $O(kn^2)$. I'm not sure how good it is, in practice. $\endgroup$ – David Richerby Aug 12 '14 at 11:51
  • 1
    $\begingroup$ @Raphael $k=10$ gives an error rate of about one in a thousand. That's a lot higher than the probability of the CPU randomly flipping a bit. But, yes, you don't need a very big $k$ to get reliability that's indistinguishable from perfect. $\endgroup$ – David Richerby Aug 12 '14 at 13:48
  • 1
    $\begingroup$ @Raphael I don't know so I asked a question about it! $\endgroup$ – David Richerby Aug 12 '14 at 15:20
  • 1
    $\begingroup$ (I should add that the bound mentioned by @DavidRicherby holds if and only if you have a proper source of (pseudo) random numbers. If not, arbitrarily bad stuff can happen.) $\endgroup$ – Raphael Aug 12 '14 at 19:10
0
$\begingroup$

I got Accepted by using Freivald's algorithm as suggested by @David Richerby. Thank you very much !

I have not tested the brute-force solution using Coppersmith-Winograd algorithm yet. Will report in a couple of days, by the way I think it might not get Accepted but possibly will gain a fairly amount of points.

For those who want to check your implementation, submit your code on http://vn.spoj.com/problems/VMATRIX/. The problem statement is in Vietnamese, so here is the short description of input format:

  • First line is number of testcase (the example gives 2 testcases)
  • For each testcase:
  • the first line is size of 3 matrices, N. In 20% testcase N <= 100.
  • next N * N lines: matrix A
  • next N * N lines: matrix B
  • next N * N lines: matrix C

Output: YES or NO for the result.

$\endgroup$
  • 2
    $\begingroup$ As I commented below mohaned's answer, Coppersmith–Winograd isn't competitive for the sorts of matrices you're dealing with. For the sizes of matrices you're dealing with, the naive $O(n^3)$ algorithm with a few optimizations tends to be faster than any of the fancy, asymptotically faster algorithms. $\endgroup$ – David Richerby Aug 12 '14 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.