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

Count The Number of Winning Sequences

Number: 3588

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Alice and Bob play an n‐round game where in each round Alice summons a creature given by the input string (each character being F, W, or E) and Bob selects one of the three creatures. The creatures interact according to “rock–paper–scissors” rules: Fire (F) beats Earth (E), Water (W) beats Fire (F), and Earth (E) beats Water (W); if both summon the same creature, it is a draw. Bob’s sequence must not use the same creature in consecutive rounds. Bob wins overall if his total win count (rounds where his creature beats Alice’s) is strictly greater than Alice’s win count (rounds where her creature beats Bob’s). Return the number of distinct sequences Bob can choose that beat Alice, modulo 10^9 + 7.

Key Insights

  • Model the problem round‐by‐round using dynamic programming (DP) where the state captures the current round, Bob’s last move (for enforcing no consecutive repetition), and the ongoing score difference.
  • Map the winning conditions: For a given round and Alice’s move:
    • Bob’s move yields +1 (win) if it beats Alice’s move (ex: if Alice is E then choosing F wins).
    • It yields 0 for a draw (same creature).
    • Otherwise, it gives –1 (loss).
  • The DP state is defined as dp[i][m][d] where i = current round, m = Bob’s last creature (encoded), and d = current score difference (Bob’s wins minus Alice’s wins). The goal is to count sequences such that after n rounds d > 0.
  • Use an offset for the difference index because the difference can be negative.
  • Transitions only allow moves different from Bob’s previous move.
  • The final answer is the sum over all states in round n that have a positive score difference.

Space and Time Complexity

Time Complexity: O(n * 3 * (2n+1) * 2) ~ O(n^2) since for each round (n), for each of 3 last moves and each possible difference state (roughly 2n), we try up to 2 candidates. Space Complexity: O(3 * (2*n+1)) for storing the DP states for each round, which is O(n).

Solution

We solve the problem using dynamic programming. First, we map the creatures F, W, and E to indices (0, 1, 2) to facilitate iteration and checking the "no consecutive move" constraint. For each round i, given Alice’s move, we calculate the outcome if Bob picks a certain creature: +1 if Bob’s move wins over Alice’s, 0 if they are the same (draw), and -1 otherwise. The DP state dp[i][prev_move][difference] tracks the number of ways to reach round i with a given last move and a net score difference (tracked with an offset to handle negative values). Initialization is done for round 0 where Bob is free to choose any creature. For subsequent rounds (i from 1 to n-1), we iterate over all valid previous states and consider the two possible moves (since Bob cannot repeat the last move). Finally, we sum all ways having a positive difference at the last round. Modular arithmetic (mod = 10^9+7) is applied at every update.

Code Solutions

# Python solution with detailed comments
MOD = 10**9 + 7

def countWinningSequences(s: str) -> int:
    n = len(s)
    # Map creatures to a numeric index for ease of use
    char_to_idx = {'F': 0, 'W': 1, 'E': 2}
    # Determine outcome when Bob plays 'b' and Alice plays 'a'
    # Winning pairs: (F beats E), (W beats F), (E beats W)
    def outcome(b, a):
        # if same creature then draw
        if b == a:
            return 0
        # Win conditions
        if (b, a) in [(0, 2), (1, 0), (2, 1)]:
            return 1
        # Otherwise loss
        return -1

    # Offset to shift differences into positive range
    offset = n
    # DP dimensions: 2 rounds using 3 moves and difference range 0 to 2*n.
    # We only need current and next round layers.
    dp = [[0] * (2*n + 1) for _ in range(3)]
    
    # Initialize for round 0: Bob can choose any creature.
    a0 = char_to_idx[s[0]]
    for move in range(3):
        diff = outcome(move, a0)
        dp[move][diff + offset] = 1

    # Process rounds 1 to n-1
    for i in range(1, n):
        # Next round dp initialization
        next_dp = [[0] * (2*n + 1) for _ in range(3)]
        a_move = char_to_idx[s[i]]
        for prev_move in range(3):
            for diff in range(2*n + 1):
                if dp[prev_move][diff] != 0:
                    # Try all possible moves for Bob that are not equal to prev_move
                    for move in range(3):
                        if move == prev_move:
                            continue
                        change = outcome(move, a_move)
                        new_diff = diff - offset + change  # actual difference value
                        new_index = new_diff + offset
                        if 0 <= new_index < 2*n + 1:
                            next_dp[move][new_index] = (next_dp[move][new_index] + dp[prev_move][diff]) % MOD
        dp = next_dp

    # Sum all states where score difference is >0
    result = 0
    for last_move in range(3):
        for diff in range(offset+1, 2*n + 1):  # positive difference indices
            result = (result + dp[last_move][diff]) % MOD
    return result

# Example usage:
s = "FWEFW"
print(countWinningSequences(s))
← Back to All Questions