USACO 2021 January Contest, Bronze Problem 3. Just Stalling

USACO 2021 January Contest, Bronze Problem 3. Just Stalling

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?

 

 

 

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.

 

 

Problem credits: Shreyas Thumathy

USACO 2021 January Contest, Bronze Problem 3. Just Stalling 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Riya Arora, Benjamin Qi)

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.
[/hide]