KABADDI MODIFIED

CONCEPTS USED:

Greedy algorithm

DIFFICULTY LEVEL:

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.

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()
    {
     //write your code here
     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[1005];
     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') 
            pol.add(i); 
        else if (arr.charAt(i) == '0') 
            thi.add(i); 
    }    
    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));
     }
     }
    }

[forminator_quiz id="1427"]

This article tried to discuss Greedy algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm you can check out MYCODE | Competitive Programming.