[Solution] Friend Groups In A Line solution codechef

Friend Groups In A Line solution codechef


There are NN positions in a queue. Given a binary string SS of length NN, where Si=Si= '11' denotes, there is a person standing in the ithith position.

The distance between two people standing in the ithith and jthjth positions respectively in the queue is ij∣i−j∣, where x∣x∣ denotes the absolute value of xx. Now, two people are considered to be friends if they are at a distance less than or equal to KK.

Let’s say, there are MM people, P1,P2,,PMP1,P2,…,PM standing one after another in a queue such that for each 1i<M1≤i<MPiPi and Pi+1Pi+1 are friends, then all the MM people are considered to be in a friend group.

For example, consider the string S=S= "11010011101001" and K=2K=2.

Let’s denote the people standing in the 1st1st2nd2nd4th4th and 7th7th positions in the queue by P1,P2,P3,P4P1,P2,P3,P4 respectively. Now, P1P1 and P2P2 are friends as the distance between them is 11P2P2 and P3P3 are also friends as the distance between them is 22P4P4 is not friend with anyone. Hence P1,P2,P3P1,P2,P3 form a friend group and P4P4 forms a separate friend group.

Now each person can move one position right or one position left or stay in the same position. However, they can’t move out of the queue. Find the minimum number of friend groups they can form if they move optimally.

It is possible that there is more than one person standing in the same position after the movements.

Input Format Friend Groups In A Line solution codechef

  • The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains two integers N,KN,K.
  • The second line of each test case contains a string SS.

Output Format Friend Groups In A Line solution codechef

For each test case, print a single line containing one integer – the minimum number of friend groups.

Constraints Friend Groups In A Line solution codechef

  • 1T51041≤T≤5⋅104
  • 1N1051≤N≤105
  • 0KN0≤K≤N
  • SS contains only characters ‘00` and ‘11
  • The sum of NN over all test cases does not exceed 106106.

Sample Input 1 

3
6 2
010010
4 0
1001
7 2
1101001

Sample Output 1 

1
2
1

Explanation

  • Test case 11: If the person standing in the 5th5th position moves one position left, the distance between the two people becomes 22 which is equal to KK. So they form a friend group.

  • Test case 22: If the person standing in the 1st1st position moves one position right and the person standing in the 4th4th position moves one position left, the string becomes “01100110“, still the distance between them is greater than K=0K=0. So they form two separate friend groups.

  • Test case 33: Initially first three people form a friend group and the fourth person forms a separate friend group. Now if the fourth person moves one position left, he becomes a friend of the third person as the distance between these two people is equal to 22, and hence all the four people belong to one friend group.

Solution: Click here

Friend Groups In A Line solution codechefsolution codechefcodechef solutioncodechef freshersonline

Leave a Comment