Page 1 of 6

10037 - Bridge

Posted: Tue Jul 23, 2002 6:20 pm
by 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! :wink:

Posted: Thu Jul 25, 2002 3:32 pm
by gvcormac
No it isn't correct. You only have to consider the fastest handful of riders.

Posted: Tue Jul 30, 2002 7:33 am
by 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? :-?

Posted: Tue Jul 30, 2002 7:56 am
by 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.

Posted: Tue Jul 30, 2002 8:53 am
by 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

Posted: Tue Jul 30, 2002 3:29 pm
by 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?

Posted: Wed Jul 31, 2002 2:58 pm
by 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. :)

Posted: Thu Aug 01, 2002 4:59 am
by 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.

Posted: Thu Aug 01, 2002 7:38 am
by 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.. :-?

Posted: Thu Aug 01, 2002 1:46 pm
by 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.

Posted: Fri Aug 02, 2002 2:59 am
by LittleJohn
I don't wanna give up, but I do, too.
It's really a big trouble...><
Deeply appreciate your help!! :)

Posted: Fri Sep 20, 2002 11:14 pm
by 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?

Posted: Sat Sep 28, 2002 11:30 pm
by 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?

Posted: Sun Sep 29, 2002 3:04 pm
by dwyak
i've tried many methods too. but all failed. :cry:
what's the matter?
although the testcase is wrong, i think i can still pass all the waterloo cases.

What's going on with 10037?

Posted: Sat Oct 12, 2002 6:14 am
by 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?