ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1578. Mammoth Hunt

Are there beautifull solution?
Posted by Joseph Puh the Battle Bear 8 Oct 2011 15:07
Are there beautifull solution? The one other from bruteforce
Re: Are there beautifull solution?
Posted by bsu.mmf.team 9 Oct 2011 04:33
Yes, there are exists one very beautiful O(N^2) solution. But the practical complexity of this algo is much less :)
Re: Are there beautifull solution?
Posted by Harkonnen 7 Aug 2022 12:22
There is also almost O(N) solution, but that's due to weak tests (probably there is a proof that N*log(N)) is enough. Just go forward and swap vertices if they form non-acute angle (that's WA14). Then go backward and do the same (that's WA22). Then do that in a loop 10 times back and forth, and get weak AC :)

P.S: Even 2 such passes is enough (no proof, just such tests). And I think there is a proof that N passes is always enough.

Edited by author 07.08.2022 12:28

Edited by author 07.08.2022 12:30