TwentyOneHundredOrBust's blog

calling all geniuses: N^3 is actually N^2 ?????????????
By TwentyOneHundredOrBust, history, 7 years ago, In English

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?

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

»
7 years ago, hide # |
← Rev. 2  
Vote: I like it -23 Vote: I do not like it

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
→ Reply
»
7 years ago, hide # |
 
Vote: I like it +104 Vote: I do not like it

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

→ Reply