| ENG RUS | Timus Online Judge |
Обсуждение задачи 1181. Разрезание окрашенного многоугольникаhadooken Useful test // Задача 1181. Разрезание окрашенного многоугольника 18 дек 2019 11:06 10 RGRGRBGBGB Possible answer: 7 4 6 3 6 2 6 1 6 1 7 1 8 1 9 Combatcook Why always WA4? // Задача 1181. Разрезание окрашенного многоугольника 25 апр 2016 19:01 My program passed all tests, which I found here or invented myself, but I have WA4. Can anybody help me find a mistake or give some special tests? I'd be very grateful... -- P.S. Already solved. This test helped me: 5 RGBRB Edited by author 27.04.2016 20:49 lallala I have O(n) // Задача 1181. Разрезание окрашенного многоугольника 12 фев 2016 16:27 Blum WA test #5 [3] // Задача 1181. Разрезание окрашенного многоугольника 3 ноя 2007 23:22 Can anyone give me some tricky tests? Rumter (2) Re: WA test #5 [2] // Задача 1181. Разрезание окрашенного многоугольника 12 июл 2008 15:35 5 RGRBG 7 RBGBRGB 6 RGBGRB 4 RRBG Roks Re: WA test #5 [1] // Задача 1181. Разрезание окрашенного многоугольника 26 сен 2008 05:13 last example is wrong Alex Mullabaev'` Re: WA test #5 // Задача 1181. Разрезание окрашенного многоугольника 6 янв 2016 11:55 10 RGBGBGBGBG Felix_Mate Idea [1] // Задача 1181. Разрезание окрашенного многоугольника 21 авг 2015 09:56 I got AC with O(N*N); Idea: use mathematical induction and prove that solution exist always. Induction gives a solution. wangbicheng1 Re: Idea // Задача 1181. Разрезание окрашенного многоугольника 2 ноя 2015 17:44 Good hint! Furthermore, it can be proved that if it is not 'obviously impossible', then there will always be a solution. uuu Why wa6? // Задача 1181. Разрезание окрашенного многоугольника 22 авг 2010 10:54 Is there some special inputs in test6? Mukhametianov Den [USU] Hint // Задача 1181. Разрезание окрашенного многоугольника 14 июл 2010 02:12 One stack is bad. But N stacks... =) [Ural SU] GetTester DP for O(n^3) [2] // Задача 1181. Разрезание окрашенного многоугольника 6 ноя 2009 14:02 I got AC with O(n^3) solution, based on DP. I suppose, that testcases are too weak. Anyway, I think, that it's not normal to get AC for O(n^3) solution. ) tiancaihb Re: DP for O(n^3) [1] // Задача 1181. Разрезание окрашенного многоугольника 7 ноя 2009 04:15 My solution is n3, but it doesn't have to check all posibilities. Some part of array f[][] is never used. Besides, I don't know a better way. ASK Re: DP for O(n^3) // Задача 1181. Разрезание окрашенного многоугольника 17 мар 2010 21:32 It is not O(n^3): the expected number of tests for each sub-interval is 2 and thus DP is O(n^2). asif O(n^3) gets TLE. Can anyone give me a better hint? [2] // Задача 1181. Разрезание окрашенного многоугольника 23 фев 2002 23:52 My mail: bsc98001@yahoo.com Gheorghe Stefan Re: O(n^3) gets TLE. Can anyone give me a better hint? [1] // Задача 1181. Разрезание окрашенного многоугольника 24 ноя 2002 21:17 > My mail: bsc98001@yahoo.com Try to eliminate all RGB consecutive but be aware to not "destroy" a rare node (i.e. eliminate them in descending order) ASK Re: O(n^3) gets TLE. Can anyone give me a better hint? // Задача 1181. Разрезание окрашенного многоугольника 17 мар 2010 20:04 What seems to be O(n^3) DP is AC as far as you remember to use "break" Shellux Why do I always WAs at test #10 // Задача 1181. Разрезание окрашенного многоугольника 27 апр 2009 17:09 ?? who can help me? thanks a lot. Fyodor Menshikov Wrong limitations [3] // Задача 1181. Разрезание окрашенного многоугольника 25 дек 2008 12:08 From moment of creation of this problem (16 Feb 2002) and till 6 Jun 2006 there was no solution that uses more than 1Mb of memory. I think that original ML was 1 Mb. Now problem has ML 16 Mb, and there are ~40 solutions (<10% of all) that use more than 1 Mb. Is it possible to lower memory limit of this problem to 1 Mb? 1Mb does not allow DP table of size N*N/2 of 2-byte integers. Vedernikoff Sergey (HSE: EconomicsForever!) Re: Wrong limitations [2] // Задача 1181. Разрезание окрашенного многоугольника 25 дек 2008 18:15 Following you logic, let's instead increase N to, say, 5000. It's not correct to change rules of the game after they were established and some authors ACed solutions under new limitations! Fyodor Menshikov Re: Wrong limitations // Задача 1181. Разрезание окрашенного многоугольника 25 дек 2008 21:09 Beauty of this problem in that it looks like trivial DP but can be solved using original algorithm much more effective. There is no much sense in having one more standard DP problem. But there is much more benefit for solvers in creating absolutely new algorithm and obtaining new knowledge. I think that current state is fault of people who 2 years ago increased ML for almost all problems not thinking of side effects. As result some problems become meaningless and silly. I think that 2 years is not so long time, and its possible to return meaning to problems that lost it after ML increase. Fyodor Menshikov Re: Wrong limitations // Задача 1181. Разрезание окрашенного многоугольника 25 дек 2008 21:21 Vedernikoff Sergey (HSE: EconomicsForever!) писал(a) 25 декабря 2008 18:15 Following you logic, let's instead increase N to, say, 5000. I considered this idea. To create new problem with the same statement and greater limitations. But after problem statistics analysis (<10% solutions would fail that new problem) I came to conclusion that it would be better to remove AC from 10% than force 90% to submit identical solutions to two problems. Jack Help me please!!!! I very need! // Задача 1181. Разрезание окрашенного многоугольника 6 июл 2007 16:18 Please,if you can,give me on C++ this programm #1181!!!I very need!Thank you very much!!! Sandro (USU) Problem 1181 "Cutting a painted polygon" is under investigation (+) [1] // Задача 1181. Разрезание окрашенного многоугольника 10 янв 2007 21:31 During first rejudge 37 authors lost AC. Tests and validator will be updated soon. Edited by author 10.01.2007 21:32 Sandro (USU) Tests are updated (+) // Задача 1181. Разрезание окрашенного многоугольника 18 янв 2007 20:36 12 more submits lost AC. Thanks to Alexander Toropov for new validator and tests! Samsonov Alex [SESC USU] One question [2] // Задача 1181. Разрезание окрашенного многоугольника 10 июн 2005 17:45 Is that true that we should output "0" if: 1) There are less than three colors in the polygon. 2) Vertex of one color is followed by the vertex of the same color (like "GG")? Tintor Marko Re: One question // Задача 1181. Разрезание окрашенного многоугольника 23 июн 2005 01:36 Yes AlexF [USTU] Re: One question // Задача 1181. Разрезание окрашенного многоугольника 5 окт 2006 19:06 There is no "0" at all! Because all these situation are discribed in the task!)) hello I have some questions...... [2] // Задача 1181. Разрезание окрашенного многоугольника 14 май 2004 18:00 I got WA all the time. here is one test : 10 BGBGRBBGRG I think the answer is 0 . But the AC solution said it's possible . I'm puzzle. Who can tell me why ? Ярославцев Григорий Re: I have some questions...... [1] // Задача 1181. Разрезание окрашенного многоугольника 14 май 2004 21:10 Everything is possible! Just think better. Tintor Marko Re: I have some questions...... // Задача 1181. Разрезание окрашенного многоугольника 23 июн 2005 01:44 Solution is 0. There is edge with 2 blue vertices: BGBGR[BB]GRG wangzhipeng if there are sevaral ways,must i descript all of them?or an arbitrary one? [1] // Задача 1181. Разрезание окрашенного многоугольника 31 янв 2005 13:39 thanks a lot! Dmitry 'Diman_YES' Kovalioff Quote: "If there are several possible cuttings that satisfy the requirements you may output any of them." (-) // Задача 1181. Разрезание окрашенного многоугольника 31 янв 2005 15:56 Alex[LSD] For those who need a hint... 8-) // Задача 1181. Разрезание окрашенного многоугольника 6 июн 2003 12:11 This problem is about invariant(some condition that remains true in spite of any modification). You need to pick diagonals one by one,just making sure that the "condition" is still true... I hope this helps you think in the right direction 8-)
|