lrohit678's blog

By lrohit678, history, 2 weeks ago, In English

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.

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by lrohit678 (previous revision, new revision, compare).

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.me/contest/2014/problem/H

This is a recent problem, the idea is pretty trivial, there is a deterministic solution using Mo's algorithm, however, it can also be done using xor hashing