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

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

10845 - The crusades

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

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?

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

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
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm

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

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.

Post Reply

Return to “Volume 108 (10800-10899)”