ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1900. Brainwashing Device

test 5 boundary case?
Posted by Bogatyr 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?
Re: test 5 boundary case?
Posted by samplex 15 Oct 2012 17:43
Try data:
3 2
9 2 1
6 3
8

Edited by author 15.10.2012 17:43
Re: test 5 boundary case?
Posted by Berezhko German 15 Oct 2012 18:32
I have problems with this test too. My answer is
23
1 3
Is the correct?
Re: test 5 boundary case?
Posted by Bogatyr 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
Re: test 5 boundary case?
Posted by Bogatyr 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....!
Re: test 5 boundary case?
Posted by samplex 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
Re: test 5 boundary case?
Posted by samplex 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.
Re: test 5 boundary case?
Posted by Bogatyr 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!
Re: test 5 boundary case?
Posted by Bogatyr 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.
Re: test 5 boundary case?
Posted by A.06 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?
Re: test 5 boundary case?
Posted by Vladimir Leskov 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