Palindromic Game

[tetraxx]

Alice and Bob are playing a game with a string of English alphabets (both uppercase and lowercase). They can select a character either from the start or end of the string. Put the selected character in a common box. The winner of the game is the first person who can make a string palindrome of length greater than 1 by using some of the box's characters. Alice starts first to pick a character and both players play optimally. Determine the winner of the game or depict if it is a Tie.

Note: A tie occurs when no one wins.

For example: If the string is aabc, then Alice can select the character 'a' or 'c' and store it into the box. If Alice chooses 'a', then the resulting string for Bob is abc. This helps Bob so that he can select either 'a' or 'c', so he can select 'a' and store it into box. Now, Bob can make a string 'aa' which is a palindrome of length is greater than 1. Hence, Bob wins the game.



Can somebody please explain this editorial?

Editorial:
We don't need to see the whole string for the palindrome, we can use 2 same characters for making a string into a palindrome, so we need to see 27 characters from beginning and 27 characters from ending. As lowercase characters will repeat from 27th index. And that's why we consider this 27th character from the ending.

What we are going to do is now check the states of string which are game-over(where a person will definitely loose). We can do this simply in O(N^3) where (N is at max 27 + 27 = 54).

Then we introduce the concept of winning and losing positions, Game over positions are denoted as losing positions, A game is winning if and only if one of the possible legal moves leads to a losing position. A game is losing if and only if all possible legal moves lead to winning positions.

And hence we can do it like this: dp[i][j] = !dp[i+1][j] || !dp[i][j-1]. where i and j are the index of string.

Also, check if the game is Tie by checking the string if characters repeat in it or not.

  #include<bits/stdc++.h>
using namespace std;
#define nl endl
int dp[60][60];
int vis[60][60];
int go(int i, int j){
    if(i > j)   return 0;
    if(i == j)  return dp[i][j];
    vis[i][j] = 1;
    // return game-over states
    if(dp[i][j] == 0)
        return dp[i][j];
    // go to non visited states
    int a = 1, b = 1;
    if(vis[i+1][j] == 0){
        a = go(i+1, j);
    }
    else a = dp[i+1][j];
    if(vis[i][j-1] == 0){
        b = go(i, j-1);
    }
    else b = dp[i][j-1];
    return dp[i][j] = !a || !b;
}
int main(){
    string s;
    cin>>s;
    int n = s.size();
    
    // Edge Case
    if(n == 2 && s[0] == s[1]){
        cout<<"Bob"<<nl;
        return 0;
    }
    if(s.size() > 54){
        s = s.substr(0, 27) + s.substr(n-27);
        n = s.size();
    }    
    std::vector<pair<int, int> > v;
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            set<char> st;
            bool fl = 0;
            for(int k = 0; k < i; k++){
                if(st.count(s[k])){
                    fl = 1;
                }
                st.insert(s[k]);
            }
            for(int l = j+1; l < n; l++){
                if(st.count(s[l])){
                    fl = 1;
                    break;
                }
                st.insert(s[l]);
            }
            if(fl)
                v.push_back({i,j});
        }
    }
    // tie case
    if(v.size() == 0){
        cout<<"Tie\n";
        return 0;
    }
    
    for(int i = 0; i < 60; i++){
        for(int j = 0; j < 60; j++){
            dp[i][j] = 1;
        }
    }
    // Game-over are marked as 0
    for(auto x: v){
        dp[x.first][x.second] = 0;
    }
    cout<<(go(0, n-1)?("Alice"):("Bob"))<<nl;
    return 0;
}

Link to the question: https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/palindrome-game-dcf03e89/

[ne555]

> Can somebody please explain this editorial?
¿what part in particular?

> As lowercase characters will repeat from 27th index
the editorial seems to be ignoring uppercase characters
the game will last at most 26+26+1 = 53 turns, and so you need 53 characters from each end.