10037 - Bridge

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

10037 - Bridge

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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
No it isn't correct. You only have to consider the fastest handful of riders.

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
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. :)
``````
Last edited by LittleJohn on Fri Sep 05, 2003 9:14 am, edited 1 time in total.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
I don't wanna give up, but I do, too.
It's really a big trouble...><
Deeply appreciate your help!! :)

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
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
New poster
Posts: 11
Joined: Mon Sep 02, 2002 4:40 pm
Location: Poland
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?
-- Krzysztof Sikora

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:
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.
Wenyuan Dai, Shanghai Jiaotong University.

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

What's going on with 10037?

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?