# Educational Codeforces Round 135 ## Problem D. Letter Picking

Interval game dp, state f[][], but simpler than general game dp, transition trivial.

First of all, we can bind the two rounds of operations together to transfer, as long as the state with an even length is considered, and there is no need to record what character was selected in the previous round.

It is not difficult to further conclude that the result is only likely to be a first mover win or a draw, which further simplifies the state and transition.

`   #include <lastweapon/io>   using namespace lastweapon;      const int N = int(2e3) + 9;   char s[N]; bool f[N][N];   int n;      int main() {   #ifndef ONLINE_JUDGE       freopen("in.txt", "r", stdin);       //freopen("out.txt", "w", stdout);   #endif       Rush {           n = strlen(RS(s));              REP(i, n+1) f[i][i] = 0;              for(int l=2;l<=n;l+=2) {               REP(i, n-l+1) {                   int j = i+l;                   bool ll = f[i+2][j] || (s[i] > s[i+1]);                   bool lr = f[i+1][j-1] || (s[i] > s[j-1]);                   bool rl = f[i+1][j-1] || (s[j-1] > s[i]);                   bool rr = f[i][j-2] || (s[j-1] > s[j-2]);                   f[i][j] = (ll && lr) || (rl && rr);               }           }           puts(f[n] ? "Alice" : "Draw");       }   }   `

Expense flow?