## 10888 - Warehouse

Moderator: Board moderators

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

### 10888 - Warehouse

Hi, All! Can anybody help me to solve this problems ?!

On contest I tried to solve p10888-Warehouse. My algo used BFS and Hungarian algo, but I got TLE.

I can't think out any idea to solve 10890. But I very want to did them. Help me please!

Thanks!

kai
New poster
Posts: 5
Joined: Mon Aug 08, 2005 2:36 pm
Location: Japan
How many times do you run the BFS for 10888?
Can your program solve a case like the following in a reasonable time?

40 40
BBBBBBBBBBBBBBBXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
(...and 35 more lines of X's)

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Although I haven't taken part in the contest, I can tell you that 10890 Maze can be solved by BFS. Backtracking (as in TSP) should work, too.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

### 10888 warehouse

for 10888 warehouse
can i use HUNGARIAN METHOD for this problem, not to get TLE?

but there can too many 'X' s..
i think i should delete appropriate warehouse('X')s,

or find other efficient algorithm...
Sorry For My Poor English..

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

### count B != cont X ???

It is very interesting question. There are nothing said in problem statement about this. But i tried to insert line like this in my code:

if (nb!=nx) a[-100000] = -1;

It will be get Runtime Error (SigSeg) or something this...

What algorithms you used, who get AC?

Tanks!

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
The number of B always equals the number of X. That should have been stated in the problem text - sorry!

I had originally forgot to mention the limit 15 (!!) for some weird reason, but at least that was included before the contest...

The Hungarian method is way overkill for this problem.

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
I find myself wanting to do a minimal weighted bipartite matching.
I don't see how I can do this withouht using the hungarian method
too lazy to code it to see if it give me TLE too
but simple greedy gave me WA and a backtrack with some simple pruning gave TLE.
is there a polytime algorithm for this matching without using the hungarian method?

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
One does not need a polynomial algorithm with the number of items to be matched are only 15. DP (2^15) is enough.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

### 10888 warehouse WA - using mincost maxflow

hi,

problem 10888 is about weighted bipartite matching,

so i used mincost maxflow algorithm, which runs with O(|f|n^2).

make virtual vertex S, T and

construct edge(capacity=1, cost=0) S to all boxes
, edge(cap=1, cost=0, also) all houses to T,
and edge(capacity=1, cost = distance from a house and a box)
pair of all boxes to all houses,

and used mincost maxflow algorithm.

i know that this algo would be give a optimal result...

also, |f| < O(V), so total complexity is about O(V^3), same as munkres algorithm known "hungarian notation"

i got ACCEPTED 10594 Data Flow, a min-cost maxflow problem, with this same minflow algorithm and code,
but i'm confused why bipartite matching gives WA.

can you help me?
Sorry For My Poor English..

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan
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.

--
glory is forever

Joker
New poster
Posts: 1
Joined: Tue Sep 06, 2005 9:28 am
Location: Russia, Novosibirsk
Contact:

### 10888 - Warehouse

Can someone give me some inputs and outputs for this problem, because I used hungarian method(get AC in other problem) and get WA...

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: Problem 10888 I/O needed

Joker wrote:Can someone give me some inputs and outputs for this problem, because I used hungarian method(get AC in other problem) and get WA...
input:

Code: Select all

``````5
6 7
.X.....
#######
.B.....
.......
.......
......X
30 2
BX##BX##BX##BX##BX##BX##BX##BX
##BX##BX##BX##BX##BX##BX##BX##
5 5
#XXX#
XBBBX
XBBBX
XBBBX
#XXX#
40 40
........................................
.######################################.
.#..B................................X#.
.######################################.
.#...B...............................X#.
.######################################.
.#....B..............................X#.
.######################################.
.#.....B.............................X#.
.######################################.
.#X.....B............................X#.
.######################################.
.#X......B...........................X#.
.######################################.
.#X.......B..........................X#.
.######################################.
.#X........B.........................X#.
.######################################.
.#X.........B........................X#.
.######################################.
.#X..........B.......................X#.
.######################################.
.#X..................................X#.
.######################################.
.#X...........B......................X#.
.######################################.
.#X..................................X#.
.######################################.
.#.............B.....................X#.
.######################################.
.#...................................X#.
.######################################.
.#..............B....................X#.
B######################################.
.#...................................X#.
.######################################.
.#...............B...................X#.
.#.####################################.
.#...................................X#.
.######################################X
40 40
........................................
.######################################.
.#X...................................#.
.####################################.#.
.#X.................................#.#.
.##################################.#.#.
..................#X..............#.#.#.
.################.###########.....#.#.#.
.#...#.......................#X...#.#.#.
.#..#..#####################..#...#.#.#.
.#.#..#.....................#..#..#.#.#.
.#.#.#..#########.#########..#.#..#.#.#.
.#.#.#.#...................#.#.#..#.#.#.
.#.#.#.#.#################.#.#.#..#.#.#.
.#.#.#.#.#BBBBBBBBBBBBBBB#.#.#.#..#.#.#.
.#.#.#.#.########.########.#.#.#..#.#.#.
.#.#.#.#...................#.#.#..#.#.#.
.#.#.#..###################..#.#..#.#.#.
.#.#..#.....................#..#..#.#.#.
.#.X#..##########.##########..#X#.#.#.#.
...#.#.......................#..#.#.#.#.
###...#######################...........
..............................##########
.#############################..........
.#.............................#######..
.#..###########################.......#.
.#.#............................####..#.
.#.#.X##########################....#.#.
.#.#.#...........................##.#.#.
.#.#.#..#########################X#.#.#.
.#.#.#.#XX#XXX#XXX#XXX#XXX#XXX#...#.#.#.
.#.#.#.#XXXX#XXX#XXX#XXX#XXX#XXX#.#.#.#.
.#.#.#..########################..#.#.#.
.#.#.#............................#.#.#.
.#.#.X############################X.#.#.
.#.#................................#.#.
.#..################################X.#.
.#....................................#.
.######################################.
........................................``````
My AC's output:

Code: Select all

``````8
15
11
363
5683``````

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
Hello ,
I got AC by using simple bipartite matching algorithm.
, but I am curious about how to apply DP on this problem.

If someone else can give me hints...

Thanks a lot!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Is it a simple matching or weighted matching? You can find weighted matching by dp. The algorithm takes O(n^2 * 2^n) time.
Ami ekhono shopno dekhi...
HomePage

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
Jan wrote:Is it a simple matching or weighted matching? You can find weighted matching by dp. The algorithm takes O(n^2 * 2^n) time.
Hello ,Jan

I use MaximumFlowMinimumCost method to solve this problem.

But could you show me how to apply DP on this problem briefly?

thanks a lot:)