Official Analysis (C++ and Java)

Solution 1

Let's consider the cows in descending order of height.

First, notice that the number of stalls we can place the tallest cow in is the number of stalls with height greater than or equal to the height of this cow.

Next, the number of stalls we can place the second tallest cow in is the number of stalls at least as tall as this cow, minus one, since the tallest cow already occupies one of these stalls. The key observation here is that this number is independent of which stall the tallest cow is placed in (which is why we sort the cows in descending order).

Similarly, the number of stalls the third tallest cow can be placed in is the number of stalls at least as tall as this cow, minus two, since the two tallest cows occupy two of these stalls.

This pattern continues, so we can compute the answer by simply multiplying all of these numbers (choices) together.

Implementation

Time Complexity: O(N2)\mathcal{O}(N^2)

C++

#include <bits/stdc++.h>
using namespace std;


int main() {
	int n;
	cin >> n;
	vector<int> cows(n);
	vector<int> stalls(n);
	for (int i = 0; i < n; i++) { cin >> cows[i]; }
	for (int i = 0; i < n; i++) { cin >> stalls[i]; }

Java

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


public class JustStalling {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());


		int[] cows = new int[n];

Python

n = int(input())
cows = sorted(map(int, input().split(" ")))
stalls = sorted(map(int, input().split(" ")))


possible_places = [0] * n
# Create a list containing the number of stalls each cow can use.
for i in range(n):
	for j in range(n):
		if cows[i] <= stalls[j]:
			possible_places[i] += 1

Solution 2

Instead of iterating through the stalls each time, we can use two pointers.

Implementation

Time Complexity: O(Nlog⁡N)\mathcal{O}(N \log N)

C++

#include <bits/stdc++.h>
using namespace std;


int main() {
	int n;
	cin >> n;


	vector<int> cows(n);
	vector<int> stalls(n);
	for (int &c : cows) { cin >> c; }

Java

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


public class JustStalling {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());


		int[] cows = new int[n];

Python

n = int(input())


cows = list(map(int, input().split()))
stalls = list(map(int, input().split()))


cows.sort()
stalls.sort()


possibilities = 1
j = n - 1

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum