Hackerearth policeman and theives problem

I am trying to solve the Policeman and Theives problem in Hackeearth website. I am able to reduce the time complexity but three test cases are failing. There seems to be a bug in the solution which causes a small mismatch. I am struggling to find the error for weeks. Below are the problem statement and my code,

Policeman and Thieves Problem statement:

You are given a grid of size that has the following specifications:

• Each cell in the grid contains either a policeman or a thief.
• A policeman can only catch a thief if both of them are in the same row.
• Each policeman can only catch one thief.
• A policeman cannot catch a thief who is more than K units away from the policeman.
  Write a program to find the maximum number of thieves that can be caught in the grid.

Input format

• First line: T (number of test cases)

  For each test case,

  • First-line contains Two space-separated integers N and K
  • Next N lines contain N space-separated characters (denoting each cell in the grid)

Output format

For each test case, print the maximum number of thieves that can be caught in the grid.

My code:

import java.io.*;
import java.util.*;

public class TestClass {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wr = new PrintWriter(System.out);
        int T = Integer.parseInt(br.readLine().trim());
        for(int t_i=0; t_i<T; t_i++)
        {
            String[] line = br.readLine().split(" ");
            int N = Integer.parseInt(line[0]);
            int K = Integer.parseInt(line[1]);
            char[][] A = new char[N][N];
            for(int i_A=0; i_A<N; i_A++)
            {
                String[] arr_A = br.readLine().split(" ");
                for(int j_A=0; j_A<arr_A.length; j_A++)
                {
                    A[i_A][j_A] = arr_A[j_A].charAt(0);
                }
            }

            int out_ = solution(A, K);
            System.out.println(out_);
            System.out.println("");
        }

        wr.close();
        br.close();
    }
    static int solution(char[][] A, int K){
        int count = 0;
        for(int i=0;i<A.length;i++){
            for(int j=0;j<A[i].length;j++){
                if(A[i][j]=='P'){
                    boolean thiefCaptured = false;
                    int x;
                    if(j-K >0){
                        x = j-K;
                    }else {
                        x = 0;
                    }
                    for(;x<j;x++) {
                        if (A[i][x] == 'T') {
                            A[i][x] = 'X';
                            A[i][j] = 'X';
                            count++;
                            thiefCaptured = true;
                            break;
                        }
                    }
                    int y;
                    if(j+K < A[i].length){
                        y = j+K;
                    }else{
                        y = A[i].length - 1;
                    }
                    for(;(y>j) && (thiefCaptured == false);y--){
                        if(A[i][y]=='T'){
                            A[i][y] = 'X';
                            A[i][j] = 'X';
                            count++;
                            break;
                        }
                    }
                }
            }
        }
        return count;
    }
}

My Logic
If an element is considered as the center of our search, then I am first looking for the thieves from the farthest left(by k units) and iterating towards the center. If the thief is not found, then I am looking for the thief from the farthest right(by k units) towards the center.

Failing test case input:

1
18 2
P P T T T P T P P T T P P P T P P T
P P P P T P P T P P T P P P T P T P
P P P T T T T T P P T P T P T T P T 
P P P P P P T P P P T T T P T T T P
P P T P P T P P P T T P P T P P P T
P T P P P P P P P P P P T T P T P P
T P T T T P P P P T P T T T T P T P
T T P T P P P P P P P T T T P T P P
P T T T T P T T P T P P P P T T P T
P T P P T T P P P P P T T P T P P P
P T P T T P T P T P T P P P P P P T
P T P P T P T P T P T P T T T P P P
T T P T P P P P P P T T T P T P T P
P T T P P P P P T P T P T P T P P T
P T P T T P T P T P P P P T P T P P
T P P P T P T P P P P P T T P P P P
P P T P P P P P P P P T T T P P T P
T T T P T P T P T P P T P P T P P P

Expected Ouput
113

Actual Output
112

Can you guys help me to figure out where I am going wrong? I am actually trying to figure out the solution for weeks but not able to progress. I know there is a different solution out there for the same question. But the thing is I would like to figure out the issue or the hole in my logic. Please help me out.

Link: Policemen and thieves on hackerearth

Your bug manifests in the line of i 11 (the 12th line if you count naturally/1-based).

P T P P T P T P T P T P T T T P P P

There are 8 thieves in this row. They can all be caught. In the following line a + indicates a policeman or policewoman successful of catching a thief, whereas - means one who doesn’t catch any.

+ T - + T + T + T + T + T T T + + -

(The first thief can be caught by either the police officer on the left or the right, it makes no difference to the count. There are yet more possible variations on who catches the first two thieves.)

Your program “catches” only 7 of the 8 thieves. Before this row you have a count of 68, which I believe is correct. After the row your count is 75, it should be 76.

In the row the first 5 thieves are caught as they should. Now what does the police officer at index 11 do? The thief to the left has already been caught. To the right are three thieves. Your second innermost loop counts down from y = j+K = 11 + 2 = 13, so catches the thief at index 13, leaving the thief at index 12 uncaught. The next police officer is at index 15.When K is 2, s/he cannot catch the thief at index 12, the distance is too great.

Edit: my idea for a solution. Since you have posted your solution, I think I can post mine without spoiling anything. My idea is for each thief to search left to right for a police officer who can catch that thief. I will start the search where the previous search left off. This ensures that each police officer catches only one thief.

	char[] row = { 'P', 'T', 'P', 'P', 'T', 'P', 'T', 'P', 'T',
			'P', 'T', 'P', 'T', 'T', 'T', 'P', 'P', 'P' };
	int k = 2; // The uppercase K from the problem
	
	int count = 0;
	// Index from where to search for the next police officer to catch a thief
	int pix = 0;
	for (int ix = 0; ix < row.length; ix++) {
		if (row[ix] == 'T') {
			if (pix < ix - k) {
				pix = ix - k;
			}
			int searchLimit = Math.min(row.length, ix + k + 1);
			while (pix < searchLimit && row[pix] != 'P') {
				pix++;
			}
			if (pix < searchLimit) { // Found
				count++;
				pix++;
			}
		}
	}
	
	System.out.println(count);

Output:

> 8

I am not using any auxiliary data structures, and I am not modifying the input array. I believe that this algorithm is efficient (I have not tried it on hackerearth).

The problem is symmetrical in police officers and thieves, so one may do it the other way around, for each police officer search for at thief to catch, it will work the same.

If the Math.min() call feels unusual, instead use either the ? : ternary operator or an if-else construct.

PS Maybe on hackerearth it would have been more appropriate to have P for police officer and H for hacker and ask how many hackers got away without being caught by police. Just joking.

I have added a logic to fix the bug pointed by @OleV.V. The added logic is, if two thieves are present consecutively to the Police, catch the nearest one first Now the failed test cases are passing but three of the previously passed test cases are getting timed out to time complexity issue. Below is the code, after addressing the bug pointed by @OleV.V. Now have to fix it in terms of time complexity

import java.io.*;
import java.util.*;
public class TestClass {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter wr = new PrintWriter(System.out);
int T = Integer.parseInt(br.readLine().trim());
for(int t_i=0; t_i<T; t_i++)
{
String[] line = br.readLine().split(" ");
int N = Integer.parseInt(line[0]);
int K = Integer.parseInt(line[1]);
char[][] A = new char[N][N];
for(int i_A=0; i_A<N; i_A++)
{
String[] arr_A = br.readLine().split(" ");
for(int j_A=0; j_A<arr_A.length; j_A++)
{
A[i_A][j_A] = arr_A[j_A].charAt(0);
}
}
int out_ = solution(A, K);
System.out.println(out_);
System.out.println("");
}
wr.close();
br.close();
}
static int solution(char[][] A, int K){
int count = 0;
for(int i=0;i<A.length;i++){
for(int j=0;j<A[i].length;j++){
if(A[i][j]=='P'){
ArrayList<Integer> leftarr = new ArrayList<>();
ArrayList<Integer> rightarr = new ArrayList<>();
int x;
if(j-K >0){
x = j-K;
}else {
x = 0;
}
for(;x<j;x++) {
if (A[i][x] == 'T') {
leftarr.add(x);
}
}
if(leftarr.size() != 0){
Collections.sort(leftarr);
A[i][leftarr.get(0)] = 'X';
A[i][j] = 'X';
count++;
continue;
}
int y;
if(j+K < A[i].length){
y = j+K;
}else{
y = A[i].length - 1;
}
for(;y>j;y--){
if (A[i][y]=='T'){
rightarr.add(y);
}
}
if(rightarr.size()!=0){
Collections.sort(rightarr);
A[i][rightarr.get(0)] = 'X';
A[i][j] = 'X';
count++;
}
}
}
}
return count;
}
}

I got a solution from GeekForGeeks website, which uses a really simple logic, based on the index of police and thief. I thought to myself, it's that simple!!!?? Well, it's how the world works. Anyways here is the optimum solution for the above problem,

import java.io.*;
import java.util.*;
public class TestClass {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter wr = new PrintWriter(System.out);
int T = Integer.parseInt(br.readLine().trim());
for(int t_i=0; t_i<T; t_i++)
{
String[] line = br.readLine().split(" ");
int N = Integer.parseInt(line[0]);
int K = Integer.parseInt(line[1]);
char[][] A = new char[N][N];
for(int i_A=0; i_A<N; i_A++)
{
String[] arr_A = br.readLine().split(" ");
for(int j_A=0; j_A<arr_A.length; j_A++)
{
A[i_A][j_A] = arr_A[j_A].charAt(0);
}
}
int out_ = solution(A, K);
System.out.println(out_);
System.out.println("");
}
wr.close();
br.close();
}
static int solution(char[][] arr, int K){
int count = 0;
for(int i=0;i<arr.length;i++){
ArrayList<Integer> thi = new ArrayList<>();
ArrayList<Integer> pol = new ArrayList<>();
for (int s = 0; s < arr[i].length; s++) {
if (arr[i]
展开收缩
 == 'P')
pol.add(s);
else if (arr[i]
展开收缩
 == 'T')
thi.add(s);
}
int l = 0, r = 0;
while (l < thi.size() && r < pol.size()) {
if (Math.abs(thi.get(l) - pol.get(r)) <= K) {
count++;
l++;
r++;
}
else if (thi.get(l) < pol.get(r))
l++;
else
r++;
}
}
return count;
}
}

Link: Policeman and Thieves Geek for Geeks