# USACO Guide: Cow Dance Show

### The Problem

The problem text is shown below (USACO Page):

### Explanation

Whenever I see a problem looking for the highest/lowest possible value for a number that determines how some process is performed, I think about **binary searching for the answer**. Implementing a binary search for K is quite simple: the minimum possible stage size is 1 cow, the maximum possible stage size is N, the size of the herd. From there, implementing a binary search that adjusts the upper and lower bounds if a certain K value is valid is trivial.

Thus, we are left with the other part of the problem: validating K values. As we are using timed events that occur in a specific order, I thought to use a PriorityQueue. My code cycles through each cow in order of arrival, and adds them to the PrioirityQueue if there is space on the stage. When the stage is full, it updates a variable that keeps track of the last timed event and skips ahead to when the first cow on the stage exits. For each cow, a check is done to see if it is possible for the cow to complete its dance without exceeding the time limit. If not, then there is no need to continue the rest of the loop or check any other cows, and `false`

is returned. If the loop finishes without `false`

being returned, then `true`

is returned, as the show has finished.

### My Solution

```
import java.io.*;
import java.util.*;
public class CowDanceShow {
private static String fileNamePrefix = "cowdance";
private static int numCows, maxTime;
private static int[] cowDanceTimes;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new FileReader(fileNamePrefix + ".in"));
StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());
numCows = Integer.parseInt(stringTokenizer.nextToken());
maxTime = Integer.parseInt(stringTokenizer.nextToken());
cowDanceTimes = new int[numCows];
for (int i = 0; i < numCows; i++) {
stringTokenizer = new StringTokenizer(reader.readLine());
cowDanceTimes[i] = Integer.parseInt(stringTokenizer.nextToken());
}
reader.close();
// Binary search the smallest possible value of K that works
int min = 1, max = numCows;
while (min != max) {
int mid = (min + max) / 2;
if (validK(mid))
max = mid;
else
min = mid + 1;
}
PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter(fileNamePrefix + ".out")));
writer.println(min);
writer.close();
}
private static boolean validK(int k) {
int lastEventTime = 0;
PriorityQueue<Integer> danceQueue = new PriorityQueue<>();
for (int i = 0; i < cowDanceTimes.length; i++) {
if (danceQueue.size() == k)
// Stage is full, go to next event
lastEventTime = danceQueue.poll();
if (lastEventTime + cowDanceTimes[i] > maxTime)
// This cow would dance past the time limit, so this is not valid
return false;
danceQueue.add(lastEventTime + cowDanceTimes[i]); // Add the next event
}
return true; // All cows danced without passing the time limit
}
}
```

### Results

This solution successfully passes all test cases without exceeding the memory or runtime limits, as seen below: