OJ Board

The answer given in the sample output is not correct. The correct answer is -1. Fortunately the judge data is fine.

Unfortunately there seems to be no good solution for this problem. Even the official judge solution is wrong. For details, see http://forums.topcoder.com/?module=Thre ... 29#1149317.

I was also stumped by that statement for a while. I finally realized that it meant that position (x,y) is better than (x', y') iff x < x' or (x = x' and y < y'), i.e. just lexicographical order. In other words, we first do a comparison on the x-coordinate (north/south) preferring northernmost, and ...

I just solved the problem, so you can use my solution to get the correct output for your test cases (http://uvatoolkit.com/problemssolve.php#11644).

You are right - I am solving min cost flow. I have also been told that it can be done with a single run of min-cost max-flow using the successive shortest path method, so that should speed up my solution significantly.

I contacted the problem author, and he told me that there was an error in the sample output. It is supposed to be 20 (not 2), but it will probably be corrected soon. Anyway, the problem can be solved using discrete ternary search and max-cost max-flow, but my solution is quite slow, so maybe there ...

Can anybody explain to me how the answer for the case in the sample input is 2? I have been looking at the problem for a while now, and it seems to me that it can be solved using max-cost max-flow, but it seems a bit pointless to try if one cannot understand the sample output.

The inputs you have provided are a bit misleading because they are not valid according to the problem statement.

9
S.**....*****D
S.****..*****D
S*.**.*.*****D
S**.....*****D
S**...*.*****D
S**.*...*****D
S**.*.*.*****D
S**.***.*****D
S****.*.*****D

According to my AC program all answers are -1. Your code outputs 29 on all of them. You can get the expected answers for your own input sets on my homepage ...

I thought about the case for some time, and initially thought that there was a bug in my solution, but now I believe that my solution (i.e. the one on uvatoolkit) is correct. The explanation for the second case is as follows. First we go from village 1 to castle 2 for at cost of 8 and then we use ...

My solution returns the same output (you can test other sets for the problem on http://www.uvatoolkit.com).

Also try my site http://uvatoolkit.com/problemssolve.php (search for DP).

Darko wrote:Can someone check if their AC is still AC on the new server?

I just coded it and got AC.

Bump again.

There is a good discussion about this problem on the topcoder forums:
http://forums.topcoder.com/?module=Thre ... 02&start=0

I implemented the algorithm mentioned and got AC in 1.320 seconds.