10863 - Shovelling Snow

[Endrju]

Hi,
I was thinking quite a long time how to solve this, but still no results . Can anyone help me with this problem? A small hint would be appreciated . (I thought about finding a reasonable solution first (shortest paths etc.) and then backtracking perhaps?, but this seems to be way too slow)

regards,
Endrju

[Martin Macko]

There are just few patterns how the smallest shovelled area may look like. Try find them all, this could help you.

[Endrju]

Thank you Martin, I think I understand the idea now

[mysword]

Can the houses seperated by the obstacles? That means the some house cannot reach other houses even clearing all the snow. If this case can happen, output what?

Can any give some test cases?

Who know how many test cases this problem has?

My algorithm runs in O(n^4), but TLE....

[Martin Macko]

Can the houses seperated by the obstacles? That means the some house cannot reach other houses even clearing all the snow. If this case can happen, output what?

During the summers, going from any of the four friends

[mf]

Can the houses seperated by the obstacles? That means the some house cannot reach other houses even clearing all the snow. If this case can happen, output what?

I think there are no such test cases; my accepted program would just output the input.

My algorithm runs in O(n^4), but TLE....

Well, my solution is the fastest on the ranklist, but in the worst case it's O((mn)^2), too.
(I can improve it to O(mn log(mn)), but that's a bit tricky.)

A few test cases:

Code: Select all

10 1
AooBooCooD

10 1
AoCBoooD.#

10 1
A.CBoooD.#

10 1
A..B..C..D

12 3
oooooooooooo
oAooBooCooDo
oooooooooooo

12 3
oooooooooooo
oA..B..C..Do
oooooooooooo

12 5
oooooooooooo
oAooBooCooDo
o.ooooo.oooo
o.ooooo.oooo
o......ooooo

12 5
oooooooooooo
ooooBooCooDo
A.oo.oo.ooo.
o.oo.oo.ooo.
oo..o..o...o

12 5
oooooooooooo
ooooBooCooDo
A.oo.oo.ooo.
o.oo.oo.oo..
oo..o..o...o

6 2
AooBCD
oooo##

6 2
A..BCD
oooo##

6 6
AooooB
oooooo
oooooo
oooooo
oooooo
CooooD

5 5
ooAoo
ooooo
BoooC
ooooo
ooDoo

5 5
ooAoo
Boooo
ooooo
ooooC
ooDoo

4 4
Ao#B
o.oo
#o.o
CoDo

20 10
oooooooooooooooooooo
Aooooooooooooooooooo
ooooooooooooooBooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooCoooooooooooooo
ooooooooooooooooDooo
oooooooooooooooooooo

20 10
oooooooooooooooooooo
Aoooo#oooooooo#ooo##
ooooo#ooooo#ooBooooo
ooooooo#o#oooooooooo
oooooooo#ooooooooooo
ooooo#oooo#ooo#ooooo
oooooooooooo#ooo#ooo
oo#ooCoo#ooooooooooo
ooooo#oooooo#oooDooo
ooooo#ooooooooooooo#

20 10
oooooo#ooB#oooooooo#
#oo#o#oo##Cooo#oo#oo
o#ooooo#o###o#o#oo#o
ooo#o#o#oo#ooooo#ooo
o##o#o#ooo#ooo#oooo#
o#oooooo#oo##oo#oooo
oo###oo#oooooo#oo#oo
ooooo#Do#o#oo#o#oooo
o#o##A##o#o##oooo#o#
ooooooooooooooo#oo#o

20 10
oooooo#ooB#..o....o#
#oo#o#oo##Cooo#oo#..
o#ooooo#o###o#o#oo#.
ooo#o#o#oo#ooooo#o..
o##o#o#ooo#ooo#ooo.#
o#oooooo#oo##oo#oo..
oo###oo#oooooo#oo#o.
ooooo#Do#o#oo#o#oo..
.#o##A##o#o##oooo#.#
..ooooooooooooo#oo#o

0 0

Here's my output.

Code: Select all

10 1
A..B..C..D

10 1
A.CB...D.#

10 1
A.CB...D.#

10 1
A..B..C..D

12 3
oooooooooooo
oA..B..C..Do
oooooooooooo

12 3
oooooooooooo
oA..B..C..Do
oooooooooooo

12 5
oooooooooooo
oA..BooC..Do
o.ooooo.oooo
o.oooo..oooo
o......ooooo

12 5
oooooooooooo
ooooBooC..Do
A.oo.oo.ooo.
o.oo.o..ooo.
o......o...o

12 5
oooooooooooo
ooooBooCooDo
A.oo.oo.oo..
o.oo.oo.oo..
o..........o

6 2
A..BCD
oooo##

6 2
A..BCD
oooo##

6 6
A....B
.ooooo
.ooooo
.ooooo
.ooooo
C....D

5 5
ooAoo
oo.oo
B...C
oo.oo
ooDoo

5 5
ooAoo
B..oo
oo.oo
oo..C
ooDoo

4 4
A.#B
o...
#o.o
C.Do

20 10
oooooooooooooooooooo
A.....oooooooooooooo
ooooo.........B..ooo
ooooo.oooooooooo.ooo
ooooo.oooooooooo.ooo
ooooo.oooooooooo.ooo
ooooo.oooooooooo.ooo
oooooCoooooooooo.ooo
ooooooooooooooooDooo
oooooooooooooooooooo

20 10
oooooooooooooooooooo
A....#oooooooo#ooo##
oooo.#ooooo#ooBooooo
oooo...#o#oooo.ooooo
oooooo.o#.......oooo
ooooo#....#ooo#.oooo
ooooo..ooooo#oo.#ooo
oo#ooCoo#oooooo..ooo
ooooo#oooooo#oooDooo
ooooo#ooooooooooooo#

20 10
oooooo#..B#oooooooo#
#oo#o#..##C..o#oo#oo
o#.....#o###.#o#oo#o
...#o#o#oo#o....#ooo
.##o#o#...#oo.#..oo#
.#oooo..#.o##.o#.ooo
..###o.#o.....#o.#oo
o..oo#Do#o#oo#o#.ooo
o#.##A##o#o##....#o#
oo............o#oo#o

20 10
oooooo#..B#........#
#oo#o#..##C..o#oo#..
o#.....#o###.#o#oo#.
...#o#o#oo#o..oo#o..
.##o#o#...#oo.#ooo.#
.#oooo..#.o##.o#oo..
.o###o.#o.....#oo#o.
.oooo#Do#o#oo#o#....
.#o##A##o#o##....#.#
..............o#oo#o

0 0

Also, as you have probably noted, the output format in this problem is exactly the same as the input format. So it's a good idea to run your program against its own output -- new output should be exactly the same as the previous one.

[mysword]

ac now, it's a stupid error...
thanks to all
my program is at the top of the ranklist now

[Per]

Well, my solution is the fastest on the ranklist, but in the worst case it's O((mn)^2), too.
(I can improve it to O(mn log(mn)), but that's a bit tricky.)

Could you elaborate a bit on this point?

[mf]

my program is at the top of the ranklist now

I'm back

Could you elaborate a bit on this point?

Basically, I'm doing dynamic programming on this subproblem. A set of people A starts at a location u=(y,x). How many 'o' squares must they cover (including the starting one) to return to their respective houses? Let this number be f(u,A). I'll use map to denote the character at location u.

If A is an empty set:
f(u,A) = +infinity, if map=='#',
f(u,A) = 1, if map=='o',
f(u,A) = 0, otherwise.

If map is one of 'A'..'D', and map is in A: f(u, A) = f(u, A \ {map}).
(if one of the person has a house at u, then he'll go home, and the rest will go without him.)

In all other cases: f(u,A) = min f(u,A\B) + f(v,B),
where the minimum is taken over vertices v, adjacent to u; and over all non-empty subsets B of A.
Intuitively, some subset of people B will have to go to another vertex v, and the remaining people (A\B) will have to stay at u.

The above relation has just one problem: it can lead to circular dependencies when you substitute B=A into it: f(u,A) = min_v f(v,A) + f(u,0).
But this equation actually is similar to Bellman's shortest path equation, so to compute f(u,A) you can do the following:

1. Compute f(u,A) bottom-up on A: start with an empty set A, then consider all A's having one element, two elements, and so on.
2. For a fixed A, first evaluate the minimum over all subsets B with 0<|B|<|A|.
3. Finally, use a shortest-path algorithm (like Bellman-Ford or Dijkstra) to take care of the cases when B=A.

Overall, this algorithm reduces the original problem to 7 shortest path problems, and its running time is dominated by Dijkstra's algorithm.

Btw, may I ask for some hint on 10857?

[Per]

Overall, this algorithm reduces the original problem to 7 shortest path problems, and its running time is dominated by Dijkstra's algorithm.

Ah, very nice! I take it you use every house map \in A with potential f(u, A \ map) as the source(s) for step 3?

Btw, may I ask for some hint on 10857?

Certainly. A very small hint (let me know if you want a bigger one): think about 2^{-i}.

[mf]

I take it you use every house map \in A with potential f(u, A \ map) as the source(s) for step 3?

Well, actually I run a modification of Dijkstra -- I don't have 'single source'.
In step 2, I compute the initial distances to vertices (from my minimum equation), and in step 3, I just keep relaxing the edges from the vertex with lowest distance (like in normal Dijkstra.)

I'll send you my solution by pm.

Added 2006/01/31:
A small clarification ot my previous post: to solve a test case you can compute f(A,u) for all subsets of people {'A','B','C'}, then f({'A','B','C'}, <location of 'D'>) will give the minimum needed number of 'o' squares. Subsets can be represented with bitmasks.