Petr's blog

By Petr, history, 7 months ago, In English
  • Vote: I like it
  • +108
  • Vote: I do not like it

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

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