10888 - Warehouse

[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!

[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)

[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.

[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...

[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!

[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.

[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?

[Yarin]

One does not need a polynomial algorithm with the number of items to be matched are only 15. DP (2^15) is enough.

[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?

[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

[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...

[Martin Macko]

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]

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]

Is it a simple matching or weighted matching? You can find weighted matching by dp. The algorithm takes O(n^2 * 2^n) time.

[hank]

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:)