Greedy algorithm

Medium.

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Arnab has made a team and he wants to fight with another team with some modified form of Kabaddi. In this game, all the players stand in a line. Now in a turn Arnab's team member can hold and win over an player of opposite team upto K distance apart. Each player of Arnab's team can win over only one opponent player and upto K distance. Player of Arnab's team is marked by 1 and opponents team is marked by 0.Find the maximum number of people Arnab's team can win over.

See original problem statement here

#### For Example :

``````1
101001 3

3

First player can win over 2nd player,3rd player can win over 4th player and last player can win over 2nd last player.``````

#### OBSERVATION:

The maximum number of defeated players increases if each player from Arnab's team deats the nearest player from opponent team.

For example, in the given test case player 1 should first try for nearest index lesser than k.

#### SOLVING APPROACH:

Let us see if we can apply greedy algorithm to this problem by referring data structures and algorithms.

A problem can be solved with greedy approch ,if it satisfies:

Greedy choice property: A global (overall) optimal solution can be reached by choosing the optimal choice at each step.

Optimal substructure: A problem has an optimal substructure if an optimal solution to the entire problem contains the optimal solutions to the sub-problems.

Since it satisfies both the properties, we can apply greedy here.

BRUTE FORCE:
Initialize a counter to 0.

Iterate through each index and loop if the current index contains 1.

The loop runs from (i-k) or 0 (whichever is maximum) to i+k or n-1 (whichever is minimum).

if the character at looped index in the given string is 0.increase the counter by 1.

``` #include <bits/stdc++.h>
using namespace std;

int main()
{
int t;cin>>t;
while(t--)
{
string s;int k;
cin>>s>>k;
int n=s.length();
int count=0;
for(int i=0;i<s.length();i++)
{if(s[i]=='1')
{for(int j=max(0,i-k);j<=min(n-1,i+k);j++)
{
if(s[j]=='0')
{
count++;
s[j]=-1;
break;
}
}}
}
cout<<count<<"\n";
}
return 0;
}
```

EFFICIENT SOLUTION:

Make two separate vectors each for 0 and 1.

Store the index of all 1s in one vector and 0s in the other.

Initiaze count to 0.

Simultaneously traverse both the vectors.

```#include <stdio.h>
#include<stdlib.h>
#include<string.h>
int solve(char arr[], int n, int k)
{
int res = 0;
int thi[n];
int pol[n];int x=0,j=0;
for (int i = 0; i < n; i++) {
if (arr[i] == '1')
pol[x++]=i;
else if (arr[i] == '0')
thi[j++]=i;
}
int l = 0, r = 0;
while (l < x && r < j) {
if (abs(thi[l] - pol[r]) <= k) {
res++;
l++;
r++;
}
else if (thi[l] < pol[r])
l++;
else
r++;
}

return res;
}
int main()
{

int t;
scanf("%d",&t);
while(t--)
{
char s;
int k;
scanf("%s",s);
scanf("%d",&k);

printf("%d\n",solve(s,strlen(s),k));
}
return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;
int solve(string arr, int n, int k)
{
int res = 0;
vector<int> thi;
vector<int> pol;
for (int i = 0; i < n; i++) {
if (arr[i] == '1')
pol.push_back(i);
else if (arr[i] == '0')
thi.push_back(i);
}
int l = 0, r = 0;
while (l < thi.size() && r < pol.size()) {
if (abs(thi[l] - pol[r]) <= k) {
res++;
l++;
r++;
}
else if (thi[l] < pol[r])
l++;
else
r++;
}

return res;
}
int main()
{

int t;
cin>>t;
while(t--)
{
string s;
int k;
cin>>s>>k;

cout<<solve(s,s.length(),k)<<endl;;
}
return 0;
}
```
```import java.util.*;

class Solution{
static int solve(String arr, int n, int k)
{
int res = 0;
ArrayList<Integer> thi=new ArrayList<>();
ArrayList<Integer> pol=new ArrayList<>();;
for (int i = 0; i < n; i++) {
if (arr.charAt(i) == '1')
else if (arr.charAt(i) == '0')
}
int l = 0, r = 0;
while (l < thi.size() && r < pol.size()) {
if (Math.abs(thi.get(l) - pol.get(r)) <= k) {
res++;
l++;
r++;
}
else if (thi.get(l) < pol.get(r))
l++;
else
r++;
}
return res;
}

public static void main (String[] args) {

Scanner sc=new Scanner(System.in);

int t=sc.nextInt();

while(t-->0)
{
String s=sc.next();
int k=sc.nextInt();

System.out.println(solve(s,s.length(),k));
}
}
}
```