|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | dp O(n^3) 0.078s | InstouT94 | 1900. Машина счастья | 19 июл 2022 18:39 | 1 | | | test | >>> | 1900. Машина счастья | 4 ноя 2021 15:46 | 1 | test >>> 4 ноя 2021 15:46 | | TLE 6 | raven | 1900. Машина счастья | 11 янв 2016 18:29 | 1 | TLE 6 raven 11 янв 2016 18:29 Isn't Test#5 the n=500 one? | | Any hints? | Programmer | 1900. Машина счастья | 17 ноя 2015 14:59 | 2 | O(n^3) dp with optimizations gets AC in 0.38 sec. Probably there is some asymptotically faster solution. | | If you have WA #4 | Smilodon_am [Obninsk INPE] | 1900. Машина счастья | 10 дек 2013 17:08 | 1 | 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? | stat958 | 1900. Машина счастья | 23 ноя 2013 22:20 | 2 | What's mean this problem? why the example one should output 14 3? | | test 5 boundary case? | Bogatyr | 1900. Машина счастья | 26 июн 2013 14:50 | 11 | 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. | | WA 5 | A.06 | 1900. Машина счастья | 10 апр 2013 10:24 | 1 | WA 5 A.06 10 апр 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. | | WA 8 | orbby | 1900. Машина счастья | 18 фев 2013 17:38 | 1 | WA 8 orbby 18 фев 2013 17:38 | | what is the TEST2 | ace | 1900. Машина счастья | 13 окт 2012 15:30 | 2 | I have a problem with test 2 too |
|
|
|
