Блог пользователя Petr

A 1:1 week
Автор Petr, история, 4 месяца назад, По-английски

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

  • Проголосовать: нравится
  • +108
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 месяца назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +33 Проголосовать: не нравится

    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.

    → Ответить