Shifting Homes :
Difficulty Level : Medium
Submissions : 514
Asked In :
Marks :10
: 8 | : 0
Homes are aligned in a row. In any given row, maximum half of the homes are occupied by families. In a season,people got infected and all families must vacate homes to move to initially unoccupied homes.
Movements are sequential and not parallel (i.e one family completes the movement, then only the second family starts). To reduce the overall time taken, it's better to move to a nearby empty room than a farther one. $$$i^{th}$$$ home to $$$j^{th}$$$ home movement results in $$$|j-i|$$$ time. Minimize the overall time taken by all families to complete the movement to unoccupied homes.
First line contains integer $$$1 \le N \le 10000$$$, Number of homes
Second line contains a string $$$S$$$, of length $$$N$$$, denoting occupied and unoccupied homes($$$1$$$ = occupied, $$$0$$$ = unoccupied)
Number of unoccupied homes $$$\ge$$$ Number of occupied homes
Integer denoting minimum overall time taken for all families to move to unoccupied homes
4 1001
2
8 00101101
8
