Permutation/Combination question from programming contest

Question

So I was recently in a programming contest and got stumped on this permutation/combination question. I am hoping someone can help me out with a solution if this ever crosses my path again.

A group of contest writers have written n problems and want to use k of them in an upcoming contest. Each problem has a difficulty level. A contest is valid if all of its k problems gave different difficulty levels.

Compute how many distinct valid contest the contest writers can produce.

Examples given were

n = 5, k = 2, {1, 2, 3, 4, 5}

Answer = 10

n = 5, k = 2, {1, 1, 1, 2, 2}

Answer = 6

n = 12, k = 5 {1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 7, 8}

Answer = 316

Answer 1

Take a look at the last, most complicated example.

You have 8 groups of difficulties (from 1 to 8) and in each group you have a number of choices (2 for difficulty level 1, 1 for difficulty level 2, 2 for difficulty level 3...).

Clearly, you have to pick 5 problems with 5 different difficulty levels from the set of 8 different difficulty levels. In your program you can easily "walk" through all possible combinations of difficulties:

$$ \\ 1 2 3 4 5\\ 1 2 3 4 6 \\ 1 2 3 4 7 \\ 1 2 3 4 8 \\ 1 3 4 5 6 \\ ...\\ 4 5 6 7 8 \\ $$

While walking through the list of combinations associate "weight" to each of them. Take a look at the first one, for example (12345): you have 2 choices for difficulty level 1, 2 choices for difficulty level 3 and 3 choices for difficulty level 5. The weight of combination 12345 is actually $2\times2\times3=12$, because you have 12 different ways to select 5 problems with difficulties 12345.

$$ \\ 1 2 3 4 5\implies weight=12\\ 1 2 3 4 6 \implies weight=4\\ 1 2 3 4 7 \implies weight=4\\ 1 2 3 4 8 \implies weight=4\\ 1 3 4 5 6 \implies weight=12\\ ...\\ 4 5 6 7 8 \implies weight=3\\ $$

Summarize all weights of all combinations of difficulties (12+4+4+4+12+...+3) and you are done.

EDIT: Another solution.

Solution described above can be very inefficient. If you have a huge number of difficulty levels, going through all combinations and assigning weights to them can be very slow. Let's do it by using recurence.

Denote the number of problems available for a difficulty level $i$ with $a_i$. In your last example:

$$A=\{a_i|i=1,...,8\}=\{2, 1, 2, 1, 3, 1, 1, 1\}$$

Denote the length of the list with $n$ (8 in the last, most complicated example).

Denote the number of possible selections of $k$ problems with the smallest difficulty level equal to $i$ with $f(A, n, k, i)$. Basically you want to calculate $f(A, 8, 5, 1)$.

You have the following recurrence formula:

$$f(A, n, k, i)=a_i\times f(A, n, k - 1, i + 1) + f(A, n, k, i + 1)\tag{1}$$

This basically means that if you need $k$ problems you can:

• either start by picking one of the problems with difficulty level $i$ ($a_i$ different ways to do that) and combine them with $k-1$ problems starting with difficulty level $i+1$
• or skip the difficulty level $i$ entirely and pick all $k$ problems starting with difficulty level $i+1$.

Whenever you use recurrence in programming, you need the exit condition (recursion has to stop somewhere). In this particular case:

$$f(A, n, k, i)=0 \space \text{for}\space k\gt(n-i+1)\tag{2}$$

...which basically means that you cannot select $k$ problems with different difficulty levels if your (smallest) starting difficulty $i$ is to big.

$$f(A, n, k, i)=1 \space \text{for}\space k=0\tag{3}$$

...which means that there is only one way to select "nothing".

(1), (2) and (3) can be easily translated into a fairly efficient computer program:

public class Competition {
    public static int f(int[] a, int k, int i) {
        int n = a.length;
        if(k > n - i) {
            return 0;
        }
        if(k == 0) {
            return 1;
        }
        return a[i] * f(a, k - 1, i + 1) + f(a, k, i + 1);
    }

    public static void main(String[] args) throws Exception {
        int[] a = {2, 1, 2, 1, 3, 1, 1, 1};
        System.out.println(f(a, 5, 0));
    }
}

I had to make some small adjustments in the code becuase indexes are zero-based in Java. The program prints 316 as expected.

A short one, isn't it? :)

Answer 2

Explained well by Oldboy, what I would like to add is this is a slight modification of "Calculating nCr using Pascal's Triangle", just you have to multiply the weight of difficulty with $C_{r-1}^{n-1}$ term and add it with C_r^{n-1} term.

$C_r^n$ = (Weight[n])*(n-1)C(r-1) + (n-1)C(r).

ll pascal(vector <pair<ll,ll>> &a, ll n, ll k){
ll psc[n+1][n+1];
psc[0][0] = 1;

for(ll line=1; line<=n; line++){
    for(ll i=0; i<=line; i++){
        if(i==line){
            psc[line][i] = a[line-1].second*psc[line-1][line-1];
        }else if(i == 0){
            psc[line][i] = 1;
        }
        else{
            psc[line][i] = (psc[line-1][i-1])*a[line-1].second + psc[line-1][i];
        }
        psc[line][i-1] %= p;
        // cout << psc[line][i] << " ";
    }
    // cout << '\n';
}

return psc[n][k]%p;
}

ll is long long int.