Petr's blog

A 1:1 week
By Petr, history, 11 months ago, In English

https://blog.mitrichev.ch/2024/01/a-11-week.html

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

»
11 months ago, # |
  Vote: I like it +14 Vote: I do not like it

If I remember corretly, the mentioned problem from Run Twice contest appeared at Petrozavodsk summer camp 2022. My solution is to check whether the input graph has a $$$4$$$-clique: a random graph should not have it.

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

    Nice! This solution feels a bit borderline to me: the graph has 1% of all edges when m=5000, so roughly speaking the probability of having a 4-clique is C(1000,4)*0.01^6 ~= 1000^4/24/100^6 = 1/24, so it might or might not appear in the ~100 testcases, not all of which have m=5000.

    → Reply