Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Useful test | hadooken | 1181. Разрезание окрашенного многоугольника | 18 дек 2019 11:06 | 1 |
10 RGRGRBGBGB Possible answer: 7 4 6 3 6 2 6 1 6 1 7 1 8 1 9 |
Why always WA4? | Combatcook | 1181. Разрезание окрашенного многоугольника | 25 апр 2016 19:01 | 1 |
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 |
I have O(n) | lallala | 1181. Разрезание окрашенного многоугольника | 12 фев 2016 16:27 | 1 |
|
WA test #5 | Blum | 1181. Разрезание окрашенного многоугольника | 6 янв 2016 11:55 | 4 |
Can anyone give me some tricky tests? 5 RGRBG 7 RBGBRGB 6 RGBGRB 4 RRBG |
Idea | Felix_Mate | 1181. Разрезание окрашенного многоугольника | 2 ноя 2015 17:44 | 2 |
Idea Felix_Mate 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. Good hint! Furthermore, it can be proved that if it is not 'obviously impossible', then there will always be a solution. |
Why wa6? | uuu | 1181. Разрезание окрашенного многоугольника | 22 авг 2010 10:54 | 1 |
Is there some special inputs in test6? |
Hint | Mukhametianov Den [USU] | 1181. Разрезание окрашенного многоугольника | 14 июл 2010 02:12 | 1 |
Hint Mukhametianov Den [USU] 14 июл 2010 02:12 One stack is bad. But N stacks... =) |
DP for O(n^3) | [Ural SU] GetTester | 1181. Разрезание окрашенного многоугольника | 17 мар 2010 21:32 | 3 |
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. ) 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. It is not O(n^3): the expected number of tests for each sub-interval is 2 and thus DP is O(n^2). |
O(n^3) gets TLE. Can anyone give me a better hint? | asif | 1181. Разрезание окрашенного многоугольника | 17 мар 2010 20:04 | 3 |
My mail: bsc98001@yahoo.com > 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) What seems to be O(n^3) DP is AC as far as you remember to use "break" |
Why do I always WAs at test #10 | Shellux | 1181. Разрезание окрашенного многоугольника | 27 апр 2009 17:09 | 1 |
?? who can help me? thanks a lot. |
Wrong limitations | Fyodor Menshikov | 1181. Разрезание окрашенного многоугольника | 25 дек 2008 21:21 | 4 |
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. 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! 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. 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. |
Help me please!!!! I very need! | Jack | 1181. Разрезание окрашенного многоугольника | 6 июл 2007 16:18 | 1 |
Please,if you can,give me on C++ this programm #1181!!!I very need!Thank you very much!!! |
Problem 1181 "Cutting a painted polygon" is under investigation (+) | Sandro (USU) | 1181. Разрезание окрашенного многоугольника | 18 янв 2007 20:36 | 2 |
During first rejudge 37 authors lost AC. Tests and validator will be updated soon. Edited by author 10.01.2007 21:32 12 more submits lost AC. Thanks to Alexander Toropov for new validator and tests! |
One question | Samsonov Alex [SESC USU] | 1181. Разрезание окрашенного многоугольника | 5 окт 2006 19:06 | 3 |
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")? There is no "0" at all! Because all these situation are discribed in the task!)) |
I have some questions...... | hello | 1181. Разрезание окрашенного многоугольника | 23 июн 2005 01:44 | 3 |
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 ? Everything is possible! Just think better. Solution is 0. There is edge with 2 blue vertices: BGBGR[BB]GRG |
if there are sevaral ways,must i descript all of them?or an arbitrary one? | wangzhipeng | 1181. Разрезание окрашенного многоугольника | 31 янв 2005 15:56 | 2 |
|
For those who need a hint... 8-) | Alex[LSD] | 1181. Разрезание окрашенного многоугольника | 6 июн 2003 12:11 | 1 |
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-) |