How to solve the 1st question in ZIO 2011

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.

@ista2000 plz help

@vijju123 can u help, zio is very near.

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.

1 Like

thanks a lot! :smiley:

1 Like