Just Stalling USACO 2021 January Contest

Just Stalling USACO Solution

Farmer John has NN cows (1≤N≤201≤N≤20) of heights a1…aNa1…aN. His barn has NN stalls with max height limits b1…bNb1…bN (so for example, if b5=17b5=17, then a cow of height at most 1717 can reside in stall 55). In how many distinct ways can Farmer John arrange his cows so that each cow is in a different stall, and so that the height limit is satisfied for every stall?

See Also: USACO 2021 January Contest

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains NN. The second line contains NN space-separated integers a1,a2,…,aNa1,a2,…,aN. The third line contains NN space-separated integers b1,b2,…,bNb1,b2,…,bN. All heights and limits are in the range [1,109][1,109].

OUTPUT FORMAT (print output to the terminal / stdout):

The number of ways Farmer John can place each cow into a different stall such that the height limit is satisfied for every stall. Note that the large size of the output might require the use of a 64-bit integer, like a “long long” in C++.

SAMPLE INPUT:

4
1 2 3 4
2 4 3 4

SAMPLE OUTPUT:

8

In this example, we cannot place the third cow into the first stall since 3=a3>b1=23=a3>b1=2. Similarly, we cannot place the fourth cow into the first or third stalls. One way to satisfy the height limits is to assign cow 11 to stall 11, cow 22 to stall 22, cow 33 to stall 33, and cow 44 to stall 44.

SCORING:

  • Test cases 1-5 satisfy N≤8N≤8.
  • Test cases 6-12 satisfy no additional constraints.

Problem credits: Shreyas Thumathy

Solution

To solve the first subtask where N≤8N≤8, we can try all N!N! possible permutations to place a cow in a stall. Note that since 20!≈2.4⋅101820!≈2.4⋅1018, the answer always fits into a long longlong long. The runtime here will be O(N⋅N!)O(N⋅N!). Alternatively, write a recursive function that tries placing the first cow in each of the stalls, the second cow in each of the stalls (aside from the one the first cow was placed in), and so on.

For a faster solution, let’s consider the cows in descending order of height.

  1. The number of stalls we can place the cow with the greatest height in is the number of stalls with height greater than or equal to the height of that cow.
  2. The number of stalls the 2nd tallest cow can be placed in is the number of stalls at least as tall as this cow minus one (because the tallest cow is in one of these stalls). The key observation is that this quantity does not depend on which of the stalls we placed the tallest cow in (which would not be the case if the cows were not sorted in decreasing order).
  3. Similarly, the number of stalls the 3rd tallest cow can be placed in is the number of stalls at least as tall as this cow minus two (because the tallest cow and the second tallest cow take up two of these stalls).

And so on. If we multiply all these together, we get the final answer. Both of the solutions below compute the answer in O(N2)O(N2) time.

Riya’s code:

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

int N, A[20], B[20];
long answer = 1;

int count_bigger(int x) {
  // Count the number of values of B_i which are greater than or equal to x
  int cnt = 0;
  for (int i=0; i<N; i++) {
    if (B[i] >= x) {
      cnt ++;
    }
  }
  return cnt;
}

int main() {
    cin >> N;
    for (int i=0; i<N; i++) {
      cin >> A[i];
    }
    for (int i=0; i<N; i++) {
      cin >> B[i];
    }
    sort(A, A+N);

    for (int i=N-1; i>=0; i--) {
      answer *= count_bigger(A[i]) - (N-1 - i);
    }

    cout << answer << endl;
}

Danny Mittal’s code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class PermootationCountingBronze {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        Integer[] cows = new Integer[n];
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        for (int j = 0; j < n; j++) {
            cows[j] = Integer.parseInt(tokenizer.nextToken());
        }
        Integer[] stalls = new Integer[n];
        tokenizer = new StringTokenizer(in.readLine());
        for (int j = 0; j < n; j++) {
            stalls[j] = Integer.parseInt(tokenizer.nextToken());
        }
        Arrays.sort(stalls);
        long answer = 1;
        for (int j = 0; j < n; j++) {
            long howManyFit = 0;
            for (int cow : cows) {
                if (cow <= stalls[j]) {
                    howManyFit++;
                }
            }
            howManyFit -= j;
            answer *= howManyFit;
        }
        System.out.println(answer);
    }
}

Bonus: Speed this up to O(NlogN)O(Nlog⁡N) by sorting both the cows and stalls by height and using two pointers.

USACO 2021 January Contest Solution

Leave a Comment