|
|
Isn't Test#5 the n=500 one? O(n^3) dp with optimizations gets AC in 0.38 sec. Probably there is some asymptotically faster solution. If you have WA #4 try this simple test: 3 2 1 5 10 answer is of course 16 1 2 What's mean this problem? why the example one should output 14 3? 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? Try data: 3 2 9 2 1 6 3 8 Edited by author 15.10.2012 17:43 I have problems with this test too. My answer is 23 1 3 Is the correct? 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 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....! 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 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. @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! I am getting correct answer for all the test cases listed here but still I have WA5, any idea why? If you have WA 5 you may try this test: 4 2 6 9 1 2 20 10 ans: 46 1 3 > 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. 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. I have a problem with test 2 too |
|
|