FRIENDGR - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY

PREREQUISITES:

Greedy

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 :tongue:)

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

O(N)

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

1 Like

how can we solve using DP? any body has solution with explanation ?

Read this comment : https://codeforces.com/blog/entry/93962#comment-829827. If you have any doubt then reply back.

1 Like

You can see my solution. I used a DP array of Nx3 size and iterated over the indices containing ‘1’. dp[i][0] stores minimum number of groups formed if we don’t move current person. dp[i][1] stores minimum number of groups formed if we move current person to right. dp[i][2] stores minimum number of groups formed if we move current person to left.
Transitions are quite easy and self-explanatory. Just check the distance with the if statements and make transitions.

My submission

https://www.codechef.com/viewsolution/49958363

Can anyone give me any counter testcase for my submission

Quick Explanation:
move this person right. move this person to the right. leave the current person where he is . move the current person to the left . move to the right.

Input :
43 4
0001011101101100011100101000011101000001000
Expected Output:
1
Obtained Output:
2

Input:
19 2
1110011010110010011
Expected Output:
1
Obtained Output:
2

thanks man , it took me some time to understand transitions but i got it thanks agian

Solution: 50185333 | CodeChef
Why my solution is giving NZEC ?

Solution: 50467112 | CodeChef
Why my solution is giving wrong answer ? Is there any test case I am missing ?