NEWREST - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

This problem is to be solved using dynamic programming approach plus some combinatorics.

First, define dp[i][j] as the number of ways to cook exactly j different types of dish for i days. As the base case, it is obvious that dp[0][0] = 1, dp[0][x] = 0 for x > 0.

Suppose we know the value of dp[i][j] for some pair (i, j). Now, consider the (i+1)th day. There are two options for us:

  • Cook a dish which has been cooked before. There are j types of such dishes. We can update dp[i+1][j]:
    dp[i+1][j] += j * dp[i][j]
  • Cook a new type of dish. Note that we don’t care which type of dish it is; we only care that its type is different from all j types. We can update dp[i+1][j+1]:dp[i+1][j+1] += dp[i][j]

After that, we’ll take the actual types of dish into account. There are M available types of dish. There are P(M, j) ways to choose j types from M types (the order is important). So, the number of ways to cook exactly j different types of dish for i days is P(M, j) * dp[i][j] = (M! / (M-j)!) * dp[i][j] = M! * (M-j)!-1 * dp[i][j]. Of course, all calculations are performed modulo MOD = 1000000007.

We can precompute all values of k! for all 1 ≤ k ≤ M. The value of k!-1 (mod MOD) can be calculated using Euler’s Theorem: k!-1 = k!MOD-2 (mod MOD). Also, the DP values can be computed only once for all T test cases.

Since the original problem asks for the number of ways to cook at most K different types of dish in N days, the final answer is: sum {M! * (M-j)!-1 * dp[N][j]} for all 1 ≤ j ≤ min(M, K).

The complexity of this solution is O(N(M+K) + M log MOD + T(M+K)).

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

5 Likes

I don’t understand the Eulers Theorem part and why are we computing (k!)^(-1) in the first place and what does it even mean. I know that we need to keep track of (M-K)! but how do we do that and why is Eulers Theorem a part of that computation. I have an OA in a few hours and I cant get this out of my head.

A much better solution could be rather than precomputing factorial and inverse factorial which of course is time-consuming to construct the inverse the factorial as we go along. Answer for m = 7, d = 4, k = 3 is: dp[4][1] X 7P1 + dp[4][2] X 7P2 + dp[4][3] X 7P3. We already have computed dp. What we need now is 7P1, 7P2, 7P3 = 7, 7X6, 7X6X5. We are computing nPr using n! / (n-r)! in the editorial. But since we already are looping from 1 -> k. We can construct nPr as we go along.

class Solution:
    @staticmethod
    def worker():
        T = int(input())
        mod = 1000000007
        dp = [[0] * 1001 for _ in range(1001)]
        dp[0][0] = 1
        for day in range(1, 1001):
            for dish in range(1, day+1):
                dp[day][dish] = (dp[day - 1][dish - 1] + dp[day-1][dish] * dish) % mod
        while T:
            T -= 1
            n, m, k = list(map(int, input().split(' ')))
            k = m if k > m else (n if k > n else k)
            factorial = 1
            total = 0
            for dishes in range(1, k+1):
                factorial = (factorial * (m-dishes+1)) % mod
                total = (factorial * dp[n][dishes] + total) % mod
            print(total)
Solution.worker()
1 Like