Skip to content

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

SourceWeekly Contest 185 Q4DifficultyHardRating2175

Description

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 satisfy 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

Solutions

Solution 1

Thinking

The search cost is how many times the prefix maximum is updated. \(n\le 50\), \(m\le 100\), so we DP on length, cost, and current maximum.

If position \(i\) does not raise the maximum, it has \(j\) choices and stays at the same cost. If it writes a new maximum \(j\), we sum states whose previous maximum is smaller and whose cost is one less.

\(k=0\) is impossible. Sum \(dp[n][k][\cdot]\) for the answer.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        if k == 0:
            return 0
        dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]
        mod = 10**9 + 7
        for i in range(1, m + 1):
            dp[1][1][i] = 1
        for i in range(2, n + 1):
            for c in range(1, min(k + 1, i + 1)):
                for j in range(1, m + 1):
                    dp[i][c][j] = dp[i - 1][c][j] * j
                    for j0 in range(1, j):
                        dp[i][c][j] += dp[i - 1][c - 1][j0]
                        dp[i][c][j] %= mod
        ans = 0
        for i in range(1, m + 1):
            ans += dp[n][k][i]
            ans %= mod
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int numOfArrays(int n, int m, int k) {
        if (k == 0) {
            return 0;
        }
        long[][][] dp = new long[n + 1][k + 1][m + 1];
        for (int i = 1; i <= m; ++i) {
            dp[1][1][i] = 1;
        }
        for (int i = 2; i <= n; ++i) {
            for (int c = 1; c <= Math.min(i, k); ++c) {
                for (int j = 1; j <= m; ++j) {
                    dp[i][c][j] = (dp[i - 1][c][j] * j) % MOD;
                    for (int j0 = 1; j0 < j; ++j0) {
                        dp[i][c][j] = (dp[i][c][j] + dp[i - 1][c - 1][j0]) % MOD;
                    }
                }
            }
        }
        long ans = 0;
        for (int i = 1; i <= m; ++i) {
            ans = (ans + dp[n][k][i]) % MOD;
        }
        return (int) ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int numOfArrays(int n, int m, int k) {
        if (k == 0) return 0;
        int mod = 1e9 + 7;
        using ll = long long;
        vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(k + 1, vector<ll>(m + 1)));
        for (int i = 1; i <= m; ++i) dp[1][1][i] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int c = 1; c <= min(i, k); ++c) {
                for (int j = 1; j <= m; ++j) {
                    dp[i][c][j] = (dp[i - 1][c][j] * j) % mod;
                    for (int j0 = 1; j0 < j; ++j0) {
                        dp[i][c][j] = (dp[i][c][j] + dp[i - 1][c - 1][j0]) % mod;
                    }
                }
            }
        }
        ll ans = 0;
        for (int i = 1; i <= m; ++i) ans = (ans + dp[n][k][i]) % mod;
        return (int) ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func numOfArrays(n int, m int, k int) int {
    if k == 0 {
        return 0
    }
    mod := int(1e9) + 7
    dp := make([][][]int, n+1)
    for i := range dp {
        dp[i] = make([][]int, k+1)
        for j := range dp[i] {
            dp[i][j] = make([]int, m+1)
        }
    }
    for i := 1; i <= m; i++ {
        dp[1][1][i] = 1
    }
    for i := 2; i <= n; i++ {
        for c := 1; c <= k && c <= i; c++ {
            for j := 1; j <= m; j++ {
                dp[i][c][j] = (dp[i-1][c][j] * j) % mod
                for j0 := 1; j0 < j; j0++ {
                    dp[i][c][j] = (dp[i][c][j] + dp[i-1][c-1][j0]) % mod
                }
            }
        }
    }
    ans := 0
    for i := 1; i <= m; i++ {
        ans = (ans + dp[n][k][i]) % mod
    }
    return ans
}

Solution 2: Prefix Sum Optimization

Thinking

The first DP computes each state by scanning every smaller previous maximum, which adds an \(O(m)\) loop. For a fixed length and search cost, adjacent maxima need almost the same sum: the sum for maximum \(j\) adds only the state at \(j-1\) to the sum for \(j-1\). We can maintain that prefix while increasing \(j\), so each state takes \(O(1)\) time. Only the previous length is needed, so two DP layers suffice.

Let \(dp[c][j]\) count arrays of the current length with search cost \(c\) and maximum \(j\). When we append a value, it either does not raise the maximum (with \(j\) choices) or raises a smaller maximum to \(j\). For each new length, maintain \(\textit{prefix} = \sum_{x=1}^{j-1} dp_{\textit{prev}}[c-1][x]\) while increasing \(j\). Then

\[dp_{\textit{next}}[c][j] = j \cdot dp_{\textit{prev}}[c][j] + \textit{prefix} \pmod{10^9+7}.\]

Initialize \(dp[1][j]=1\) for arrays of length \(1\). The answer is the sum of \(dp[k][j]\) for \(1 \le j \le m\). The time complexity is \(O(nkm)\), reduced from \(O(nkm^2)\) in Solution 1. Keeping only the previous and next lengths uses \(O(km)\) space instead of \(O(nkm)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        if k == 0:
            return 0
        mod = 10**9 + 7
        dp = [[0] * (m + 1) for _ in range(k + 1)]
        for j in range(1, m + 1):
            dp[1][j] = 1
        for i in range(2, n + 1):
            nxt = [[0] * (m + 1) for _ in range(k + 1)]
            for c in range(1, min(i, k) + 1):
                prefix = 0
                for j in range(1, m + 1):
                    prefix = (prefix + dp[c - 1][j - 1]) % mod
                    nxt[c][j] = (dp[c][j] * j + prefix) % mod
            dp = nxt
        return sum(dp[k]) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int numOfArrays(int n, int m, int k) {
        if (k == 0) return 0;
        constexpr int mod = 1e9 + 7;
        vector<vector<long long>> dp(k + 1, vector<long long>(m + 1));
        for (int j = 1; j <= m; ++j) dp[1][j] = 1;
        for (int i = 2; i <= n; ++i) {
            vector<vector<long long>> nxt(k + 1, vector<long long>(m + 1));
            for (int c = 1; c <= min(i, k); ++c) {
                long long prefix = 0;
                for (int j = 1; j <= m; ++j) {
                    prefix = (prefix + dp[c - 1][j - 1]) % mod;
                    nxt[c][j] = (dp[c][j] * j + prefix) % mod;
                }
            }
            dp.swap(nxt);
        }
        long long ans = 0;
        for (int j = 1; j <= m; ++j) ans = (ans + dp[k][j]) % mod;
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function numOfArrays(n: number, m: number, k: number): number {
    if (k === 0) {
        return 0;
    }
    const mod = 1e9 + 7;
    let dp: number[][] = Array.from({ length: k + 1 }, () => Array(m + 1).fill(0));
    for (let j = 1; j <= m; ++j) {
        dp[1][j] = 1;
    }
    for (let i = 2; i <= n; ++i) {
        const next: number[][] = Array.from({ length: k + 1 }, () => Array(m + 1).fill(0));
        for (let c = 1; c <= Math.min(i, k); ++c) {
            let prefix = 0;
            for (let j = 1; j <= m; ++j) {
                prefix = (prefix + dp[c - 1][j - 1]) % mod;
                next[c][j] = (dp[c][j] * j + prefix) % mod;
            }
        }
        dp = next;
    }
    return dp[k].reduce((sum, count) => (sum + count) % mod, 0);
}

Comments