(Analysis by Eric Hsu)

Solution 1: We can greedily build towers one at a time as such: process the remaining cows from heaviest to lightest, adding a cow to the current tower if possible. Repeat this $M$ times, once for each tower.

Code:

N, M, K = map(int, input().split())

cows = []
for _ in range(N):
w, a = map(int, input().split())
cows += [w] * a
cows.sort(reverse=True)

for _ in range(M):
remaining_cows = []
current_cow = 1e100 #arbitrary large number
for cow in cows:
if cow + K <= current_cow:
current_cow = cow
else:
remaining_cows += [cow]

if len(remaining_cows) == 0:
break
cows = remaining_cows

Time Complexity: $O(c^2)$, where $c$ is the number of cows.

Solution 2a: Process the cows from heaviest to lightest. When we process a cow, we try to put it on any tower. This is always optimal since we could put any of the remaining cows on a tower that the current cow can be placed on, so it doesn't matter where we place the current cow.

Code:

N, M, K = map(int, input().split())

cows = []
for _ in range(N):
w, a = map(int, input().split())
cows += [w] * a
cows.sort(reverse=True)

towers = [1e100]*min(M, len(cows))
for cow in cows:
for i in range(M):
if cow + K <= towers[i]:
towers[i] = cow
break

Solution 2b: Instead of placing the cow on an arbitrary tower, we only try to place it on the tower with the heaviest cow on top. This is because if it is possible to place a cow on a tower, it is possible to place it on the tower with the heaviest cow on top.

Time Complexity: $O(c^2)$

Note that the number of towers is bounded by the number of cows, since if the number of towers is greater than the number of cows, we can just remove the excess towers.

We can optimize solution 2b in subtask 1 by speeding up the search for the heaviest cow. We can do this by keeping a sorted queue of towers where the front of the queue is the tower with the heaviest cow on top. When we place the current cow on a tower, we move that tower to the back of the queue since the current cow is lighter than all of the cows processed before it.

Time complexity: $O(c\log c)$, where the log factor comes from sorting the cows by weight.

Code:

from collections import deque
N, M, K = map(int, input().split())

cows = []
for _ in range(N):
w, a = map(int, input().split())
cows += [w] * a
cows.sort(reverse=True)

towers = deque([1e100]*min(M, len(cows)))
for cow in cows:
if cow + K <= towers[0]:
towers.popleft()
towers.append(cow)

Subtask 3: Instead of processing individual cows and towers, compress them into (weight, count) pairs. See the code for the details. The time complexity of the remaining portion of the code after the sorting step is bounded by the number of insertions to and deletions from the queue. Both of these are at most $N$, so the time complexity of the remaining portion is $O(N)$.

Overall time complexity: $O(N \log N)$

Code:

from collections import deque
N, M, K = map(int, input().split())

pairs = []
for _ in range(N):
w, a = map(int, input().split())
pairs.append([w, a])
pairs.sort(reverse = True)

towers = deque()
towers.append([1e100, M])
for w, a in pairs:
remaining = a
while len(towers) > 0 and remaining > 0 and w + K <= towers[0][0]:
if towers[0][1] > remaining:
towers[0][1] -= remaining
remaining = 0
else:
remaining -= towers[0][1]
towers.popleft()
cnt = a - remaining
if cnt > 0:
towers.append([w, cnt])

Using an ordered set rather than a deque can also pass with given constraints.

Danny Mittal's code:

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

public class BovineAcrobaticsBR {

public static void main(String[] args) throws IOException {
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
int n = Integer.parseInt(tokenizer.nextToken());
int m = Integer.parseInt(tokenizer.nextToken());
int k = Integer.parseInt(tokenizer.nextToken());
CowGroup[] cowGroups = new CowGroup[n];
for (int j = 0; j < n; j++) {
tokenizer = new StringTokenizer(in.readLine());
int weight = Integer.parseInt(tokenizer.nextToken());
int amt = Integer.parseInt(tokenizer.nextToken());
cowGroups[j] = new CowGroup(weight, amt);
}
Arrays.sort(cowGroups, Comparator.comparingInt(group -> group.weight));

TreeSet<CowGroup> treeSet = new TreeSet<>(Comparator.comparingInt(group -> group.weight));
int towers = 0;
long answer = 0;
for (CowGroup group : cowGroups) {
int disp = group.amt;
while (disp > 0) {
CowGroup floor = treeSet.floor(new CowGroup(group.weight - k, 0));
if (floor == null) {
break;
}
treeSet.remove(floor);
if (floor.amt <= disp) {
disp -= floor.amt;
} else {
treeSet.add(new CowGroup(floor.weight, floor.amt - disp));
disp = 0;
}
}
towers -= group.amt - disp;
int canAdd = Math.min(group.amt, m - towers);
}