3985 - Board games

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

Post Reply
User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

3985 - Board games

Post by andmej » Mon Sep 01, 2008 4:41 am

Problem 3985 - Board games from the Live Archive looks like a simple application of Bellmand-Ford's algorithm.

At first I tried simply running Bellmand-Ford an if there existed a negative cycle, print "infinity." This gave me Wrong Answer. So then I noticed that there could be a negative cycle that could not lead later to the destination (I assumed the graph is directed). So I first computed the transitive-closure of the graph using Ford's algorithm and in the part of the Bellman-Ford that checks the presence of an edge (u, v) that belongs to a negative cycle, I see if edge v can take me to the destination. If this is true, then I print "infinity."

This gives me Wrong answer too! I don't know where could my program fail. Is there a very tricky case for this problem? Thank you.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

hasib_bd
New poster
Posts: 14
Joined: Wed Apr 30, 2008 12:39 pm

3985 - Board games

Post by hasib_bd » Mon Sep 01, 2008 11:54 am

I also did the same thing mentioned by andmej and in addition i also resubmitted the solution considering the graph to be undirected but still getting wa. Can anyone who solved this give some sample i/o (and/or tricky)?

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 3985 - Board games

Post by andmej » Mon Sep 01, 2008 10:19 pm

Apparently there are big numbers in the judge's test cases.

I finally got accepted after changing the data type used in the relaxation step in Bellman's Ford algorithm from int to long long:

Before (Gives Wrong Answer):

Code: Select all

int u = e[j].u, v = e[j].v;
int w = e[j].w;
if (d[u] + w < d[v])
    d[v] = d[u] + w;
After (Gives Accepted):

Code: Select all

int u = e[j].u, v = e[j].v;
long long w = e[j].w;
if (d[u] + w < d[v])
    d[v] = d[u] + w;
So be careful with a possible overflow. Also, you don't need to run Transitive closure. At first this gave me time limit exceeded on the Live Archive. So I sent my code to ZJU judge which is much faster, you can practice there first and then optimize your code for the Live Archive. Good luck!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

hasib_bd
New poster
Posts: 14
Joined: Wed Apr 30, 2008 12:39 pm

Re: 3985 - Board games

Post by hasib_bd » Tue Sep 02, 2008 9:55 pm

At first I got accepted in ZJU judge but still was getting wa in uva.

After a lot of trials and errors finally i got ac with edge variable type as long int. I found that there are some inputs where u = v & w != 0. I was relaxing edges where u and v are not equal (as i was using a adjacency matrix) and that's why was getting wa.

I think input edge specification where u = v & w != 0 doesn't go with the problem specification, although this is not written clearly but what does it mean by 1 1 -100? That means if i'm standing on square 1, my score will be -infinity? I'm requesting your attention on this issue.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 3985 - Board games

Post by andmej » Wed Sep 03, 2008 3:51 pm

I am not sure, but my program did produce "infinity" for this input:

Code: Select all

1

3
0 2
3
0 0 -100
0 1 1  
1 2 1
I think the problem description has some flaws, it's very ambiguous in some parts. This holds for all problems from the problem-set that this problem belongs to (SWERC 2007).
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Post Reply

Return to “ACM ICPC Archive Board”