fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. // We use 2D vectors for memoization.
  8. // memoA[l][r] = Can Alice win if it's her turn on S[l...r]?
  9. // memoB[l][r] = Can Alice win if it's Bob's turn on S[l...r]?
  10. vector<vector<int>> memoA;
  11. vector<vector<int>> memoB;
  12. string S;
  13. vector<int> prefixA, prefixB;
  14.  
  15. // Helper to count 'A's in S[l...r]
  16. int countA(int l, int r) {
  17.     if (l > r) return 0;
  18.     return prefixA[r + 1] - prefixA[l];
  19. }
  20.  
  21. // Helper to count 'B's in S[l...r]
  22. int countB(int l, int r) {
  23.     if (l > r) return 0;
  24.     return prefixB[r + 1] - prefixB[l];
  25. }
  26.  
  27. // Solves for memoB[l][r]
  28. bool solveB(int l, int r);
  29.  
  30. // Solves for memoA[l][r] (Alice's turn)
  31. bool solveA(int l, int r) {
  32.     if (l > r) {
  33.         return false; // Base case: Bob made the last move, Alice loses
  34.     }
  35.     if (memoA[l][r] != -1) {
  36.         return memoA[l][r];
  37.     }
  38.  
  39.     // Check if Alice can move
  40.     if (countA(l, r) == 0) {
  41.         return memoA[l][r] = solveB(l, r); // Alice skips
  42.     }
  43.  
  44.     // Alice wants to find *any* move that leads to a win (true).
  45.     // We can use the O(N^2) optimization:
  46.     // A_win[l][r] = (S[l] == 'A' ? B_win[l+1][r] : false) || A_win[l+1][r]
  47.  
  48.     bool canWin = solveA(l + 1, r); // Result if she doesn't pick S[l]
  49.     if (S[l] == 'A') {
  50.         canWin = canWin || solveB(l + 1, r); // Result if she picks S[l]
  51.     }
  52.  
  53.     return memoA[l][r] = canWin;
  54. }
  55.  
  56. // Solves for memoB[l][r] (Bob's turn)
  57. bool solveB(int l, int r) {
  58.     if (l > r) {
  59.         return true; // Base case: Alice made the last move, Alice wins
  60.     }
  61.     if (memoB[l][r] != -1) {
  62.         return memoB[l][r];
  63.     }
  64.  
  65.     // Check if Bob can move
  66.     if (countB(l, r) == 0) {
  67.         return memoB[l][r] = solveA(l, r); // Bob skips
  68.     }
  69.  
  70.     // Bob wants to find *any* move that leads to a loss for Alice (false).
  71.     // Alice only wins if *all* of Bob's moves lead to a win for her.
  72.     // B_win[l][r] = (S[r] == 'B' ? A_win[l][r-1] : true) && B_win[l][r-1]
  73.  
  74.     bool canAliceWin = solveB(l, r - 1); // Result if Bob doesn't pick S[r]
  75.     if (S[r] == 'B') {
  76.         canAliceWin = canAliceWin && solveA(l, r - 1); // Result if Bob picks S[r]
  77.     }
  78.  
  79.     return memoB[l][r] = canAliceWin;
  80. }
  81.  
  82. string solve() {
  83.     int N;
  84.     cin >> N;
  85.     cin >> S;
  86.  
  87.     // Initialize memoization tables with -1 (uncomputed)
  88.     memoA.assign(N, vector<int>(N, -1));
  89.     memoB.assign(N, vector<int>(N, -1));
  90.  
  91.     // Precompute prefix sums for 'A' and 'B' counts
  92.     prefixA.assign(N + 1, 0);
  93.     prefixB.assign(N + 1, 0);
  94.     for (int i = 0; i < N; ++i) {
  95.         prefixA[i + 1] = prefixA[i] + (S[i] == 'A');
  96.         prefixB[i + 1] = prefixB[i] + (S[i] == 'B');
  97.     }
  98.  
  99.     if (solveA(0, N - 1)) {
  100.         return "Alice";
  101.     } else {
  102.         return "Bob";
  103.     }
  104. }
  105.  
  106. int main() {
  107.     int T;
  108.     cin >> T;
  109.     for (int i = 1; i <= T; ++i) {
  110.         cout << "Case #" << i << ": " << solve() << endl;
  111.     }
  112.     return 0;
  113. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6
7
ABBAAAB
1
A
1
B
2
AB
6
AAAAAA
7
BBBBBBA
stdout
copy 
Case #1: Alice
Case #2: Alice
Case #3: Bob
Case #4: Bob
Case #5: Alice
Case #6: Alice
https://ideone.com/H2j9rA
language:
C++ (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!