## Intuition The problem involves determining how many initial and final box positions are possible for the doll such that Marisa can always win the game. The key insight is that Marisa can move the doll to an adjacent box or keep it in the same box after each guess. This means that the doll's position can be adjusted to avoid any guessed positions by Alice. The problem can be visualized as a dynamic programming problem where we keep track of the possible positions of the doll after each guess. The goal is to count all possible transitions from any starting position to any ending position after all guesses. ## Approach 1. **Initialization**: We will use a dynamic programming table `dp[i][j]` where `i` represents the number of guesses made, and `j` represents the position of the doll. `dp[i][j]` will store the number of ways the doll can be at position `j` after `i` guesses. 2. **Base Case**: Before any guesses, the doll can be in any position, so initialize `dp[0][j] = 1` for all `j` from `1` to `n`. 3. **DP Transition**: For each guess `i`, update the possible positions `j`: - If `j` is not the guessed position `a[i]`, the doll can stay at `j`, move from `j-1` to `j`, or move from `j+1` to `j`. - Use prefix sums to efficiently compute the number of ways to reach each position `j` from the previous positions. 4. **Final Count**: After processing all guesses, sum up all values in `dp[m][j]` to get the total number of scenarios where Marisa can win. 5. **Optimization**: Use a single array for `dp` and update it in place to save space. ## Complexity - **Time**: O(n * m), where `n` is the number of boxes and `m` is the number of guesses. This is because we iterate over all boxes for each guess. - **Space**: O(n), since we only need to maintain the current state of the dp array. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector a(m); for (int i = 0; i < m; ++i) { cin >> a[i]; } vector dp(n + 1, 1); // dp[0] is unused, dp[1] to dp[n] are used vector prefix_sum(n + 1, 0); for (int i = 0; i < m; ++i) { // Calculate prefix sums for the current dp array prefix_sum[0] = 0; for (int j = 1; j <= n; ++j) { prefix_sum[j] = prefix_sum[j - 1] + dp[j]; } // Update dp for the next guess vector new_dp(n + 1, 0); for (int j = 1; j <= n; ++j) { if (j != a[i]) { // Sum of ways to reach j from j-1, j, j+1 new_dp[j] = prefix_sum[min(n, j + 1)] - prefix_sum[max(0, j - 2)]; } } dp = new_dp; } // Sum all possible end positions long long result = 0; for (int j = 1; j <= n; ++j) { result += dp[j]; } cout << result << '\n'; return 0; } ``` This solution efficiently calculates the number of ways Marisa can win by using dynamic programming and prefix sums to handle the transitions between possible positions of the doll after each guess.

Alice and the Unfair Game

Problem Details