To solve the first subtask where $N \leq 8$, we can try all $N!$ possible permutations to place a cow in a stall. Note that since $20!\approx 2.4\cdot 10^{18}$, the answer always fits into a $\texttt{long long}$. The runtime here will be $O(N\cdot 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.

- 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.
- 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).
- 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 $\mathcal{O}(N^2)$ 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(N\log N)$ by sorting both the cows and stalls by height and using two pointers.