## Intuition The problem is about reconstructing a sequence of poker game results such that the difference between wins and losses never exceeds a given threshold `k`. The sequence contains known results (`W`, `L`, `D`) and unknown results (`?`). Our task is to replace `?` with `W`, `L`, or `D` to ensure the sequence is valid according to the rules. The key insight is to maintain a balance between wins and losses as we process the sequence. We must ensure that at no point does the difference between the number of wins and losses exceed `k`. ## Approach 1. **Initialize Counters**: Start by counting the number of wins (`W`), losses (`L`), and draws (`D`) in the given sequence. Also, count the number of unknowns (`?`). 2. **Simulate the Sequence**: Traverse the sequence and try to replace each `?` with `W`, `L`, or `D` such that the difference between wins and losses never exceeds `k`. 3. **Decision Making**: - If the current difference between wins and losses is less than `k`, prioritize converting `?` to `W` to increase wins. - If the difference is greater than `-k`, prioritize converting `?` to `L` to increase losses. - If the difference is exactly `k` or `-k`, convert `?` to `D` to maintain the balance. 4. **Validation**: After processing the sequence, check if the final difference between wins and losses is within the allowed range. If not, output "NO". 5. **Output the Result**: If a valid sequence is found, print it. ## Complexity - **Time**: O(n), where `n` is the length of the sequence. We process each character of the sequence once. - **Space**: O(1), as we only use a fixed amount of extra space for counters. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; string s; cin >> s; int wins = 0, losses = 0, draws = 0, unknowns = 0; // Count initial number of W, L, D, and ? for (char c : s) { if (c == 'W') wins++; else if (c == 'L') losses++; else if (c == 'D') draws++; else if (c == '?') unknowns++; } // Process each character and replace '?' with the appropriate result for (int i = 0; i < n; ++i) { if (s[i] == '?') { if (wins - losses < k) { s[i] = 'W'; wins++; } else if (losses - wins < k) { s[i] = 'L'; losses++; } else { s[i] = 'D'; draws++; } } } // Final check to ensure the sequence is valid if (abs(wins - losses) > k) { cout << "NO" << endl; } else { cout << s << endl; } return 0; } ``` This solution efficiently processes the sequence, replacing `?` with the most suitable result to maintain the balance between wins and losses, ensuring the sequence remains valid.

Roma and Poker

Problem Details