Dice Roll Simulation

HARD

Description

A die simulator generates a random number from 1 to 6 for each roll. You introduced a constraint to the generator such that it cannot roll the number i more than rollMax[i] (1-indexed) consecutive times.

Given an array of integers rollMax and an integer n, return the number of distinct sequences that can be obtained with exact n rolls. Since the answer may be too large, return it modulo 10⁹ + 7.

Two sequences are considered different if at least one element differs from each other.

Example 1:

Input: n = 2, rollMax = [1,1,2,2,2,3]
Output: 34
Explanation: There will be 2 rolls of die, if there are no constraints on the die, there are 6 * 6 = 36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 = 34.

Example 2:

Input: n = 2, rollMax = [1,1,1,1,1,1]
Output: 30

Example 3:

Input: n = 3, rollMax = [1,1,1,2,2,3]
Output: 181

Constraints:

1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15

Approaches

Checkout 4 different approaches to solve Dice Roll Simulation. Click on different approaches to view the approach and algorithm in detail.

2D Dynamic Programming with Subtraction

This is a more efficient approach that redefines the DP state to reduce the dimensions of the table and improve the time complexity. Instead of tracking the consecutive count explicitly in the state, we calculate the number of valid sequences by taking the total possible sequences and subtracting the invalid ones. This 'subtraction' principle leads to a faster solution.

Algorithm

Define dp[i][j] as the number of valid sequences of length i ending with face j.
Define S[i] as the total number of valid sequences of length i, which is sum(dp[i][p]) over all faces p.
Base case: S[0] = 1 (for the empty sequence).
Iterate i from 1 to n:
- For each face j from 0 to 5:
  - Start with dp[i][j] = S[i-1], which is the count if there were no constraints.
  - Let k = rollMax[j]. We must subtract the invalid sequences that end with more than k consecutive j's.
  - If i > k, the number of invalid sequences is the number of valid sequences of length i-k-1 that did not end in j. This is S[i-k-1] - dp[i-k-1][j]. Subtract this from dp[i][j].
  - If i == k, there is exactly one invalid sequence (all j's). Subtract 1.
- Calculate S[i] by summing dp[i][j] over all j.
Return S[n].

Let dp[i][j] be the number of valid sequences of length i ending with face j. Let S[i] be the total number of valid sequences of length i.

To calculate dp[i][j], we can start with the total number of ways to form a sequence of length i-1 (S[i-1]) and append j. This gives us S[i-1] potential sequences.

However, this includes invalid sequences where j is rolled more than rollMax[j] consecutive times. We must subtract these. An invalid sequence of length i ending with rollMax[j] + 1 consecutive j's must have the form ... p j j ... j, where p != j. The prefix ... p has length i - (rollMax[j] + 1). The number of such prefixes is the number of valid sequences of that length that do not end in j, which is S[i - rollMax[j] - 1] - dp[i - rollMax[j] - 1][j]. This gives us our recurrence.

class Solution {
    public int dieSimulator(int n, int[] rollMax) {
        long MOD = 1_000_000_007;
        long[][] dp = new long[n + 1][6];
        long[] sum = new long[n + 1];
        sum[0] = 1;

        for (int i = 1; i <= n; i++) {
            long currentSum = 0;
            for (int j = 0; j < 6; j++) {
                // Initially, assume we can append j to any valid sequence of length i-1
                dp[i][j] = sum[i - 1];
                
                int k = rollMax[j];
                if (i > k) {
                    // Subtract sequences of length i-k-1 not ending with j
                    long toSubtract = (sum[i - k - 1] - dp[i - k - 1][j] + MOD) % MOD;
                    dp[i][j] = (dp[i][j] - toSubtract + MOD) % MOD;
                } else if (i == k) {
                    // Subtract the sequence of all j's
                    dp[i][j] = (dp[i][j] - 1 + MOD) % MOD;
                }
                currentSum = (currentSum + dp[i][j]) % MOD;
            }
            sum[i] = currentSum;
        }

        return (int) sum[n];
    }
}

Complexity Analysis

Time Complexity: O(n * faces). This is a significant improvement as we removed the dependency on `max_rollMax` from the loops.Space Complexity: O(n * faces). We use a 2D DP table of size `(n+1) x 6` and a sum array of size `n+1`.

Pros and Cons

Pros:

Much faster time complexity than the 3D DP approaches.
The DP state is simpler (2D vs 3D).

Cons:

Still uses linear space with respect to n.
The recurrence relation is slightly more complex to derive.

Code Solutions

Checking out 3 solutions in different languages for Dice Roll Simulation. Click on different languages to view the code.

class Solution {
private
  Integer[][][] f;
private
  int[] rollMax;
public
  int dieSimulator(int n, int[] rollMax) {
    f = new Integer[n][7][16];
    this.rollMax = rollMax;
    return dfs(0, 0, 0);
  }
private
  int dfs(int i, int j, int x) {
    if (i >= f.length) {
      return 1;
    }
    if (f[i][j][x] != null) {
      return f[i][j][x];
    }
    long ans = 0;
    for (int k = 1; k <= 6; ++k) {
      if (k != j) {
        ans += dfs(i + 1, k, 1);
      } else if (x < rollMax[j - 1]) {
        ans += dfs(i + 1, j, x + 1);
      }
    }
    ans %= 1000000007;
    return f[i][j][x] = (int)ans;
  }
}

Video Solution

Watch the video walkthrough for Dice Roll Simulation

Patterns:

Dynamic Programming

Data Structures:

Array

Companies:

Akuna Capital |