After diving more and more into randomized algorithms(and teeny-weeny bit into the simulation of ray tracing) I have realised the unfathomable potential of Monte-Carlo methods (if used properly) . It can help break down extremely complex constructive algorithms into simple random sampling.
However, considering the time limit of 1-2 secs on most of the problems on CF and AtCoder it feels impossible to simulate Monte Carlo without facing a TLE or a WA (if the ans involves exact floating points).
Is there any way to implement a time bound randomised search and bypass the natural time based restrictions and is it feasible during official rounds?
To those who help, ありがとうございます in advance..
cf problems often require a globally optimal answer. monte carlo methods might get stuck in a local minimum
Two icpc problems come to mind https://codeforces.me/contest/1773/problem/A https://codeforces.me/gym/104848/problem/D (Second one also has a deterministic solution). I suppose cf rounds also had problems where you can do something randomly a few times and you are basically guaranteed to succeed quickly enough, but I can't remember anything.
If what you're asking is can you cheese a lot of problems with random approach, when it's unintended, then the answer is no.
Yes... I actually meant it for constructive algos for which the exact construction does not come to mind, but we can treat it as a deterministic randomisation of trails via which we can find out the limiting factor that confirms our choice...
There was also this problem where randomisation over the three choices of final values after finding out the prime factors and then applying Monte Carlo for about 20 times would give the right prime factor..
Not monte-carlo but I remember a matroid intersection problem with low constraints that people managed to AC using simulated annealing.
Is it this one? https://codeforces.me/problemset/problem/1556/H
Yes, check this comment out https://codeforces.me/blog/entry/94384#comment-834678
Yes, I remember this problem, which had a randomized solution: https://codeforces.me/contest/2149/problem/G
2074E - Empty Triangle
2246E - lce4113 and Security Game
Both these problems strictly require randomization, most problems that strictly require randomization are interactive
Plenty of problems also have an alternative or primary randomized solution