|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Are there beautifull solution? | Joseph Puh the Battle Bear | 1578. Охота на мамонта | 7 авг 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. Охота на мамонта | 11 июн 2022 17:48 | 1 | Proof andreyDagger 11 июн 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. Охота на мамонта | 11 июн 2022 17:40 | 1 | WA15 andreyDagger 11 июн 2022 17:40 I had X[2000], then I changed it to X[2002] and got AC | | Hint | Md sabbir Rahman | 1578. Охота на мамонта | 14 ноя 2018 20:31 | 1 | Hint Md sabbir Rahman 14 ноя 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. Охота на мамонта | 4 апр 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. Охота на мамонта | 5 июл 2013 18:56 | 1 | Почему в условии задачи сказано, что начальная и конечная точки маршрута фиксированы, а в примерах конечные точки получаются разными?
Edited by author 08.07.2013 01:51 | | WA# 14 | IgorKoval [PskovSU] | 1578. Охота на мамонта | 21 апр 2013 03:13 | 1 | WA# 14 IgorKoval [PskovSU] 21 апр 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. Охота на мамонта | 11 окт 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. Охота на мамонта | 13 май 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. |
|
|
|
