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

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

10888 - Warehouse

Post by Victor Barinov » Mon Aug 08, 2005 1:36 pm

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!

:cry: :cry: :cry:

Thanks!

kai
New poster
Posts: 5
Joined: Mon Aug 08, 2005 2:36 pm
Location: Japan

Post by kai » Mon Aug 08, 2005 2:58 pm

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

Post by Observer » Mon Aug 08, 2005 4:08 pm

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

Post by wook » Mon Aug 08, 2005 4:13 pm

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

Post by Victor Barinov » Mon Aug 08, 2005 6:08 pm

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:

Post by Yarin » Mon Aug 08, 2005 6:28 pm

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.

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Mon Aug 08, 2005 10:42 pm

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

Post by Yarin » Tue Aug 09, 2005 11:59 am

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

Post by wook » Sun Aug 14, 2005 5:08 am

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?
Sorry For My Poor English.. :)

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Sat Sep 03, 2005 6:19 am

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
New poster
Posts: 1
Joined: Tue Sep 06, 2005 9:28 am
Location: Russia, Novosibirsk
Contact:

10888 - Warehouse

Post by Joker » Tue Sep 06, 2005 10:14 am

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

User avatar
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

Post by Martin Macko » Sun Dec 11, 2005 4:30 pm

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

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Mon Aug 20, 2007 10:30 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Aug 20, 2007 1:48 pm

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

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Mon Aug 20, 2007 3:59 pm

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

Post Reply

Return to “Volume 108 (10800-10899)”