Problems which are made easier by Randomised algorithms

Правка en2, от lrohit678, 2024-11-11 04:08:20

Hi CodeForces, Currently I am studying Randomised algorithms for my Theoretical Computer science course. Our professor mentioned that there used to be many problems prior which had a randomised solution in polynomial time but not a known deterministic solution in polynomial time, but there aren’t that many problems of this type left now.

I wanted to know are there any Competitive programming problems which have a randomised algorithm solution and have a much worse deterministic solution in terms of time complexity or implementation.

Note our course mostly focuses on the theoretical aspects, so it would gave me a better intuition about randomised algorithms if I am able to do such a problem.

Теги randomization, algorithms

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский lrohit678 2024-11-11 04:08:20 21 Tiny change: ' solution but not a' -> ' solution in polynomial time but not a'
en1 Английский lrohit678 2024-11-11 04:04:37 745 Initial revision (published)