2016 Jan Gold Problem 1 Angry Cows

Official Problem Statement

Angry Cows

Problem

The farmer has lined up N bales of hay, each of different weights, and each located at different points along a line. The cows get into a dispute about who gets to eat which bale, and as a result, decide to blow them up. When a bale explodes, it creates an explosion of radius R (where R is a positive integer). This explosion can trigger other bales within the explosion radius to explode, potentially leading to a chain reaction. Each bale can only explode once.

Given the positions of the bales of hay along the line, and given that the cows have the ability to set the explosion radius of the first bale they explode, your task is to calculate the maximum number of bales they can explode.

Solution

This problem can be solved by using a binary search on the explosion radius, and a two pointer method to simulate the chain reaction.

• Sort the bales according to their position along the line.
• Use binary search to find the minimum explosion radius that can blow up all the bales. The lower limit of the search is 1 and the upper limit is the maximum difference between the positions of the bales.
• For each possible explosion radius, use two pointers to iterate through the bales. One pointer represents the leftmost bale that can still be blown up (initially this is the first bale), and the other represents the rightmost bale that can be blown up (initially this is also the first bale).
• The left pointer advances whenever the difference in the positions of the bales at the left and right pointers is greater than the current explosion radius. The right pointer advances whenever the difference in positions is less than or equal to the explosion radius.
• The binary search checks if it is possible to reach the end of the array of bales with the current explosion radius. If it is possible, the search continues with a smaller radius, otherwise it continues with a larger radius.
• The minimum explosion radius which can blow up all bales is the answer.

Complexity

The complexity of the solution is O(N log N) due to the sorting and binary search, where N is the number of bales. The two pointer method takes linear time for each explosion radius checked, but since the explosion radius is varied logarithmically, the overall complexity is still O(N log N). This is efficient enough for the problem constraints.

Code

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

constexpr int INF = 2000000000;

int main() {
    std::ios::sync_with_stdio(false);
    freopen("angry.in", "r", stdin);
    freopen("angry.out", "w", stdout);

    int N;
    std::cin >> N;

    std::vector<int> A(N);
    for (int &a : A) {
        std::cin >> a;
        a *= 2;  // Multiplying by 2 for decimal precision
    }

    // Sort and remove duplicates
    std::sort(A.begin(), A.end());
    A.erase(std::unique(A.begin(), A.end()), A.end());

    std::vector<int> DP[2];
    for (int it = 0; it < 2; it++) {
        int lastIdx = 0;
        DP[it].resize(N, INF);
        DP[it][0] = -2;

        for (int i = 1; i < N; i++) {
            while (lastIdx + 1 < i && std::abs(A[i] - A[lastIdx + 1]) > DP[it][lastIdx + 1] + 2) {
                lastIdx++;
            }
            DP[it][i] = std::min(std::abs(A[i] - A[lastIdx]), DP[it][lastIdx + 1] + 2);
        }

        std::reverse(A.begin(), A.end());
    }

    std::reverse(DP[1].begin(), DP[1].end());

    int i = 0;
    int j = N - 1;
    int result = INF;

    while (i < j) {
        result = std::min(result, std::max((A[j] - A[i]) / 2, 2 + std::max(DP[0][i], DP[1][j])));

        if (DP[0][i + 1] < DP[1][j - 1]) {
            i++;
        } else {
            j--;
        }
    }

    // Print the result with one decimal place
    std::cout << result / 2 << '.' << (result % 2 ? 5 : 0) << '\n';

    return 0;
}

Java

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

public class AngryCows {
    private static final String INPUT_FILE = "angry.in";
    private static final String OUTPUT_FILE = "angry.out";

    public static void main(String[] args) {
        ArrayList<Integer> locations = new ArrayList<>();

        try (BufferedReader reader = new BufferedReader(new FileReader(INPUT_FILE));
             PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter(OUTPUT_FILE)))) {

            // Parse the number of haystacks
            int numHaystacks = Integer.parseInt(reader.readLine());

            // Parse all the haystack locations
            for (int i = 0; i < numHaystacks; i++) {
                locations.add(Integer.parseInt(reader.readLine()));
            }

            // Sort the locations in ascending order
            Collections.sort(locations);

            int beg = 0;
            int rad = 0;
            int end = numHaystacks - 1;
            int rad1 = 0;

            double bestRadius = Double.MAX_VALUE;

            while (true) {
                double val = Math.max(Math.max(rad, rad1) + 1, (double) (locations.get(end) - locations.get(beg)) / 2);
                bestRadius = Math.min(bestRadius, val);

                int pot = Math.max(rad + 1, locations.get(beg + 1) - locations.get(beg));
                int pot1 = Math.max(rad1 + 1, locations.get(end) - locations.get(end - 1));

                if (pot < pot1) {
                    rad = pot;
                    int index = beg;
                    while (index < numHaystacks - 1 && locations.get(beg) + pot >= locations.get(index + 1)) {
                        index++;
                    }
                    beg = index;
                } else {
                    rad1 = pot1;
                    int index = end;
                    while (index > 0 && locations.get(end) - pot1 <= locations.get(index - 1)) {
                        index--;
                    }
                    end = index;
                }

                if (end <= beg) {
                    bestRadius = Math.min(bestRadius, Math.max(rad, rad1));
                    break;
                }
            }

            writer.printf("%.1f", bestRadius);

        } catch (IOException e) {
            System.err.println("Failed to read or write file: " + e.getMessage());
            e.printStackTrace();
        }
    }
}

Python

import sys

def read_input(file):
    with open(file, 'r') as f:
        lines = f.readlines()
        n = int(lines[0])
        locations = [int(x) for x in lines[1:]]
    return n, locations

def write_output(file, best_radius):
    with open(file, 'w') as f:
        f.write(f'{best_radius:.1f}\n')

def main():
    INPUT_FILE = 'angry.in'
    OUTPUT_FILE = 'angry.out'

    num_haystacks, locations = read_input(INPUT_FILE)

    # Sort the locations in ascending order
    locations.sort()

    beg = 0
    rad = 0
    end = num_haystacks - 1
    rad1 = 0

    best_radius = float('inf')

    while True:
        val = max(max(rad, rad1) + 1, (locations[end] - locations[beg]) / 2)
        best_radius = min(best_radius, val)

        pot = max(rad + 1, locations[beg + 1] - locations[beg])
        pot1 = max(rad1 + 1, locations[end] - locations[end - 1])

        if pot < pot1:
            rad = pot
            index = beg
            while index < num_haystacks - 1 and locations[beg] + pot >= locations[index + 1]:
                index += 1
            beg = index
        else:
            rad1 = pot1
            index = end
            while index > 0 and locations[end] - pot1 <= locations[index - 1]:
                index -= 1
            end = index

        if end <= beg:
            best_radius = min(best_radius, max(rad, rad1))
            break

    write_output(OUTPUT_FILE, best_radius)

if __name__ == "__main__":
    main()