10845 - The crusades

Pupirev Sergei · Post by **Pupirev Sergei** » Fri May 20, 2005 8:22 am

Can somebody help to solve this problem? I don't know algorithm faster than O(2^30)...

stubbscroll · Post by **stubbscroll** » Sat May 21, 2005 3:37 pm

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?

dumb dan · Post by **dumb dan** » Sat May 21, 2005 3:57 pm

I haven't really thought alot about this problem, but isn't it some kind of variant of the knapsack problem?

Pupirev Sergei · Post by **Pupirev Sergei** » Sat May 21, 2005 7:33 pm

- Do a brute force for the first king's path

But isn't it O(2^30) ?

stubbscroll · Post by **stubbscroll** » Sun May 22, 2005 1:00 am

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.