| ENG RUS | Timus Online Judge |
Discussion of Problem 1065. FrontierBigPolandBro If you get WA, try this test too // Problem 1065. Frontier 23 Sep 2020 00:06 6 1 1 0 0 4 0 6 1 10 2 6 2 4 1 5 answer is 8 Cuac!++ efficient idea [2] // Problem 1065. Frontier 7 Apr 2008 07:07 Hi!, i have gotten AC in this problem, but i have 0.093 secs, and im not well ranked on the best solutions table, i think the difficult part of this problem is to see which triangle have historical monuments inside, i did it with an O ( logM * M * N ) approach, do anybody have something better? i really would like to know how to get 0.015 secs or less. Thank you very much! Eric ( Cuac!++ ). hedrok Re: efficient idea [1] // Problem 1065. Frontier 9 Apr 2008 00:09 Hi. I've got 0.015 secs. http://acm.timus.ru/status.aspx?author=34678&num=1065&refresh=no My algo woks O(M*N + N^3). Here is my idea: i don't look which triangles contain historical monuments. i calculate which sequences of vertexes can we delete and what length we win if we do so. Then i find optimal way of selecting these sequences of vertexes. Do you need more details? ASK Re: efficient idea // Problem 1065. Frontier 24 Apr 2018 00:12 Nope, it is at least O(M*N*log(N) + N^3), but with N~50 it is not noticeable. For each tower check how many towers can be skipped, that is for each possible skipping length check if there are monuments ccw to the chord: O(M*N^2), but can be O(M*N*log(N)) with binary search. For each length and each start calculate minimal perimeter on the way from start to start+length trying all intermediary towers: O(N^3). For each triple of towers that form a triangle, sum minimal perimeters and find the global minimum: O(N^3). Grebnov Ilya[ISPU] Why I got wrong answer? Please help me! [2] // Problem 1065. Frontier 7 Apr 2003 15:26 [code was deleted] Edited by moderator 22.04.2004 00:58 Dmitry 'Diman_YES' Kovalioff A test for you (+) [1] // Problem 1065. Frontier 7 Apr 2003 16:07 5 2 8 9 0 -7 -8 -7 -8 1 -8 9 -4 -3 -1 -5 Your program outputs 37.20 but the answer is 51.78 yaniel Re: A test for you (+) // Problem 1065. Frontier 30 Jan 2011 13:01 Edited by author 13.05.2014 12:53 Tiberiu Danet If you get WA, try this test case [11] // Problem 1065. Frontier 2 Mar 2003 22:22 Try this test case: 4 0 0 0 0 3 3 0 2 0 The answer should be 8.61. You have to find a solution with non-zero area, but the original polygon's vertices may lie on the same line. lzperfect Re: If you get WA, try this test case // Problem 1065. Frontier 2 May 2004 11:49 Thanks for your test,I Aced my program 198808xc Re: If you get WA, try this test case // Problem 1065. Frontier 23 Feb 2005 13:08 Thanks very much. With the help of your TestData, I got ACed. Kit Re: If you get WA, try this test case // Problem 1065. Frontier 31 Mar 2005 19:59 Thank you very, very, very much! boaz Re: If you get WA, try this test case // Problem 1065. Frontier 13 Oct 2005 14:28 Thank you very, very, very much!!! wfhhzyh Re: If you get WA, try this test case // Problem 1065. Frontier 6 Jul 2007 19:36 Tanks a lot! EA Re: If you get WA, try this test case // Problem 1065. Frontier 7 Nov 2007 00:18 Thank you. :) fengyi Re: If you get WA, try this test case [4] // Problem 1065. Frontier 15 May 2008 10:42 what a good test!! thank you very much Dmitry "Logam" Kobelev [TSOGU] Re: If you get WA, try this test case [3] // Problem 1065. Frontier 27 Aug 2008 21:26 So many happy people there), but I still wa4 :P Will someone ACer put here correct answer for this test? 13 3 -5 3 -3 6 0 7 4 6 7 5 7 4 7 3 7 2 5 -3 4 -3 3 -3 -2 -3 -5 -2 3 3 5 0 -1 1 My prog says 30.20 hedrok (ONPU) Re: If you get WA, try this test case // Problem 1065. Frontier 2 Sep 2008 18:46 Your answer is correct. Just a test: 4 2 0 2 1 0 0 -2 -1 0 0 1 0 -1 Answer: 8.94 wr(wrbuaa2005@126.com) Re: If you get WA, try this test case [1] // Problem 1065. Frontier 10 Sep 2008 06:59 If you want some test data, send E-mail to me, I can help you. Глащенко Никита Re: If you get WA, try this test case // Problem 1065. Frontier 20 Jul 2009 15:54 Test for WA#4 6 1 -1 -1 -4 0 -1 1 1 1 4 0 1 -1 0 0 Answer 8.00
|