[Solved] 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

  • 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

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

Constraints

  • 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 


Python

import sys
input = lambda:sys.stdin.readline()

int_arr = lambda: list(map(int,input().split()))
str_arr = lambda: list(map(str,input().split()))
get_str = lambda: map(str,input().split())
get_int = lambda: map(int,input().split())
get_flo = lambda: map(float,input().split())

mod = 1000000007

def solve(n,k,s):
ans = [i for i in range(n) if s[i] == “1”]

if ans == []:
print(0)
return

c = 1
ans[0] += 1
for i in range(1,len(ans)):
if abs((ans[i]+1)-ans[i-1]) <= k:
ans[i] += 1
elif abs(ans[i]-ans[i-1]) <= k:
pass
elif abs((ans[i]-1)-ans[i-1]) <= k:
ans[i] -= 1
else:
ans[i] += 1
c += 1
print(c)

for _ in range(int(input())):
n,k = get_int()
s = str(input())[:-1]
solve(n,k,s)


C++

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
int t;
cin>>t;

// your code goes here
while(t–>0){
ll n,k;
cin>>n>>k;
string s;
cin>>s;
vector<int> v;
for(int i=0;i<n;i++){
if(s[i]==’1′){
v.push_back(i);
}
}
if(v.size()==0){
cout<<0<<endl;
continue;
}
for(int i=0;i<v.size();i++){
if(i==0){
v[i]+=1;
}
else{
if(v[i]-v[i-1]<k){
v[i]+=1;
}
else if(v[i]-v[i-1]==k+1){
v[i]-=1;
}
else if(v[i]-v[i-1]!=k){
v[i]+=1;
}
}
}
int cnt=1;
for(int i=1;i<v.size();i++){
if(v[i]-v[i-1]>k) cnt++;
}
cout<<cnt<<endl;
}

return 0;
}


Java

import java.io.*;
import java.util.*;
class Solution{
public static boolean isFriend(int x, int y, int k){
if(Math.abs(x – y) <= k)return true;
return false;
}
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = U.tt(br.readLine());
while(t– > 0){
int inputs[] = U.tty(br.readLine().split(” “));
int N = inputs[0];
int K = inputs[1];
char x[] = br.readLine().toCharArray();
Stack<Integer> stack = new Stack<>();
int group = 0;
for(int i = 0; i < N; i++){
if(x[i] == ‘1’){
if(stack.isEmpty()){
stack.push(i+1);
}else{
if(isFriend(i, stack.peek(), K)){
if(isFriend(i+1, stack.peek(), K)){
stack.push(i+1);
}else{
stack.push(i);
}
}else if(isFriend(i-1, stack.peek(), K)){
stack.push(i – 1);
}else{
stack.clear();
group++;
stack.push(i + 1);
}
}
}
}
if(stack.size() > 0){
System.out.println(group+1);
}else{
System.out.println(group);
}

// System.out.println(result);
}
}
}
class U{
static int[] tty(String s[]){
int arr[] = new int[s.length];
for(int i = 0;i < s.length; i++){
arr[i] = Integer.parseInt(s[i]);
}
return arr;
}
static int[] tty(char s[]){
int arr[] = new int[s.length];
for(int i = 0;i < s.length; i++){
arr[i] = Character.getNumericValue(s[i]);
}
return arr;
}
static int tt(String s){
return Integer.parseInt(s);
}
static long tl(String s){
return Long.parseLong(s);
}
}

 


Also read : Black cells in a chessboard solution codechef

Also read : Large Square solution codechef

Also read : Bus full of passengers solution codechef

Friend Groups In A Line solution codechef 

 

No Comments, Be The First!

Your email address will not be published.