How to calculate the expected number of operations of the editorial solution for 444B DZY Loves FFT?

Правка en2, от oos1111, 2018-02-28 16:48:30

I got stuck at the problem 444B DZY Loves FFT and I read the editorial.
And I really don't understand how to calculate the expected time complexity of the whole algorithm. How to prove that the worst expected number of operations is around ten million? Please help!

Теги probability

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский oos1111 2018-02-28 16:48:30 0 (published)
en1 Английский oos1111 2018-02-28 16:47:42 461 Initial revision (saved to drafts)