### Runtime_terror_'s blog

By Runtime_terror_, history, 2 years ago,

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.

• +28

 » 2 years ago, # | ← Rev. 2 →   +24 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.com/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 : )