USACO 2020 US Open Bronze Problem 2

Problems and Contests
#1

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;
    static int calcRadius(int[] line)
    {
        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)
                        {
                            distances.add(Math.abs(j - i));
                        }
                    }
                }
            }
        }
        int ans = Collections.min(distances);
        return ans;
    }



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

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

        int max = 0;
        for(int i = 0; i < N; i++)
        {
            String[] line = in.readLine().split(" ");
            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 radius = calcRadius(map);
        //System.out.println("Radius = " + radius);
        //out.println(Radius);
        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++;
                index += radius;
                
            }
            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("]");
    }
}
#2

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.

#3

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.