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.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3843 |
| 2 | jiangly | 3705 |
| 3 | Benq | 3628 |
| 4 | orzdevinwang | 3571 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | jqdai0815 | 3530 |
| 8 | ecnerwala | 3499 |
| 9 | gyh20 | 3447 |
| 10 | Rebelz | 3409 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 154 |
| 5 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 145 |
| 10 | pajenegod | 144 |
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 : )