1420

1420. Build Array Where You Can Find The Maximum Exactly K Comparisons (Hard)

You are given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:

You should build the array arr which has the following properties:

• arr has exactly n integers.
• 1 <= arr[i] <= m where (0 <= i < n).
• After applying the mentioned algorithm to arr, the value search_cost is equal to k.

Return the number of ways to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 109 + 7.

 

Example 1:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

Example 2:

Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisify the mentioned conditions.

Example 3:

Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]

 

Constraints:

• 1 <= n <= 50
• 1 <= m <= 100
• 0 <= k <= n

Companies: Dunzo

Related Topics:
Dynamic Programming, Prefix Sum

Hints:

• Use dynamic programming approach. Build dp table where dp[a][b][c] is the number of ways you can start building the array starting from index a where the search_cost = c and the maximum used integer was b.
• Recursively, solve the small sub-problems first. Optimize your answer by stopping the search if you exceeded k changes.

Solution 1. DP

// OJ: https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/
// Author: github.com/lzl124631x
// Time: O(M^2 * NK)
// Space: O(MNK)
// Ref: https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/discuss/586576/C%2B%2B-Bottom-Up-Dynamic-Programming-with-Explanation
class Solution {
    typedef long long LL;
    LL dp[51][101][51] = {};
public:
    int numOfArrays(int n, int m, int k) {
        int mod = 1e9+7;
        for (int i = 0; i <= m; ++i) dp[1][i][1] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                for (int t = 1; t <= k; ++t) {
                    LL s = 0;
                    s = (s + j * dp[i - 1][j][t]) % mod;
                    for (int x = 1; x < j; ++x) s = (s + dp[i - 1][x][t - 1]) %mod;
                    dp[i][j][t] = (dp[i][j][t] + s) % mod;
                }
            }
        }
        LL ans = 0;
        for (int i = 1; i <= m; ++i) ans = (ans + dp[n][i][k]) % mod;
        return ans;
    }
};

Solution 2. Top-down DP

Let dp[n][m][k] be the number of ways to build arrays with n elements left to fill, m being the previously filled maximum element, and k being the search_cost left to achieve. The answer is dp[N][0][K].

dp[0][m][k] = 1 if k == 0
            = 0 otherwise

For dp[n][m][k], we have two options

• If the elements left after filling the current element n - 1 is greater than or equal to the remaining search cost k, we can fill [1,m] to the current element. So we add dp[n-1][m][k] * m to dp[n][m][k].
• If k >= 1, we can fill [m+1, M] to the current element, So, we add SUM( dp[n-1, i, k-1] | m+1 <= i <= M ) to dp[n][m][k].

// OJ: https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons
// Author: github.com/lzl124631x
// Time: O(M^2 * NK)
// Space: O(MNK)
class Solution {
public:
    int numOfArrays(int N, int M, int K) {
        if (K == 0) return 0;
        int memo[51][101][51] = {}, ans = 0, mod = 1e9 + 7;
        memset(memo, -1, sizeof(memo));
        function<int(int, int, int)> dp = [&](int n, int m, int k) -> int {
            if (n == 0) return k == 0;
            if (memo[n][m][k] != -1) return memo[n][m][k];
            int ans = 0;
            if (n - 1 >= k) ans = (ans + (long)dp(n - 1, m, k) * m % mod) % mod;
            if (k >= 1) {
                for (int i = m + 1; i <= M; ++i) {
                    ans = (ans + dp(n - 1, i, k - 1)) % mod;
                }
            }
            return memo[n][m][k] = ans;
        };
        return dp(N, 0, K);
    }
};