Can correct randomized solution fail?

Правка en1, от antontrygubO_o, 2019-01-25 03:44:24

I am just curious.

Suppose some problem has a randomized solution which fails with probability at most . If it has, say, 100 tests, the probability of failing some of them is about . Therefore, once in 104 it may happen that correct randomized solution doesn't pass.

Has anyone experienced anything like that? Maybe even the exact solution that didn't pass got AC after submitting it the second time? Or am I getting something wrong?

Теги #randomisation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский antontrygubO_o 2019-01-25 03:48:18 519 Первая редакция перевода на Русский
en1 Английский antontrygubO_o 2019-01-25 03:44:24 512 Initial revision (published)