Page 1 of 1

10845 - The crusades

Posted: Fri May 20, 2005 8:22 am
by Pupirev Sergei
Can somebody help to solve this problem? I don't know algorithm faster than O(2^30)...

Posted: Sat May 21, 2005 3:37 pm
by stubbscroll
I haven't implemented this algorithm yet, but here's a suggection:

- Do a brute force for the first king's path
- For each path above, do a maxflow on the available edges for the second king's path.

Now the problem is how to do the first step quickly. Btw, what happened to the picture in the problem statement?

Posted: Sat May 21, 2005 3:57 pm
by dumb dan
I haven't really thought alot about this problem, but isn't it some kind of variant of the knapsack problem?

Posted: Sat May 21, 2005 7:33 pm
by Pupirev Sergei
- Do a brute force for the first king's path
But isn't it O(2^30) ?

Posted: Sun May 22, 2005 1:00 am
by stubbscroll
Pupirev Sergei wrote:
- Do a brute force for the first king's path
But isn't it O(2^30) ?
I'm not at all sure if brute force will work, but clever pruning might do the trick. I have used backtracking+pruning on some other hard graph problems with success earlier. I doubt my proposed solution is the good way to solve this problem, though.