Runtime_terror_'s blog

What is randomization?
By Runtime_terror_, history, 3 years ago, In English

I am new to CP and I have seen comments from many experienced programmers about how they couldn't figure out the problem but got it accepted using randomization. Any information / link to blogs / tutorials about this technique would be helpful to me.

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

»
3 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

Say you have this problem — We have n children , each having a candy which can have 1 out of k flavours. Find a candy that is liked by atleast half of the children. This is a very stupid example, and it can be solved without randomisation, but it can be used to solve some very interesting problems ->https://codeforces.net/problemset/problem/1523/D
The idea is , we take a random flavour, and count its occurrences. If it is at least half, we found the answer. Let's say I repeat this 50 times, the probability of me not finding the answer will be 1/2^50, which is really low.
There are many other examples.....and often randomisation is not the expected solution. It is more of a hack. Randomly shuffling an array to find a construction that satisfies some conditions, randomly choosing points on a 2D plane that satisfy some conditions. The list is long.But........I haven't seen too many problems that actually "expect" a randomised solution. Usually it is used in a case like "Fuck it, 20 minutes left, lets code some randomised garbage" . Sometimes, that garbage actually passes : )

→ Reply