STR3-Editorial

editorial
, ,
1

PROBLEM LINK:

Practice Link
Alice and Bob and the game of strings

Author: dragno99
Editorialist: dragno99

PROBLEM:

Alice and Bob are playing a game. They have N number of strings in the beginning of the game. Game begins with Alice and then Bob will play and then Alice and so on…

In each turn, the player must choose any lower case english character and that character must be present in the last position of any string. Now, remove the last character from all the string which has this character at its last position, and discard all the other strings which do not have this character at their last position.

At any time, if the player won’t be able to choose any character then he will lose and the other player will win the game.

Now you have to determine the winner of the game if both players play optimally.

PREREQUISITES:

  • Trie
  • Game Theory

DIFFICULTY:

EASY

EXPLANATION:

Generally in problems like game theory, you should think like, if you can push your opponent in a losing state then currently you are in Winning state and you can definitely win otherwise you are in a losing state and you can not win this game at all.

In this problem we will apply same logic.

Removing the same character from the given strings gives us the idea of building a trie over the given strings when reversed. After constructing the trie, performing the given operation on
the given strings by removing some suffixes of the strings is equivalent to moving through the removed characters in the trie from the root. Now starting from Alice after performing some
number of moves by Alice followed by Bob we will evaluate for every Node V of the trie if Alice has a winning strategy or not. Let us say we are at Node V of our trie, Alice has a winning
strategy at Node V if for any direct Child Node U, Alice has a losing strategy for Node U.

We will evaluate the above condition for every Node V of the trie recursively and if Alice has a winning strategy for the root node of the trie, print “Alice” else print “Bob”.

Time complexity of DFS and building a Trie is O(sum of lengths of all strings).

SOLUTION:

Setter's Solution in C++ 
/*  Jai Shree Ram 🚩🚩🚩 */
#include "bits/stdc++.h"
#define ll long long int
#define oo 1000000000000000000
#define forr(i,n) for(int i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define unique(v) sort(all(v)); v.resize(distance(v.begin(),unique(all(v))))
#define eb emplace_back
#define FF first
#define SS second
#define mem(a,v) memset(a,v,sizeof(a))
#define pb push_back
#define popcount(x) __builtin_popcount(x)

using namespace std;

template<typename T>
ostream &operator<<(ostream &output,const vector<T> &v){ 
   if(v.empty()) return output;
   for(int i=0;i<v.size()-1;i++) output << v[i] <<" ";
   output << v.back();
   return output;
}
template<typename T>
istream &operator>>(istream &input,vector<T> &v){ 
   for(auto &i: v) cin >> i;
   return input;            
}

class Trie{
   class node{
   public:
       node* nxt[26];
       bool is_end;
       node(){
           for(int i=0;i<26;i++){
               nxt[i] = NULL;
           }
           is_end = 0;
       }
   };
   node* root;
public:
   Trie(){
       root = new node();
   }
   void insert(const string &s){
       node* curr = root;
       for(int i=0;i<s.size();i++){
           if(!curr->nxt[s[i] - 'a']){
               curr->nxt[s[i] - 'a'] = new node();
           }
           curr = curr->nxt[s[i] - 'a'];
           curr->is_end = 0;
       }
       curr->is_end = 1;
   }
   bool rec(node *curr){
       int tot_node = 0 , win = 0;
       for(int i=0;i<26;i++){
           if(curr->nxt[i]){
               win += rec(curr->nxt[i]);
               tot_node++;
           }
       }
       if(tot_node == win) return false;
       else return true;
   }
   bool get(){
       node* curr = root;
       return rec(curr);
   }
};


void __sol(){
   int n; cin >> n;
   string s[n];
   forr(i,n) cin >> s[i];
   Trie t;
   forr(i,n){
       reverse(all(s[i]));
       t.insert(s[i]);
   }
   if(t.get()) cout << "Alice\n";
   else cout <<"Bob\n";
   return;
}


int main(){ 
   fastio;
   int tc=1;  cin >> tc;
   while(tc--) __sol();
   return 0;
}
3 Likes