Codeforces 455B - A Lot of Games

Problem Statement:
455B - A Lot of Games

Solution:
An interesting game theory problem. As usual, game theory problems tend to be pretty creative. First of all, we need to build a prefix tree using all the strings, which can be done in \(O(N)\). The root of the tree is an empty string, which is also the initial state of the game. The tree hence represent the graph of valid moves on each state of the game. We want to know, assuming both players play optimally, whether First can force his way to win and also whether he can lose a given game. We can use Sprague Grundy Theorem, but for this particular problem it is not necessary, as we can use a simple dynamic programming reasoning. First denote win[u] and lose[u] as the table which tells us whether the current player who has to move at state u can eventually win or lose. Suppose we want to fill up win[u], we check all states v that is directly pointed by u, and win[u] is only true if and only if there is a state with win[v] which is false. This reasoning also applies for filling up lose[u].



So knowing whether First can win or lose a game will give us a simple way to decide whether First can win the whole game. If First can both win and lose, then he can just lose until the last round for which he wins the game. Otherwise, if First can only win, then First and Second will alternately start the rounds, so if First ends up starting the last round, he will win. Finally, if First can only lose, then he will definitely lose :D

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
using namespace std;

int adj[100005][27];
int win[100005];    //can first person win if start at node u?
int lose[100005];   //can first person lose if start at node u?
int N, K, node;
string s[100005];

void build(int n){
    int cur = 1;
    int k = 0;
    int sz = s[n].size();
    while(k<sz && adj[cur][s[n][k]-'a']){
        cur = adj[cur][s[n][k]-'a'];
        ++k;
    }
    while(k<sz){
        adj[cur][s[n][k]-'a'] = ++node;
        cur = node;
        ++k;
    }

}

void build_win_lose(int u){
    bool isleaf = true;
    win[u] = lose[u] = 0;
    for(int i=0;i<26;++i){
        if(!adj[u][i])continue;
        isleaf=false;
        build_win_lose(adj[u][i]);
        if(win[adj[u][i]]==0)win[u]=1;
        if(lose[adj[u][i]]==0)lose[u]=1;
    }
    if(isleaf){
        win[u] = 0;
        lose[u] = 1;
    }
}

int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;++i){
        cin >> s[i];
    }
    node = 1;
    for(int i=0;i<N;++i){
        build(i);
    }
    build_win_lose(1);
    if(win[1]&&lose[1]){
        printf("First\n");
    } else {
        if(win[1]){
            if(K%2)printf("First\n"); else printf("Second\n");
        } else {
            printf("Second\n");
        }
    }
    return 0;
}