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

calling all geniuses: N^3 is actually N^2 ?????????????
Автор TwentyOneHundredOrBust, история, 5 лет назад, По-английски

https://mirror.codeforces.com/contest/1237/submission/62742100

Looks N^3, but seems to be N^2 after constructing many cases. Any proofs/can you hack it?

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

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится -23 Проголосовать: не нравится

You can try this input:

2000
2000 0 0
1998 0 0
  ...
4 0 0
2 0 0
1 0 0
3 0 0
  ... 
1997 0 0
1999 0 0
→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +104 Проголосовать: не нравится

Something like this makes your algorithm work in $$$O(n^3)$$$ time. You need $$$O(n)$$$ points on each diagonal:

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    In contest I submitted the same idea but I was sorting first.

    my submission

    I tried (CUSTOM INVOCATION) it passed your testcase in 31ms, I also believe that it remains O(N^3). How it pass all testcases and your testcase ? mnbvmar

    → Ответить