Блог пользователя YahiaBadr

God Of Matrices
Автор YahiaBadr, история, 6 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

This might Help

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

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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
→ Ответить