The__Knight's blog

Is Monte Carlo Actually Viable in Official Rounds?
By The__Knight, history, 3 months ago, In English

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..

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

cf problems often require a globally optimal answer. monte carlo methods might get stuck in a local minimum

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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...

      → Reply
  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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..

    → Reply
»
3 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Not monte-carlo but I remember a matroid intersection problem with low constraints that people managed to AC using simulated annealing.

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Yes, I remember this problem, which had a randomized solution: https://codeforces.me/contest/2149/problem/G

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply