Shortest Impossible Sequence of Rolls

1. We are looking for the smallest length L such that the number of distinct subsequences of rolls of length L is less than k^L.
2. We can iterate L from 1 upwards.
3. For each L, we calculate the total number of distinct subsequences of length L that can be formed from the rolls array.
4. Let dp[i][j] be the number of distinct subsequences of length j in the prefix rolls[0...i-1].
5. The recurrence relation is: dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] - dp[p][j-1]), where p is the index of the previous occurrence of the element rolls[i-1]. This formula counts subsequences not using rolls[i-1] (dp[i-1][j]) and those formed by appending rolls[i-1] to shorter subsequences, avoiding double counting.
6. We can optimize space by noticing that computing the column for length L only requires the column for length L-1. So we can use two arrays, one for the previous length and one for the current length.
7. For each L, we compute dp[n][L]. If dp[n][L] < k^L, we have found our answer, and we return L.
8. We must handle potential overflow when calculating k^L.

Let dp[i][j] be the number of distinct subsequences of length j that can be formed using the prefix of the rolls array of length i (i.e., rolls[0...i-1]). Our goal is to find the smallest j such that dp[n][j] < k^j.

The recurrence relation for dp[i][j] is derived by considering the element rolls[i-1]:

• Subsequences of length j in rolls[0...i-1] that do not include rolls[i-1] are the same as subsequences of length j in rolls[0...i-2]. Their count is dp[i-1][j].
• Subsequences of length j in rolls[0...i-1] that do include rolls[i-1] as their last element are formed by taking any distinct subsequence of length j-1 from rolls[0...i-2] and appending rolls[i-1]. The number of such new subsequences is dp[i-1][j-1]. However, this might lead to double counting if rolls[i-1] has appeared before. If the previous occurrence of rolls[i-1] was at index p-1, then any subsequence of length j-1 from rolls[0...p-2] extended with rolls[i-1] has already been counted. We must subtract these, which amounts to dp[p-1][j-1].

So, the full recurrence is: dp[i][j] = dp[i-1][j] + dp[i-1][j-1] - dp[p-1][j-1], where p is the 1-based index of the previous occurrence of rolls[i-1].

We can optimize the space from O(n*ans) to O(n) by using only two arrays to store the DP results for the current and previous lengths.

1import java.util.Arrays;2 3class Solution {4    public int shortestImpossibleSequenceOfRolls(int[] rolls, int k) {5        int n = rolls.length;6        // dp for length len-1. Initially for len=0, there's 1 empty subsequence.7        long[] prevDp = new long[n + 1];8        Arrays.fill(prevDp, 1);9 10        for (int len = 1; len <= n + 1; len++) {11            long kPowLen = 1;12            // Calculate k^len with overflow check13            for (int i = 0; i < len; i++) {14                if (kPowLen > Long.MAX_VALUE / k) {15                    kPowLen = Long.MAX_VALUE; // Represents a very large number16                    break;17                }18                kPowLen *= k;19            }20 21            long[] currDp = new long[n + 1]; // dp for length len22            int[] last = new int[k + 1]; // Stores last seen 1-based index of a roll value23 24            for (int i = 1; i <= n; i++) {25                // Number of subsequences of length 'len' in rolls[0...i-2]26                currDp[i] = currDp[i - 1];27                28                // New subsequences formed by appending rolls[i-1]29                long toAdd = prevDp[i - 1];30                int rollValue = rolls[i - 1];31                if (last[rollValue] > 0) {32                    // Subtract subsequences that would be duplicates33                    toAdd -= prevDp[last[rollValue] - 1];34                }35                currDp[i] += toAdd;36            }37 38            if (currDp[n] < kPowLen) {39                return len;40            }41            prevDp = currDp;42        }43        44        return n + 1; // Should not be reached given problem constraints45    }46}

1. Initialize a variable ans to 1, representing the length of sequences we can currently form. Initially, we can only form sequences of length 0 (the empty sequence), so the first impossible length is 1.
2. Initialize an empty set, seen, to keep track of the unique roll values encountered in the current segment of rolls.
3. Iterate through the rolls array one by one.
4. For each roll, add it to the seen set.
5. After adding a roll, check if the size of the seen set has become equal to k.
6. If seen.size() == k, it means we have found a segment in rolls that contains all possible outcomes from 1 to k. This allows us to extend all previously formable sequences by one more arbitrary roll. Therefore, we increment ans.
7. After incrementing ans, we clear the seen set to start looking for the next complete segment.
8. After iterating through all the rolls, the final value of ans is the length of the shortest impossible sequence.

Let's analyze why this greedy strategy works. We are looking for the smallest L such that some sequence of rolls of length L is not a subsequence of rolls. This is equivalent to finding the largest L-1 for which all sequences of length L-1 are subsequences of rolls.

Let's say we have found count disjoint segments in rolls, where each segment contains all numbers from 1 to k. Let these segments be S_1, S_2, ..., S_{count}.

Claim 1: All sequences of length count are possible. Consider any sequence [r_1, r_2, ..., r_{count}]. We can find r_1 in the first segment S_1. After finding r_1, we look for r_2 in the rest of the rolls array, which includes S_2, ..., S_{count}. We can surely find r_2 in S_2. We continue this process, finding r_i in segment S_i. Since the segments are disjoint and appear in order, we can always find the sequence [r_1, ..., r_{count}] as a subsequence of rolls. This means the shortest impossible sequence must have a length of at least count + 1.

Claim 2: There exists an impossible sequence of length count + 1. After finding count such segments, the remainder of the rolls array does not contain a full set of 1..k. This means there is at least one number, say y, that is missing from this remainder. If we construct a sequence of length count+1 that requires y to be found in this remainder, that sequence will be impossible. The greedy strategy of finding the shortest possible segments ensures that we can construct such an impossible sequence. Therefore, the shortest impossible length is exactly count + 1.

The algorithm is to count these segments. We start with ans = 1 (for the base case of length 1 sequences being impossible if not all k values are present at all). Each time we find a full set of 1..k, we increment ans.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int shortestImpossibleSequenceOfRolls(int[] rolls, int k) {6        int ans = 1;7        Set<Integer> seen = new HashSet<>();8        9        for (int roll : rolls) {10            seen.add(roll);11            if (seen.size() == k) {12                // Found a segment with all k numbers.13                // This means we can form one more layer of sequences.14                ans++;15                // Reset to find the next segment.16                seen.clear();17            }18        }19        20        return ans;21    }22}