YahiaBadr's blog

God Of Matrices
By YahiaBadr, history, 6 years ago, In English

Here is te problem were it says that: just print YES if AxB=C where A,B,C are nxn matrices. so the apporoach was to multiply C and B w matrix D which it’s size is nx1 so the operiations could be faster AxBxD= CxD. My question comes here, while choosing the values D it must be choosed by math.random otherwise it will fail in one of tests. Could anyone say why?

  • Vote: I like it
  • +22
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How else would you choose the tests? It just might happen that you get unlucky and get a false positive (say, A * B and C share an element of their kernel, but are not equal).

→ Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

This might Help

https://en.wikipedia.org/wiki/Freivalds%27_algorithm

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I made the tests for this problem. There are tests against solutions that check only sums of rows and sums of columns (D consists of 1). The simpliest test is:

Spoiler
→ Reply