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.
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! 
1 Like