Hi, I am unable to come up with any solution for this problem. Can any one explain me the recursive/DP solution of the 1st problem came in ZIO 2011.

Recursive Algorithm would be helpful.

# How to solve the 1st question in ZIO 2011

**jvjplus**#1

**joffan**#3

You can treat the two dimensions separately; spread the guards so that they cover all the north-south roads, then spread them so that they cover the east-west roads. The “condition” about two guards not occupying the same position is trivially true for the minimum-move solution, since generally the nearest guard moves to cover a gap.

For example, the profile of guards given on a north-south section for map(a) looks like this:

`EW road: 1 2 3 4 5 6 7 8 9`

guards: 0 0 0 0 4 2 2 0 1

For any uncovered (zero) east-west road here, we can find out which side the guard needs to come from by checking which side has an excess - so road 8, for example, will be covered from above. For this small set we can rearrange the profile one step at a time:

- row 1 is empty, find the nearest non-empty row
- move a guard on row 5 to row 1 (4 steps)
- move a guard on row 5 to row 2 (3 steps)
- move a guard on row 5 to row 3 (2 steps)
- move a guard on row 5 to row 4 (1 step - leaving row 5 unguarded)
- move a guard on row 6 to row 5 (1 step)
- row 6 is (now) OK
- move the spare guard on row 7 to row 8 (1 step)
- row 8 is (now) OK
- row 9 is OK.

`EW road: 1 2 3 4 5 6 7 8 9 steps total`

guards: 0 0 0 0 4 2 2 0 1

move: 1 0 0 0 3 2 2 0 1 4 4

move: 1 1 0 0 2 2 2 0 1 3 7

move: 1 1 1 0 1 2 2 0 1 2 9

move: 1 1 1 1 0 2 2 0 1 1 10

move: 1 1 1 1 1 1 2 0 1 1 11

move: 1 1 1 1 1 1 1 1 1 1 12

Total of 12 steps to flatten this profile - then similarly for the east-west section:

`NS road: 1 2 3 4 5 6 7 8 9 steps total`

guards: 0 1 1 1 2 1 2 0 1

move: 1 0 1 1 2 1 2 0 1 1 1

move: 1 1 0 1 2 1 2 0 1 1 2

move: 1 1 1 0 2 1 2 0 1 1 3

move: 1 1 1 1 1 1 2 0 1 1 4

move: 1 1 1 1 1 1 1 1 1 1 5

5 more steps for a total of 17 steps to complete the conditions.