| ENG RUS | Timus Online Judge |
Discussion of Problem 1578. Mammoth HuntJoseph Puh the Battle Bear Are there beautifull solution? [2] // Problem 1578. Mammoth Hunt 8 Oct 2011 15:07 Are there beautifull solution? The one other from bruteforce bsu.mmf.team Re: Are there beautifull solution? [1] // Problem 1578. Mammoth Hunt 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 :) Harkonnen Re: Are there beautifull solution? // Problem 1578. Mammoth Hunt 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 andreyDagger Proof // Problem 1578. Mammoth Hunt 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 andreyDagger WA15 // Problem 1578. Mammoth Hunt 11 Jun 2022 17:40 I had X[2000], then I changed it to X[2002] and got AC Md sabbir Rahman Hint // Problem 1578. Mammoth Hunt 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 ? melkiy Tests needed [3] // Problem 1578. Mammoth Hunt 26 Oct 2009 18:48 Would someone be so kind to give any tricky tests? I have WA#11 :( unlucky [Vologda SPU] Re: Tests needed [2] // Problem 1578. Mammoth Hunt 6 Feb 2010 02:23 My solution get WA 11 too. It work's incorrect at test 2 0 0 3 0 3 2 4 5 Astekinane Re: Tests needed [1] // Problem 1578. Mammoth Hunt 17 Oct 2011 21:06 Ans "NO"? ASK Re: Tests needed // Problem 1578. Mammoth Hunt 4 Apr 2018 01:13 NO is impossible vb002 Неправильная формулировка? // Problem 1578. Mammoth Hunt 5 Jul 2013 18:56 Почему в условии задачи сказано, что начальная и конечная точки маршрута фиксированы, а в примерах конечные точки получаются разными? Edited by author 08.07.2013 01:51 IgorKoval [PskovSU] WA# 14 // Problem 1578. Mammoth Hunt 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 Korduban [Kiev] clarification [5] // Problem 1578. Mammoth Hunt 13 Oct 2007 15:00 Angles must be strogly acute? I.e., right angles (pi/2) are restricted? Vedernikoff Sergey Re: clarification [4] // Problem 1578. Mammoth Hunt 14 Oct 2007 16:25 See first sample. Ostap Korkuna (Lviv NU) There is no right angle in the answer for the first sample, so it tells nothing... (-) [3] // Problem 1578. Mammoth Hunt 20 Oct 2007 16:36 Vedernikoff Sergey Re: There is no right angle in the answer for the first sample, so it tells nothing... (-) [2] // Problem 1578. Mammoth Hunt 28 Oct 2007 19:58 It is now absent, but before the sample was corrected there was right angle... Denis Koshman Re: There is no right angle in the answer for the first sample, so it tells nothing... (-) [1] // Problem 1578. Mammoth Hunt 12 Aug 2008 11:28 My AC solution rejects right angles -XraY- Re: There is no right angle in the answer for the first sample, so it tells nothing... (-) // Problem 1578. Mammoth Hunt 11 Oct 2012 16:10 I got AC when I deleted right angles. I had WA before that. VasilySlesarev How to solve? [5] // Problem 1578. Mammoth Hunt 8 May 2009 16:10 I can suggest only bruteforce. Edited by author 08.05.2009 16:12 Vedernikoff Sergey (HSE: АОП) Re: How to solve? [4] // Problem 1578. Mammoth Hunt 8 May 2009 16:39 If you can suggest - then try! =) VasilySlesarev Re: How to solve? [3] // Problem 1578. Mammoth Hunt 8 May 2009 19:54 I think, it will be TLE. Vedernikoff Sergey (HSE: АОП) Re: How to solve? // Problem 1578. Mammoth Hunt 8 May 2009 20:52 Sometimes in sportcoding it's better not to think =) Samsonov Alex [USU] Re: How to solve? [1] // Problem 1578. Mammoth Hunt 10 May 2009 00:30 This problem has elegant solution which is very easy to code. Try to find it. VasilySlesarev Re: How to solve? // Problem 1578. Mammoth Hunt 13 May 2009 06:00 Thank you very much. I have found the solution. This problem is beautiful.
|