| Show all threads Hide all threads Show all messages Hide all messages |
| Useful test | hadooken | 1181. Cutting a Painted Polygon | 18 Dec 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. Cutting a Painted Polygon | 25 Apr 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. Cutting a Painted Polygon | 12 Feb 2016 16:27 | 1 |
|
| WA test #5 | Blum | 1181. Cutting a Painted Polygon | 6 Jan 2016 11:55 | 4 |
Can anyone give me some tricky tests? 5
RGRBG
7
RBGBRGB
6
RGBGRB
4
RRBG |
| Idea | Felix_Mate | 1181. Cutting a Painted Polygon | 2 Nov 2015 17:44 | 2 |
Idea Felix_Mate 21 Aug 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. Cutting a Painted Polygon | 22 Aug 2010 10:54 | 1 |
Is there some special inputs in test6? |
| Hint | Mukhametianov Den [USU] | 1181. Cutting a Painted Polygon | 14 Jul 2010 02:12 | 1 |
Hint Mukhametianov Den [USU] 14 Jul 2010 02:12 One stack is bad. But N stacks... =) |
| DP for O(n^3) | [Ural SU] GetTester | 1181. Cutting a Painted Polygon | 17 Mar 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. Cutting a Painted Polygon | 17 Mar 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. Cutting a Painted Polygon | 27 Apr 2009 17:09 | 1 |
??
who can help me? thanks a lot. |
| Wrong limitations | Fyodor Menshikov | 1181. Cutting a Painted Polygon | 25 Dec 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. Cutting a Painted Polygon | 6 Jul 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. Cutting a Painted Polygon | 18 Jan 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. Cutting a Painted Polygon | 5 Oct 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. Cutting a Painted Polygon | 23 Jun 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. Cutting a Painted Polygon | 31 Jan 2005 15:56 | 2 |
|
| For those who need a hint... 8-) | Alex[LSD] | 1181. Cutting a Painted Polygon | 6 Jun 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-) |
