PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
You are given a binary string S_i of length N, where each S_i = 1 denotes a person at position i.
Two people are considered friends if the absolute difference of their positions is \le K. A group of people are considered a friend group if each person in the group has at least one friend in the same group.
You can move each person atmost one step from their current position (multiple people can be at the same position after the movements). Determine the minimum number of friend groups you can have if you move the people optimally.
EXPLANATION:
(See the bolded texts in each case for a quick editorial 
)
We solve this problem greedily.
Iterate over characters of string S from left to right. When the current element is 0, continue iterating. Let x be the current index. Also, let last be the position of the last encountered person while iterating. Initially, let last = -1. Finally, maintain another variable ans, which is initially zero.
Case 1: If last = -1, it means person at position x is the first person from the left. Thus, since there are no people to his left, it is better to move this person right and bring him closer to people on the right.
Case to show why this is necessary
Consider N = 5, K = 1, S = 01001
If you do not move person at index 2 to the right, it won’t be possible to form a friendship with person at index 5, which is otherwise possible if you move person at index 2 and 5 to the right and left, respectively.
Then, update the value of last to x+1 (since the last encountered person is now at index x+1). Also, set ans to 1 (Signifies the start of a friend group).
Case 2: If x-last < K, moving the current person to the right by one step won’t break friendship with the last encountered person (on his left), and following similarly from the logic of Case 1, it is wise to move this person to the right.
Then, update the value of last to x+1 (since the current person is now at index x+1). Leave ans as it is (since there is no change to the number of friend groups).
Case 3: If x-last = K, it is best to leave the current person where he is. This is because moving him to the left does no benefit (already part of the last encountered person’s friend group) and moving him to the right does no benefit either (he may become friends with the next person in line, at the cost of losing his current friend group; so there is no overall decrease in the number of groups).
Then, update the value of last to x (since the current person is now at index x). Leave ans as it is (since there is no change to the number of friend groups).
Case 4: If x - last = K+1, the optimal strategy would be to move the current person to the left. Best case, he can maintain friendship with people both to his immediate left and right. Worst case, moving to the left would make it impossible for him to be friends with the person to his right.
Contrasted with the best and worse cases of not moving/moving to the right (where you can at best, only have friendship with the person on your right), it is best to move to the left.
Then, update the value of last to x-1 (since the current person is now at index x-1). Leave ans as it is (since there is no change to the number of friend groups).
Case 5: If x-last > K+1, it is best to move to the right, following the logic of Case 1 (not possible to be friends with anyone on the left).
Then, update the value of last to x+1 (since the current person is now at index x+1). Add 1 to ans, since there is now a new friend group.
TIME COMPLEXITY:
Since there is only one iteration done over the string S, the time complexity per test case is
SOLUTIONS:
Editorialist’s solution can be found here.
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters