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)$?

Improve this question
$\endgroup$
8
  • $\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, 2014 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, 2014 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, 2014 at 13:48
  • 1
    $\begingroup$ @Raphael I don't know so I asked a question about it! $\endgroup$
    – David Richerby
    Aug 12, 2014 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, 2014 at 19:10

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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, 2014 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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