Page 1 of 1

10863 - Shovelling Snow

Posted: Mon Jun 20, 2005 9:33 pm
by 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 8) . (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

Posted: Tue Jun 21, 2005 9:28 am
by Martin Macko
There are just few patterns how the smallest shovelled area may look like. Try find them all, this could help you.

Posted: Tue Jun 21, 2005 11:02 pm
by Endrju
Thank you Martin, I think I understand the idea now :D

10863, help

Posted: Mon Dec 12, 2005 3:58 pm
by 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.... :(

Re: 10863, help

Posted: Mon Dec 12, 2005 4:27 pm
by Martin Macko
mysword wrote: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?
Problem statement wrote:During the summers, going from any of the four friends

Posted: Mon Dec 12, 2005 4:46 pm
by 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.

Posted: Wed Dec 14, 2005 2:22 pm
by mysword
ac now, it's a stupid error...
thanks to all
my program is at the top of the ranklist now :)

Posted: Wed Dec 14, 2005 3:49 pm
by Per
mf wrote: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?

Posted: Wed Dec 14, 2005 9:16 pm
by mf
mysword wrote:my program is at the top of the ranklist now
I'm back ;)
Per wrote: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?

Posted: Wed Dec 14, 2005 10:02 pm
by Per
mf wrote: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}.

Posted: Wed Dec 14, 2005 10:18 pm
by 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.