| ENG RUS | Timus Online Judge |
Discussion of Problem 1181. Cutting a Painted Polygonhadooken Useful test // Problem 1181. Cutting a Painted Polygon 18 Dec 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? // Problem 1181. Cutting a Painted Polygon 25 Apr 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) // Problem 1181. Cutting a Painted Polygon 12 Feb 2016 16:27 Blum WA test #5 [3] // Problem 1181. Cutting a Painted Polygon 3 Nov 2007 23:22 Can anyone give me some tricky tests? Rumter (2) Re: WA test #5 [2] // Problem 1181. Cutting a Painted Polygon 12 Jul 2008 15:35 5 RGRBG 7 RBGBRGB 6 RGBGRB 4 RRBG Roks Re: WA test #5 [1] // Problem 1181. Cutting a Painted Polygon 26 Sep 2008 05:13 last example is wrong Alex Mullabaev'` Re: WA test #5 // Problem 1181. Cutting a Painted Polygon 6 Jan 2016 11:55 10 RGBGBGBGBG Felix_Mate Idea [1] // Problem 1181. Cutting a Painted Polygon 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. wangbicheng1 Re: Idea // Problem 1181. Cutting a Painted Polygon 2 Nov 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? // Problem 1181. Cutting a Painted Polygon 22 Aug 2010 10:54 Is there some special inputs in test6? Mukhametianov Den [USU] Hint // Problem 1181. Cutting a Painted Polygon 14 Jul 2010 02:12 One stack is bad. But N stacks... =) [Ural SU] GetTester DP for O(n^3) [2] // Problem 1181. Cutting a Painted Polygon 6 Nov 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] // Problem 1181. Cutting a Painted Polygon 7 Nov 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) // Problem 1181. Cutting a Painted Polygon 17 Mar 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] // Problem 1181. Cutting a Painted Polygon 23 Feb 2002 23:52 My mail: bsc98001@yahoo.com Gheorghe Stefan Re: O(n^3) gets TLE. Can anyone give me a better hint? [1] // Problem 1181. Cutting a Painted Polygon 24 Nov 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? // Problem 1181. Cutting a Painted Polygon 17 Mar 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 // Problem 1181. Cutting a Painted Polygon 27 Apr 2009 17:09 ?? who can help me? thanks a lot. Fyodor Menshikov Wrong limitations [3] // Problem 1181. Cutting a Painted Polygon 25 Dec 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] // Problem 1181. Cutting a Painted Polygon 25 Dec 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 // Problem 1181. Cutting a Painted Polygon 25 Dec 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 // Problem 1181. Cutting a Painted Polygon 25 Dec 2008 21:21 Vedernikoff Sergey (HSE: EconomicsForever!) wrote 25 December 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! // Problem 1181. Cutting a Painted Polygon 6 Jul 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] // Problem 1181. Cutting a Painted Polygon 10 Jan 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 (+) // Problem 1181. Cutting a Painted Polygon 18 Jan 2007 20:36 12 more submits lost AC. Thanks to Alexander Toropov for new validator and tests! Samsonov Alex [SESC USU] One question [2] // Problem 1181. Cutting a Painted Polygon 10 Jun 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 // Problem 1181. Cutting a Painted Polygon 23 Jun 2005 01:36 Yes AlexF [USTU] Re: One question // Problem 1181. Cutting a Painted Polygon 5 Oct 2006 19:06 There is no "0" at all! Because all these situation are discribed in the task!)) hello I have some questions...... [2] // Problem 1181. Cutting a Painted Polygon 14 May 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] // Problem 1181. Cutting a Painted Polygon 14 May 2004 21:10 Everything is possible! Just think better. Tintor Marko Re: I have some questions...... // Problem 1181. Cutting a Painted Polygon 23 Jun 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] // Problem 1181. Cutting a Painted Polygon 31 Jan 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." (-) // Problem 1181. Cutting a Painted Polygon 31 Jan 2005 15:56 Alex[LSD] For those who need a hint... 8-) // Problem 1181. Cutting a Painted Polygon 6 Jun 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-)
|