TopCoder SRM 637

Division 1
Problem 250:
SRM 637 Div1 (250) - GreaterGame

Solution:
To find the expectation, first sort the cards on each hand. Then for each of the known Sothe's card, we can determine whether we want to top the card with the lowest possible card on our hand, or just lose with the lowest possible card. Each of the card that we topped will contribute to the expectation by 1, and those we lose contribute 0. Then we will end up with the cards that Sothe did not reveal, and the cards that we do not used yet. For each card on our hand, we find the probability of our card winning given the knowledge of Sothe's remaining cards. Each of the probability contributes to our expectation. Hence we just sum up all the probabilities with the number of the cards that we won earlier on.



Problem 500:
Problem Statement:
SRM 637 Div 1 (500) - PathGame

Solution:
The problem requires a knowledge on Sprague-Grundy Theorem on impartial game assuming normal play condition. The board game can be modeled as an impartial game: Given a board of length k, with a path starting on the left and an ending point on the right, determine whether the game is N or P. We have 9 types of such games depending on which row can be our starting point and which row can be our ending point. Then we do a DP on every grundy number on each possible game moves, which is the minimum excluded number amongst the grundy numbers of the direct child vertices of the current vertex on the game graph. Finally we check the board and find out what is its grundy number. If it is equal to 0, then the game is P, otherwise it is N.

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

int grundy[1003][3][3];
int mex[10050];
class PathGame {
public:
    string judge(vector<string> board) {
        int N = board[0].size();
        for(int i=0;i<=10*N;++i){
            mex[i] = 0;
        }
        int pc = 0;
        for(int i=0;i<3;++i){
            for(int j=0;j<3;++j){
                grundy[0][i][j] = 0;
            }
        }
        for(int k=1;k<=N;++k){
            for(int left=0;left<3;++left){
                for(int right=0;right<3;++right){
                    ++pc;
                    for(int i=1;i<=k;++i){
                        for(int p=1;p<=2;++p){
                            if(i == 1 && left+p == 3) continue;
                            if(i == k && right+p == 3) continue;
                            int gnum = grundy[i-1][left][p] ^ grundy[k-i][p][right];
                            mex[gnum] = pc;
                        }
                    }
                    for(int i=0;i<=10*N;++i){
                        if(mex[i] < pc) {
                            grundy[k][left][right] = i;
                            break;
                        }
                    }
                }
            }
        }
        int next = 0;
        int prev = 0;
        int ans = 0;
        for(int i=0;i<N;++i){
            int p = 0;
            if(board[0][i] == '#') p = 1;
            if(board[1][i] == '#') p = 2;
            if (p > 0) {
                ans ^= grundy[i-next][prev][p];
                prev = p;
                next = i+1;
            }
        }
        ans ^= grundy[N-next][prev][0];
        if (ans == 0) return "Sothe"; else return "Snuke";
    }
};