How to solve the 1st question in ZIO 2011

help
dynamic-programming
recursion
zio
zio2011

#1

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.


#2

@vijju123 can u help, zio is very near.


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


#4

@ista2000 plz help


#5

thanks a lot! :smiley: