| ENG RUS | Timus Online Judge |
Discussion of Problem 1900. Brainwashing DeviceInstouT94 dp O(n^3) 0.078s // Problem 1900. Brainwashing Device 19 Jul 2022 18:39 >>> test // Problem 1900. Brainwashing Device 4 Nov 2021 15:46 4 3 0 0 10 0 0 0 -- 10 1 2 3 raven TLE 6 // Problem 1900. Brainwashing Device 11 Jan 2016 18:29 Isn't Test#5 the n=500 one? Programmer Any hints? [1] // Problem 1900. Brainwashing Device 9 Aug 2015 11:47 Nikolay Makarov Re: Any hints? // Problem 1900. Brainwashing Device 17 Nov 2015 14:59 O(n^3) dp with optimizations gets AC in 0.38 sec. Probably there is some asymptotically faster solution. Smilodon_am [Obninsk INPE] If you have WA #4 // Problem 1900. Brainwashing Device 10 Dec 2013 17:08 If you have WA #4 try this simple test: 3 2 1 5 10 answer is of course 16 1 2 stat958 What's mean this problem? why the example one should output 14 3? [1] // Problem 1900. Brainwashing Device 17 Aug 2013 14:43 What's mean this problem? why the example one should output 14 3? ძამაანთ [Tbilisi SU] Re: What's mean this problem? why the example one should output 14 3? // Problem 1900. Brainwashing Device 23 Nov 2013 22:20 I don't understand too Bogatyr test 5 boundary case? [10] // Problem 1900. Brainwashing Device 14 Oct 2012 20:20 I can't get past WA #5. I know it's an n=500 case, but my solution works for n=500 with various k and passenger data as far as I can tell. Any other boundary conditions known to be in test 5? samplex Re: test 5 boundary case? [9] // Problem 1900. Brainwashing Device 15 Oct 2012 17:43 Try data: 3 2 9 2 1 6 3 8 Edited by author 15.10.2012 17:43 Berezhko German Re: test 5 boundary case? // Problem 1900. Brainwashing Device 15 Oct 2012 18:32 I have problems with this test too. My answer is 23 1 3 Is the correct? Bogatyr Re: test 5 boundary case? [7] // Problem 1900. Brainwashing Device 15 Oct 2012 18:38 But your example is ill-formed because you've included data correct for n=4 but you specify n=3 Assuming you meant "4 2" instead of "3 2", yes my solution also produces: 23 1 3 which a visual check shows is the correct answer (based on my understanding! If you have AC and get a different result than "23/1 3", please respond!) Edited by author 16.10.2012 02:47 Bogatyr Re: test 5 boundary case? [6] // Problem 1900. Brainwashing Device 16 Oct 2012 02:54 I'm beginning to wonder if the test 5 answer set includes all possible correct answers, since in many problems there will be quite a lot of legal answers when there are ties for each maximum span. Of course everyone thinks their problem is right and the tests are wrong :). What is it I'm missing, I must be brainwashed not to see it! What's wrong with my thinking? + add the passenger groups into the corresponding spans + greedy approach, take max, then 2nd max, etc., k times + make sure to count a particular passenger group only once if it participates in finding one of the k max spans + total up each max span, and output the spans in ascending order What else is there? Must be a silly mistake or misunderstanding....! samplex Re: test 5 boundary case? [5] // Problem 1900. Brainwashing Device 16 Oct 2012 19:20 Yes, I meant "4 2". I got WA #5 too and my programm correctly work on my example, but I understand that my programm may not work properly in the examples, like the one that I brought. My example is simple, but it shows that in the first selection, each railroad crossing gives us 12 happy people, but the end result depends on the first choice. If first choice is 2nd, than result — 21 / 1 2 samplex Re: test 5 boundary case? [3] // Problem 1900. Brainwashing Device 16 Oct 2012 20:05 Try it: 5 2 9 11 4 2 4 9 2 8 7 9 48 / 2 4 is wrong answer. 52 / 1 3 is correct. Bogatyr Re: test 5 boundary case? // Problem 1900. Brainwashing Device 16 Oct 2012 22:23 @samplex: Thank you! This shows my "choose the first max" greedy approach is wrong. I suspected this was the problem but didn't work hard enough to come up with a counter-example. So my code matches my solution approach, but my solution approach was wrong. Back to the drawing board... always be skeptical of the greedy approach! A.06 Re: test 5 boundary case? [1] // Problem 1900. Brainwashing Device 10 Apr 2013 09:57 I am getting correct answer for all the test cases listed here but still I have WA5, any idea why? Vladimir Leskov Re: test 5 boundary case? // Problem 1900. Brainwashing Device 26 Jun 2013 14:50 If you have WA 5 you may try this test: 4 2 6 9 1 2 20 10 ans: 46 1 3 Bogatyr Re: test 5 boundary case? // Problem 1900. Brainwashing Device 16 Oct 2012 22:24 > My example is simple, but it shows that in the first selection, each railroad crossing > gives us 12 happy people, but the end result depends on the first choice. If first > choice is 2nd, than result — 21 / 1 2 Yes I missed this point, thanks again. A.06 WA 5 // Problem 1900. Brainwashing Device 10 Apr 2013 10:24 I am using DP O(n^2) time and getting WA 5. I have tried all the test cases listed here and my program outputs correct answer for all of them. If anyone has any examples, please respond, thank you. orbby WA 8 // Problem 1900. Brainwashing Device 18 Feb 2013 17:38 try: 3 2 0 0 0 ace what is the TEST2 [1] // Problem 1900. Brainwashing Device 13 Oct 2012 14:32 Mahammad Valiyev Re: what is the TEST2 // Problem 1900. Brainwashing Device 13 Oct 2012 15:30 I have a problem with test 2 too
|