# USACO 2020 US Open Bronze Problem 2

Hi everyone,

I was working on problem 2. On test case number 2 I got 7 instead of 6. I walked through and debugged the test case and my program looked correct. Why did I get 6? Here is my code:

``````import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class SocialDistancing2 {
final static int SICK = 2;
final static int HEALTHY = 1;
{
ArrayList<Integer> distances = new ArrayList<>();
for(int i = 0; i < line.length; i++)
{
if(line[i] == HEALTHY)
{
for(int j = 0; j < line.length; j++)
{
if(j != i)
{
if(line[j] == SICK)
{
}
}
}
}
}
int ans = Collections.min(distances);
return ans;
}

public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("socdist2.out")));

//System.out.println("N = " + N);
int[][] input = new int[N][2];

int max = 0;
for(int i = 0; i < N; i++)
{
input[i][0] = Integer.parseInt(line[0]);
input[i][1] = Integer.parseInt(line[1]);
if(Integer.parseInt(line[0]) > max) max = Integer.parseInt(line[0]);
}
in.close();

//Stores user input. 0 = no cow, 1 = non-infected cow, 2 = infected cow

int[] map = new int [max + 1];

for(int i = 0; i < N; i++)
{
int location = input[i][0];
int hasCorona = input[i][1];

if(hasCorona == 0)
map[location] = HEALTHY;
else if(hasCorona == 1)
map[location] = SICK;

}

//System.out.println(Arrays.toString(map));
//System.out.println("Input = " + Arrays.deepToString(input));
//System.out.println("Max = " + max);

//System.out.println("Map = " + Arrays.toString(map));

//printMap(map);

int ans = 0;
int index = 0;
while(index < map.length)
{
if(map[index] == SICK)
{
//System.out.println("cow position " + index + " is sick, next index to check is = " + (index + radius));
ans++;

}
else index++;
}

out.println(ans);
//System.out.println(ans);

out.close();

}

private static void printMap(int[] map) {
System.out.print("map: [");
for (int i = 0; i< map.length; i++)
{
System.out.print(i + ":" + (map[i] == 0 ? "-" : (map[i] == SICK) ? "S" : "H") + ", ");
if (i > 0 && i % 30 == 0) System.out.println("");
}
System.out.println("]");
}
}
``````

Uh, why not just print out all the relevant info? The test case is pretty small, so it shouldn’t take much time to debug.

All of your code is correct until the last part, where you calculate the answer.
The answer should be the number of “gaps” between consecutive pairs of sick cows that are greater than or equal to `radius`.
This is because `radius - 1` is the maximum distance such that a cow can infect another cow, so any pair of cows greater than or equal to the maximum distance must have been infected separately.
To check each pair of sick cows, you can create a variable `last` that stores the position of the last infected cow (-infinity if none). When a new infected cow is processed, check if the “gap” between the last infected cow and the current cow is greater than or equal to radius, increment `ans` by one if so. You also need to update `last` if the current cow is infected.
Below is my code for the last part.

``````int ans = 0;
int last = -1000000;
for (int index = 0; index < map.length; index++)
{
if(map[index] == SICK && index - last > radius)
ans++;
if (map[index] == SICK)
last = index;
}
``````

You might also want to be careful if every cow is infected, because then your array `distances` would be empty, so an exception will be thrown if you get in `min`.