CHAIRS - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest
Practice

Author: Hasan Jaddouh
Testers: Kamil Debowski
Editorialist: Hasan Jaddouh

Difficulty:

simple

Prerequisites:

none

Problem Statement:

There are N chairs placed in circular order, some of them are occupied by a child while the rest are empty, you want to change the places of children so that they all sit next to each other, in one move you can tell a child to go in clockwise or anti-clockwise order until he reaches first empty chair and sit on it. Find the minimum number of moves required to achieve the goal.

Explanation:

In each move one of two things will happen:

1- if the chosen child was on the boundary of a block of occupied chairs and he is told to move in the direction of this block:

then length of one block of empty chairs will increase by 1 and length of another block will decrease by 1 (if it became 0 length the block disappears).

2- if the chosen child was in the middle of a block of occupied chairs or he was on the boundary but he is told to move away from direction of this block:

then length of one block of empty chairs will decrease by 1 (if it became 0 length the block disappears) and new block with 1 empty chair will appear.

Let S be total number of empty chairs among all N chairs, the given goal (all children forming a consecutive segment) is equivalent to the following condition: all empty chairs form a consecutive segment. So let’s say we want to get only one block of empty chairs of length exactly S and since in one move one block of empty chairs will increase by at most 1 then the answer is at least S-A where A is length of longest block of empty chairs.

we can show that the answer is exactly S-A if we show that we can always choose a move such that we can increase length of any block we want, choose the block of empty chairs that you want to increase its length, it must be surrounded by two occupied chairs, pick anyone of them and tell him to go the direction away from this block.

so the solution is just to count total number of empty chairs and calculate the sizes of each block and subtract the maximum length of empty chairs block from total number of empty chairs

Time complexity: O(N)

Author’s and Tester’s Solutions

Setter
Tester

4 Likes
2

What if I calculate number of one’s as O and maximum size of one’s segment as S and wouldn’t the answer be O-S?
For example:-
11001011 O=5 and S=4 and answer is “1”.

3

What if we calculate maximum continuous no. of zero’s as C and total count of zero’s as C1 then answer would be C1-C.

1 Like
4

Is any alternative solution to this problem? And what if it is linear arrangement instead of circular chair arrangemenets?

5

1000010000

1 Like
6

The number of one’s is 2 and largest segment of one’s is 1 and answer would be 2-1=1. And in fact we require only one move to complete the arrangement.

7

What will be the answer for 110110000 ?Algorithm gives ans 1 but we require at least 2 moves.
As if i remove longest 0 sub-string then i get 11011 and for this i require at least 2 moves.

1 Like
8

Actually the correct answer is 4 because if you told the child in index 5 (0-based) to move to left direction, he will sit in chair in index 4 because it’s first available chair so you need 3 extra moves

9

@heathorjoker , the answer is indeed 1. Pick the child sitting at position 4 (0-based indexing) and tell him to move left. He will find an empty chair at position 2 and he will sit there.
initially : 110110000
pick the child marked in bold : 1101__1__0000 tell him to go left …
finally : 11__1__100000… So ans = 1 .