10888 - Warehouse

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Aug 20, 2007 4:36 pm

Code: Select all

Suppose there are 4 boxes and 4 destinations. And lets consider that f(0001) means that the cost where the 4th destination is used and there is only one box. f(0010) returns the cost where the 3rd destination is used with box 1.

So, f(1001) returns the min cost such that the first two boxes are used and the 1st and the 4th destinations are used.

So, f(1101) returns the min cost such that the first three boxes are used and the 1st, 2nd and the 4th destinations are used. So, the number of '1's means the number of boxes. Right?

So, f(1111) is our desired result. And suppose cost[i][j] means the cost to connect the ith box to the jth destination.

Now we can build a recurrence

f(1111) = min ( f(1110) + cost[4][4], f(1101) + cost[4][3], f(1011) + cost[4][2],
                f(0111) + cost[4][1] );
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Re:

Post by DJWS » Wed Jun 11, 2008 9:10 am

polone wrote:There are a situation that some X may not be matched to every B.

So you should exam your cost list that shouldn't exist strange numbers.

Hope that help you~
I made assertions in my code and I found the # of B is equal to the # of X.
The problem statement does not mention the equality so we can not assume they are the same in fact.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 10888 - Warehouse

Post by andmej » Fri Aug 01, 2008 4:52 am

Hi, I understand the DP solution explained above by Jan.

However, I don't understand the solution using min-cost max-flow algorithm.

Can somebody explain the idea a little deeper? Thanks.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10888 - Warehouse

Post by Shafaet_du » Sun Aug 28, 2011 11:27 am

Problem setter should have mentioned that number of destination==number of boxes.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10888 - Warehouse

Post by Shafaet_du » Sun Aug 28, 2011 11:29 am

try this:

Code: Select all

1
5 8
X...#..X
X#......
.BB#.#.X
..B#...#
X..B...B



output:

Code: Select all

21

Post Reply

Return to “Volume 108 (10800-10899)”