PROBLEM LINK:
Setter: Nagulan S
Editorialist: Nagulan S
DIFFICULTY:
Easy
CONCEPT:
PROBLEM:
The zombie’s infection level is graded from 0 to 9, 0 being the most severe case and 9 being the weakest case. The mad scientist tells you that all zombies with infection levels greater than or equal to D can be cured but the zombies with infection levels less than D cannot be cured as they are critically affected. However, you have K special antidotes to contain critically infected zombies, i.e. if a zombie’s infection level is less than D, by using the special antidote you can make them greater than D.
There are N zombies walking in a line. Your job is to pick up a contiguous group of zombies to cure such that all the zombies in this group can be cured. The aim of the journey is to pick up as many zombies as you can and save them.
EXPLANATION
The aim of the problem is to cure the maximum number of zombies and it is known that an infinite number of zombies with a level greater than or equal to D can be cured. So our ultimate aim is to select a substring of zombies such that it contains:
at most K zombies with level < D and
any number of zombies with level >= D.
Subtask-1 (Brute Force)
The substring of zombies we need may be present at any part of the string starting from any index. So the brute force approach is to assume the substring starts from i th index and traverses from i th position till the index before we meet the K+1 th zombie with level <D. The common doubt arising here would be “why K+1 th zombie but not kth zombie because we only have K special antidote?”. The reason we do this is to ensure that we also take into consideration the zombies with level >=D after the K th zombie we identified with level <D. So the maximum zombies we get in this iteration starting from i th position is calculated by excluding the final K+1 th zombie we encountered. This repeated for all i from 0 to N-1, and the maximum of all the iteration results is the final result.
Subtask-2 (Sliding Window)
The substring of zombies we need is present within two indices (start, end) in the string, and we know at a time only k zombies with level <D can be present within our assumed substring. So lefts initialize two pointers start and end to zero at the beginning, now we need to increment the end pointer until we have K zombies of level <D within start and end. Once the end pointer meets the K+1 th zombie with level <D our taken substring becomes invalid, so we need to stop incrementing the end pointer and start incrementing the start pointer till we have only k zombies with level <D inside start and end, then we start our incrementation of endpointer until we meet the next K+1 zombie. This step is method is repeated till the end pointer reaches N-1 th index. At each iteration, we store the length of the current substring formed and print finally the maximum among them.
TIME COMPLEXITY
Time complexity is O(N^2) for subtask-1
Time complexity is O(N) for subtask-1
SOLUTIONS:
Setter’s Solution in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main(String[] args)throws IOException {
Scanner ob=new Scanner(System.in);
int n,k,d,i,start,end,maxlength,currlength,t;
t=ob.nextInt();
while(t-->0) {
n=ob.nextInt();
k=ob.nextInt();
d=ob.nextInt();
int arr[]=new int[n];
for(i=0;i<n;i++) {
arr[i]=ob.nextInt();
}
start=0;
end=0;
maxlength=0;
currlength=0;
while(end<n) {
if(k<0) {
while(arr[start]>=d)
start++;
k++;
end++;
start++;
currlength=end-start;
}
else {
if(arr[end]<d) {
k--;
}
if(k>=0){
end++;
currlength++;
}
}
if(maxlength<currlength)
maxlength=currlength;
}
System.out.println(maxlength+"\n");
}
}
}
Feel free to share your approach, if you want to. (even if its same 
) . Suggestions are welcomed as always had been. 