10037 - Bridge

[LittleJohn]

Here is my thoughts (get WA):
when the number of people > 3, we select one of the two strategies below:
[assume that all the people are sorted so that A is the fastest and Z is the slowest]
1) (AZ), (A), (AY), (A)
2) (AB), (A), (YZ), (B)
and finally we just pass the bridge by using the fastest one.
Is it correct or not? Thanks a lot!

[gvcormac]

No it isn't correct. You only have to consider the fastest handful of riders.

[LittleJohn]

Just like sample input: 1, 2, 5, 10:
We have to choose the fastest 1 and 2 at first time.
And when 1 is back, we are going to choose the slowest 5 and 10 (not 1 and 10)...
But you said that we only have to consider the fastest...
Do I misunderstand what you mean?

[gvcormac]

Suppose the people are A, B, C, D, ... Y, Z, in order from fastest to slowest. Your basic strategy is right, but it should be applied to A, B, C, D, not A, B, Y, Z.

[LittleJohn]

Thank you for your help.
But I can't understand. Suppose the input is [1, 2, 3, 4, 5]
According to your strategy:
(1, 2) -> 2
(1) -> 1
(3, 4) -> 4
(2) -> 2
(1, 5) -> 5
(1) -> 1
(1, 2) -> 2
total = 17

And mine:
(1, 2) -> 2
(1) -> 1
(4, 5) -> 5
(2) -> 2
(1, 3) -> 3
(1) -> 1
(1, 2) -> 2
total = 16

[gvcormac]

You are correct. Sorry about that. Just to be sure I glanced at my notes and my approach is as you said originally. Are you handling the cases of 3, 2, 1 people correctly?

[LittleJohn]

Yes, it works well with the cases of 1, 2, 3 people.
But I still can't find my bugs.
Could somebody test my program if possible? Thanks very much!

Code: Select all

Rejudged. :)

[gvcormac]

Your program works on all my data files.

I did observe that one of the data files had an extra line at the end. So it is likely that in converting to "multiple input" the uva people preserved that extra line.

To remedy this you would have to scan for the empty line at the end of each test case.

[LittleJohn]

Thank you, Dr. Cormack.
Scanf in C language will ignore all the empty lines, thus when the data files have an extra line at the end, the C program works well.
I wonder how the judge check program was written..if it used gets() to read the whole line and sscanf to parse the string,
it may be wrong when my output does not match the reading format of that check-program.
Still don't know how to do now..

[gvcormac]

At Waterloo there were 13 separate input files. One had an extra line. This went unnoticed because, as you said, most programs simply ignored the extra line.

At uva, I assume they concatenated all the input files. So one of the cases would have extra input. I thought you would have to do something like this at the end of each case:

{
char x[1000];
gets(x); /* read to end of line*/
while (gets(x) && *x) {} /* read until empty line */
}

But I just tried this with the Waterloo model solution and it gets WA!

I also tried ignoring "n", the number of people, and I still get WA. I give up.

[LittleJohn]

I don't wanna give up, but I do, too.
It's really a big trouble...><
Deeply appreciate your help!! :)

[Yarin]

This problem is most definately broken. By doing lots of asserts & submissions, I found that the testdata indeed is a concatenation of the 13 testcases on the Waterloo site. The problem is that the 7th test case is faulty, it specifies n=1000, but then contains 1001 integers. This messes things up quite a bit.

I was surprised that so many people still have got this one AC, so I decided to check when people had got it accepted. To my - not so big surprise - nobody has got it AC during the last 3 months (before that, _many_ people each month). Which gives? Something happened 3 months ago (like multiple input!?) which caused the problem to get broke?

[Krzysztof Sikora]

I have algorithm like LittleJohn. My program pass all Waterloo tests.
I know that one test has more then n people.
I tried three ways:
1. read n
for i = 1 to n read human
read line until empty line
2. read integer (n, dummy line)
n = 0
read human; n++; until empty line
3. specification

All three method failed. Could you tell me how to solve it?

[dwyak]

i've tried many methods too. but all failed.
what's the matter?
although the testcase is wrong, i think i can still pass all the waterloo cases.

[Revenger]

What are you doing? The test data for 10037 is wrong! May be you have spoiled it while you were formating it?.

My solution gets WA. But I have judge solution! What's wrong?