|
|
Show all threads Hide all threads Show all messages Hide all messages | Are there beautifull solution? | Joseph Puh the Battle Bear | 1578. Mammoth Hunt | 7 Aug 2022 12:22 | 3 | Are there beautifull solution? The one other from bruteforce Yes, there are exists one very beautiful O(N^2) solution. But the practical complexity of this algo is much less :) 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 | Proof | andreyDagger | 1578. Mammoth Hunt | 11 Jun 2022 17:48 | 1 | Proof andreyDagger 11 Jun 2022 17:48 Why can we always choose the farthest point? Suppose the opposite. Let we have 3 adjacent points in our way, which make obtuse angle. Let's call them A, B and C. angle ABC is obtuse, that means that |AC|>|AB| and |AC|>|BC|. But that's impossible because our algorithm chooses the farthest point, but B is not the farthest, C is further than B. Contradiction. Edited by author 11.06.2022 17:49 Edited by author 11.06.2022 17:49 | WA15 | andreyDagger | 1578. Mammoth Hunt | 11 Jun 2022 17:40 | 1 | WA15 andreyDagger 11 Jun 2022 17:40 I had X[2000], then I changed it to X[2002] and got AC | Hint | Md sabbir Rahman | 1578. Mammoth Hunt | 14 Nov 2018 20:31 | 1 | Hint Md sabbir Rahman 14 Nov 2018 20:31 If you're stuck think like this, having a directed segment AB, you just need a C among the remaining points s.t. <CBA is acute. Fixing A, is there a way to choose B such that any C among remaining will form acute <CBA ? | Tests needed | melkiy | 1578. Mammoth Hunt | 4 Apr 2018 01:13 | 4 | Would someone be so kind to give any tricky tests? I have WA#11 :( My solution get WA 11 too. It work's incorrect at test 2 0 0 3 0 3 2 4 5 | Неправильная формулировка? | vb002 | 1578. Mammoth Hunt | 5 Jul 2013 18:56 | 1 | Почему в условии задачи сказано, что начальная и конечная точки маршрута фиксированы, а в примерах конечные точки получаются разными? Edited by author 08.07.2013 01:51 | WA# 14 | IgorKoval [PskovSU] | 1578. Mammoth Hunt | 21 Apr 2013 03:13 | 1 | WA# 14 IgorKoval [PskovSU] 21 Apr 2013 03:13 If you get WA# 14 this test maybe help you: 2 0 1 1 0 1 1 2 1 answer: YES 1 4 2 3 | clarification | Korduban [Kiev] | 1578. Mammoth Hunt | 11 Oct 2012 16:10 | 6 | Angles must be strogly acute? I.e., right angles (pi/2) are restricted? It is now absent, but before the sample was corrected there was right angle... My AC solution rejects right angles I got AC when I deleted right angles. I had WA before that. | How to solve? | VasilySlesarev | 1578. Mammoth Hunt | 13 May 2009 06:00 | 6 | I can suggest only bruteforce. Edited by author 08.05.2009 16:12 If you can suggest - then try! =) Sometimes in sportcoding it's better not to think =) This problem has elegant solution which is very easy to code. Try to find it. Thank you very much. I have found the solution. This problem is beautiful. |
|
|
|