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.
3985 - Board games
Moderator: Board moderators
3985 - Board games
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
3985 - Board games
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)?
Re: 3985 - Board games
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):
After (Gives Accepted):
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!
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;
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;
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
Re: 3985 - Board games
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.
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.
Re: 3985 - Board games
I am not sure, but my program did produce "infinity" for this input:
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).
Code: Select all
1
3
0 2
3
0 0 -100
0 1 1
1 2 1
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com