## 10845 - The crusades

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm

### 10845 - The crusades

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

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
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
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
I haven't really thought alot about this problem, but isn't it some kind of variant of the knapsack problem?

Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm
- Do a brute force for the first king's path
But isn't it O(2^30) ?

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
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.