{"id":1422,"date":"2020-06-11T03:46:46","date_gmt":"2020-06-11T03:46:46","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1422"},"modified":"2022-03-28T23:44:47","modified_gmt":"2022-03-28T23:44:47","slug":"kabaddi-modified","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/kabaddi-modified\/","title":{"rendered":"KABADDI MODIFIED"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Greedy algorithm<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium.<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

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.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example :<\/h4>\n
1\n101001 3\n\n3\n\nFirst player can win over 2nd player,3rd player can win over 4th player and last player can win over 2nd last player.<\/code><\/pre>\n
OBSERVATION:<\/h3>\n
\n
The maximum number of defeated players increases if each player from Arnab’s team deats the nearest player from opponent team.<\/p>\n
For example, in the given test case player 1 should first try for nearest index lesser than k.<\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
\n
Let us see if we can apply greedy algorithm to this problem.<\/p>\n
A problem can be solved with greedy approch ,if it satisfies:<\/p>\n
Greedy choice property<\/strong>: A global (overall) optimal solution can be reached by choosing the optimal choice at each step.<\/p>\n
Optimal substructure<\/strong>: A problem has an optimal substructure if an optimal solution to the entire problem contains the optimal solutions to the sub-problems.<\/p>\n
Since it satisfies both the properties, we can apply greedy here.<\/p>\n
BRUTE FORCE:<\/h4>\n
Initialize a counter to 0.<\/p>\n
Iterate through each index and loop if the current index contains 1.<\/p>\n
The loop runs from (i-k) or 0 (whichever is maximum) to i+k or n-1 (whichever is minimum).<\/p>\n
if the character at looped index in the given string is 0.increase the counter by 1.<\/p>\n<\/blockquote>\n\t\t\t\t\t\t