825 - Walking on the Safe Side

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

Moderator: Board moderators

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

825 - Walking on the Safe Side

Post by 10153EN » Sun Jun 30, 2002 8:51 am

I have a question on this problem~

Does the *minimal path* in the problem description means (width+height-1) or an actual minimal path that reaches the goal from the starting position?

Thx

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard » Sun Jun 30, 2002 9:21 am

i've solved it generaly (i still think the problem description allow longer minimal pathes), but now i checked the judge's input and found no minimal path longer as width+height-2

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Sun Jun 30, 2002 9:55 am

Yes, you are right.

I just found my bug, initialization of variables~ Suit~ :wink: :wink:

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

Post by henar2 » Wed Oct 09, 2002 5:46 pm

What should the output be if there is a underground passage in the north-west corner or in the south-east corner or in both?
I consider output "0" for these three cases.
Thank you.

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Wed Oct 09, 2002 6:13 pm

I don't think there are such cases in the input, otherwise I should get a SIGABRT

Anyway, I think the output should be 0.

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

Post by uzioriluzan » Mon Nov 04, 2002 1:11 am

Picard wrote:i've solved it generaly (i still think the problem description allow longer minimal pathes), but now i checked the judge's input and found no minimal path longer as width+height-2
Where can you find judge's input? Have u got the input for problem 827 - Buddy Memory Allocator, too?

Thanks a lot!

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

About 825, and wrong answer

Post by cyfra » Wed Mar 26, 2003 12:36 pm

Hi!

I have just solved this task. But there is something wrong in the input.

I mean that there are some spaces after the numbers. For pascal users if they use eoln function it may cause many errors...

I wonder if this could be fixed..

Good Luck :wink:

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu May 22, 2003 3:24 am

Thanks for your note, cyfra. I've got an AC!!

However, I still don't understand what "minimal paths" mean in this qq........................

Also, my algorithm isn't very good. If the width and height are large, my program can't handle it......
(P.S. I made use of Floyd-Warshall's Algorithm...)

Any suggestions? Any help is warmly welcomed.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

route
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

Post by route » Sun May 25, 2003 3:45 pm

what is the maximum of "positive integers" in the input ?
(width and height)

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha » Tue May 27, 2003 6:26 am

route wrote:what is the maximum of "positive integers" in the input ?
(width and height)
100 is enough.

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha » Tue May 27, 2003 6:32 am

Observer wrote: However, I still don't understand what "minimal paths" mean in this qq........................

Also, my algorithm isn't very good. If the width and height are large, my program can't handle it......
(P.S. I made use of Floyd-Warshall's Algorithm...)

Any suggestions? Any help is warmly welcomed.
The minimal paths mean the total steps is (W-1)+(N-1).
And I just use easy DP to solve, because for the tatal different path of position p[j] = p[i-1][j] + p[j-1].

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Tue May 27, 2003 10:26 pm

Did you use long arithmetic? It's quite possilbe to get overflow...

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed May 28, 2003 2:17 am

eloha wrote:
Observer wrote: However, I still don't understand what "minimal paths" mean in this qq........................

Also, my algorithm isn't very good. If the width and height are large, my program can't handle it......
(P.S. I made use of Floyd-Warshall's Algorithm...)

Any suggestions? Any help is warmly welcomed.
The minimal paths mean the total steps is (W-1)+(N-1).
And I just use easy DP to solve, because for the tatal different path of position p[j] = p[i-1][j] + p[j-1].


Ah yes! You're right!!

Thanks very much! :p
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Fri May 30, 2003 9:15 pm

Can somebody post a few inputs and outputs? I think I have small mistakes like 0 0 ->1 and so on.
Is it nessesary to use long arithmetic?

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs » Sat Mar 06, 2004 9:25 pm

Dima, hi.

I think I have an answer to your not a very recent question. :)
Dima wrote:Is it nessesary to use long arithmetic?
Nope.
Dima wrote:Can somebody post a few inputs and outputs?
Here you are:

Code: Select all

8

1 1
1

1 8
1

1 8
1 4

8 1
1
2
3
4
5
6
7
8

8 1
1
2
3
4 1
5
6
7
8

4 4
1
2
3
4

8 8
1
2
3 5
4 1 4
5 3 6
6 2 7
7 8
8

8 8
1
2 6
3 2
4 5
5 1
6 3
7 5 8
8 5

Code: Select all

1

1

0

1

0

20

0

233
Anyway, try rewriting your code from scratch. That usually helps. :wink:

Post Reply

Return to “Volume 8 (800-899)”