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.