3985 - Board games

[andmej]

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.

[hasib_bd]

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)?

[andmej]

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!

[hasib_bd]

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.

[andmej]

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).