We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Dice Roll Simulation

Number: 1343

Difficulty: Hard

Paid? No

Companies: Akuna Capital

Problem Description

Given n dice rolls and an array rollMax of length 6 (1-indexed constraints) where rollMax[i] indicates the maximum number of consecutive times that face i+1 can be rolled, determine the number of distinct valid sequences of dice rolls of length n. Two sequences are different if they differ in at least one roll. The final answer should be computed modulo 10^9 + 7.

Key Insights

  • Use dynamic programming (DP) to track the state of sequences.
  • Define a DP state that tracks the number of rolls, the last rolled face, and the current count of consecutive occurrences of that face.
  • When transitioning, if the same face is rolled again, check the constraint limit from rollMax; if a different face is rolled, reset the consecutive count to 1.
  • The constraints are tight for n (up to 5000) but the maximum consecutive counts for each face are small (up to 15), so keeping track of consecutive counts is feasible.

Space and Time Complexity

Time Complexity: O(n * 6 * (max(rollMax))) since for each roll we update DP states for 6 faces and each face may have up to rollMax[i] states. Space Complexity: O(n * 6 * (max(rollMax))) for maintaining the DP table. With rollMax values being constant (at most 15), this is effectively linear with respect to n.

Solution

We adopt a dynamic programming approach by defining our state as dp[i][j][k] where:

  • i: the number of rolls performed so far,
  • j: the last rolled face (0-indexed corresponding to dice faces 1 to 6),
  • k: the number of consecutive times face j has been rolled (with k ranging from 1 up to rollMax[j]).

Initialization:

  • For the first roll (i = 1), we can choose any face (from 1 to 6) and the count will be 1.

Transition:

  • For each new roll i+1 from state dp[i][j][k]:
    • If we roll the same face j and if k is less than rollMax[j] then we can extend the streak to k + 1.
    • If we roll a different face m then we start a new streak with count 1 for face m.

Sum up all valid sequences after n rolls and return the answer modulo 10^9 + 7.

Code Solutions

MOD = 10**9 + 7

def dieSimulator(n, rollMax):
    # dp[i][j][k]: number of sequences with i rolls, ending with face j (0-indexed), streak of k
    dp = [[[0] * (rollMax[j] + 1) for j in range(6)] for _ in range(n + 1)]
    
    # Initialize for the first roll: every face can appear once
    for j in range(6):
        dp[1][j][1] = 1
    
    for i in range(1, n):
        for j in range(6):  # current face
            for k in range(1, rollMax[j] + 1):
                if dp[i][j][k]:
                    # roll the same face j if possible
                    if k < rollMax[j]:
                        dp[i+1][j][k+1] = (dp[i+1][j][k+1] + dp[i][j][k]) % MOD
                    # roll a different face m, reset count to 1
                    for m in range(6):
                        if m != j:
                            dp[i+1][m][1] = (dp[i+1][m][1] + dp[i][j][k]) % MOD
    
    total = 0
    for j in range(6):
        for k in range(1, rollMax[j] + 1):
            total = (total + dp[n][j][k]) % MOD
    return total

# Example usage:
print(dieSimulator(2, [1, 1, 2, 2, 2, 3]))  # Expected output: 34
← Back to All Questions