onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

Dynamic Programming (3D) - Complex approach
Dynamic Programming (2D) - Complex approach

Approach 1: Dynamic Programming (3D)

The key insight for solving this problem is to use dynamic programming to count the number of valid sequences.

Let's define a 3D DP array dp[i][j][k] where:

i represents the current roll number (from 1 to n)
j represents the face value of the current roll (from 1 to 6)
k represents the number of consecutive occurrences of face value j (from 1 to rollMax[j-1])

The value dp[i][j][k] represents the number of valid sequences of length i that end with k consecutive occurrences of face value j.

The base cases are:

dp[1][j][1] = 1 for all j from 1 to 6 (there is one way to roll each face value on the first roll)

For the recurrence relation, we need to consider two cases:

If the current roll has the same face value as the previous roll (extending a consecutive sequence):
dp[i][j][k] = dp[i-1][j][k-1] for k > 1
If the current roll has a different face value from the previous roll (starting a new consecutive sequence):
dp[i][j][1] = sum(dp[i-1][j'][k']) for all j' != j and all valid k'

The final answer is the sum of dp[n][j][k] for all j from 1 to 6 and all valid k from 1 to rollMax[j-1].

Algorithm:

Initialize a 3D DP array dp of size (n+1) × 7 × 16, where dp[i][j][k] represents the number of valid sequences of length i that end with k consecutive occurrences of face value j.
Set the base cases: dp[1][j][1] = 1 for all j from 1 to 6.
For each roll i from 2 to n:
a. For each face value j from 1 to 6:
i. For each consecutive count k from 1 to rollMax[j-1]:
1. If k = 1 (starting a new consecutive sequence):
- dp[i][j][1] += sum(dp[i-1][j'][k']) for all j' != j and all valid k'
2. If k > 1 (extending a consecutive sequence):
- dp[i][j][k] = dp[i-1][j][k-1]
Calculate the final answer as the sum of dp[n][j][k] for all j from 1 to 6 and all valid k from 1 to rollMax[j-1].
Return the final answer modulo 10^9 + 7.

Time Complexity:

O(n * 6 * max(rollMax))

We need to compute the DP values for each roll, each face value, and each possible consecutive count. The maximum consecutive count is bounded by the maximum value in rollMax.

Space Complexity:

O(n * 6 * max(rollMax))

We use a 3D DP array of size (n+1) × 7 × 16 to store the number of valid sequences for each state.

Approach 2: Dynamic Programming (2D)

We can optimize the space complexity by using a 2D DP array instead of a 3D DP array.

Let's define a 2D DP array dp[i][j] where:

i represents the current roll number (from 1 to n)
j represents the face value of the current roll (from 1 to 6)

The value dp[i][j] represents the number of valid sequences of length i that end with face value j.

Additionally, we'll use another 2D array consecutive[i][j] to keep track of the number of valid sequences of length i that end with face value j for each possible consecutive count.

The recurrence relation is:

dp[i][j] = sum(dp[i-1][j']) for all j' != j + sum(consecutive[i-1][j][k]) for all valid k

Where consecutive[i-1][j][k] represents the number of valid sequences of length i-1 that end with k consecutive occurrences of face value j, and k is less than rollMax[j-1].

The final answer is the sum of dp[n][j] for all j from 1 to 6.

Algorithm:

Initialize a 2D DP array dp of size (n+1) × 7, where dp[i][j] represents the number of valid sequences of length i that end with face value j.
Initialize a 3D array consecutive of size (n+1) × 7 × 16, where consecutive[i][j][k] represents the number of valid sequences of length i that end with k consecutive occurrences of face value j.
Set the base cases: dp[1][j] = 1 and consecutive[1][j][1] = 1 for all j from 1 to 6.
For each roll i from 2 to n:
a. For each face value j from 1 to 6:
i. Calculate the number of sequences that can be extended with face value j:
- For all j' != j, add dp[i-1][j'] to dp[i][j]
- For j' = j, add sum(consecutive[i-1][j][k]) for all k < rollMax[j-1] to dp[i][j]
ii. Update the consecutive array:
- consecutive[i][j][1] = sum(dp[i-1][j']) for all j' != j
- consecutive[i][j][k] = consecutive[i-1][j][k-1] for all k from 2 to rollMax[j-1]
Calculate the final answer as the sum of dp[n][j] for all j from 1 to 6.
Return the final answer modulo 10^9 + 7.

Time Complexity:

O(n * 6 * max(rollMax))

The time complexity remains the same as the 3D DP approach, as we still need to compute the values for each state.

Space Complexity:

O(n * 6 * max(rollMax))

We use a 2D DP array of size (n+1) × 7 and a 3D array for consecutive counts, so the space complexity remains the same.

Pseudocode

solution.pseudo

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
function dieSimulator(n, rollMax):
    MOD = 10^9 + 7
 
    // Initialize DP array
    dp = new 3D array of size (n+1) × 7 × 16, initialized with 0
 
    // Base cases
    for j from 1 to 6:
        dp[1][j][1] = 1
 
    // Fill DP array
    for i from 2 to n:
        for j from 1 to 6:
            // Case 1: Starting a new consecutive sequence
            for j' from 1 to 6:
                if j' != j:
                    for k' from 1 to rollMax[j'-1]:
                        dp[i][j][1] = (dp[i][j][1] + dp[i-1][j'][k']) % MOD
 
            // Case 2: Extending a consecutive sequence
            for k from 2 to rollMax[j-1]:
                dp[i][j][k] = dp[i-1][j][k-1]
 
    // Calculate the final answer
    result = 0
    for j from 1 to 6:
        for k from 1 to rollMax[j-1]:
            result = (result + dp[n][j][k]) % MOD
 
    return result

Previous Next

String Problems

Palindrome Checker

Determine if a string reads the same forward and backward.

EasyString Manipulation

Message Encryption

Reverse a string to create a simple encryption system.

EasyString Manipulation

Word Puzzle Challenge

Check if two strings are anagrams of each other.

EasyString Manipulation

Learning Objective

Understand different approaches to solve the dice roll simulation problem and analyze their efficiency.