## 10863 - Shovelling Snow

**Moderator:** Board moderators

### 10863 - Shovelling Snow

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

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
- A great helper
**Posts:**481**Joined:**Sun Jun 19, 2005 1:18 am**Location:**European Union (Slovak Republic)

### 10863, help

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

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
- A great helper
**Posts:**481**Joined:**Sun Jun 19, 2005 1:18 am**Location:**European Union (Slovak Republic)

### Re: 10863, help

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

I think there are no such test cases; my accepted program would just output the input.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?

Well, my solution is the fastest on the ranklist, but in the worst case it's O((mn)^2), too.My algorithm runs in O(n^4), but TLE....

(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
```

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

I'm backmysword wrote:my program is at the top of the ranklist now

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.Per wrote:Could you elaborate a bit on this point?

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?

Last edited by mf on Wed Dec 14, 2005 10:09 pm, edited 1 time in total.

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?mf wrote: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?

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

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.