Page 1 of 2
10888 - Warehouse
Posted: Mon Aug 08, 2005 1:36 pm
by Victor Barinov
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!
Posted: Mon Aug 08, 2005 2:58 pm
by kai
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)
Posted: Mon Aug 08, 2005 4:08 pm
by Observer
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.
10888 warehouse
Posted: Mon Aug 08, 2005 4:13 pm
by wook
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...
count B != cont X ???
Posted: Mon Aug 08, 2005 6:08 pm
by Victor Barinov
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!
Posted: Mon Aug 08, 2005 6:28 pm
by Yarin
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.
Posted: Mon Aug 08, 2005 10:42 pm
by abishek
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?
Posted: Tue Aug 09, 2005 11:59 am
by Yarin
One does not need a polynomial algorithm with the number of items to be matched are only 15. DP (2^15) is enough.
10888 warehouse WA - using mincost maxflow
Posted: Sun Aug 14, 2005 5:08 am
by wook
hi,
problem 10888 is about weighted bipartite matching,
so i used mincost maxflow algorithm, which runs with O(|f|n^2).
but i got wrong answer.
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?
Posted: Sat Sep 03, 2005 6:19 am
by polone
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~
--
glory is forever
10888 - Warehouse
Posted: Tue Sep 06, 2005 10:14 am
by Joker
Can someone give me some inputs and outputs for this problem, because I used hungarian method(get AC in other problem) and get WA...
Re: Problem 10888 I/O needed
Posted: Sun Dec 11, 2005 4:30 pm
by Martin Macko
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:
Posted: Mon Aug 20, 2007 10:30 am
by hank
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!
Posted: Mon Aug 20, 2007 1:48 pm
by Jan
Is it a simple matching or weighted matching? You can find weighted matching by dp. The algorithm takes O(n^2 * 2^n) time.
Posted: Mon Aug 20, 2007 3:59 pm
by hank
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:)