Letter Picking
Contest: Educational Codeforces Round 135 (Rated for Div. 2)
Difficulty rating: 1800
Tags: constructive algorithms, dp, games, two pointers

Alice and Bob are playing a game. Initially, they are given a non-empty string $$$s$$$, consisting of lowercase Latin letters. The length of the string is even. Each player also has a string of their own, initially empty.

Alice starts, then they alternate moves. In one move, a player takes either the first or the last letter of the string $$$s$$$, removes it from $$$s$$$ and prepends (adds to the beginning) it to their own string.

The game ends when the string $$$s$$$ becomes empty. The winner is the player with a lexicographically smaller string. If the players' strings are equal, then it's a draw.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if there exists such position $$$i$$$ that $$$a_j = b_j$$$ for all $$$j < i$$$ and $$$a_i < b_i$$$.

What is the result of the game if both players play optimally (e. g. both players try to win; if they can't, then try to draw)?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

Each testcase consists of a single line — a non-empty string $$$s$$$, consisting of lowercase Latin letters. The length of the string $$$s$$$ is even.

The total length of the strings over all testcases doesn't exceed $$$2000$$$.

Output format:
For each testcase, print the result of the game if both players play optimally. If Alice wins, print "Alice". If Bob wins, print "Bob". If it's a draw, print "Draw".

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
One of the possible games Alice and Bob can play in the first testcase:

1. Alice picks the first letter in $$$s$$$: $$$s=$$$"orces", $$$a=$$$"f", $$$b=$$$"";
2. Bob picks the last letter in $$$s$$$: $$$s=$$$"orce", $$$a=$$$"f", $$$b=$$$"s";
3. Alice picks the last letter in $$$s$$$: $$$s=$$$"orc", $$$a=$$$"ef", $$$b=$$$"s";
4. Bob picks the first letter in $$$s$$$: $$$s=$$$"rc", $$$a=$$$"ef", $$$b=$$$"os";
5. Alice picks the last letter in $$$s$$$: $$$s=$$$"r", $$$a=$$$"cef", $$$b=$$$"os";
6. Bob picks the remaining letter in $$$s$$$: $$$s=$$$"", $$$a=$$$"cef", $$$b=$$$"ros".

Alice wins because "cef" < "ros". Neither of the players follows any strategy in this particular example game, so it doesn't show that Alice wins if both play optimally.

Example input:
2
forces
abba

Example output:
Alice
Draw

Editorial:
What do we do, when the array loses elements only from the left or from the right and the constraints obviously imply some quadratic solution? Well, apply dynamic programming, of course.
The classic $$$dp[l][r]$$$ — what is the outcome if only the letters from positions $$$l$$$ to $$$r$$$ (non-inclusive) are left. $$$dp[0][n]$$$ is the answer. $$$dp[i][i]$$$ is the base case — the draw (both strings are empty). Let $$$-1$$$ mean that Alice wins, $$$0$$$ be a draw and $$$1$$$ mean that Bob wins.
How to recalculate it? Let's consider a move of both players at the same time. From some state $$$[l; r)$$$, first, Alice goes, then Bob. The new state becomes $$$[l', r')$$$, Alice picked some letter $$$c$$$, Bob picked some letter $$$d$$$. What's that pick exactly? So, they both got a letter, prepended it to their own string. Then continued the game on a smaller string $$$s$$$ and prepended even more letters to the string. Thus, if we want to calculate $$$[l, r)$$$ from $$$[l', r')$$$, we say that we append letters $$$c$$$ and $$$d$$$. Now it's easy. If $$$dp[l'][r']$$$ is not a draw, then the new letters change nothing — the result is still the same. Otherwise, the result of the game is the same as the comparison of letters $$$c$$$ and $$$d$$$.
How to perform both moves at once? First, we iterate over the Alice's move: whether she picks from $$$l$$$ or from $$$r$$$. After that we iterate over the Bob's move: whether he picks from $$$l$$$ or from $$$r$$$. Since we want $$$dp[l][r]$$$ to be the best outcome for Alice, we do the following. For any Alice move, we choose the worse of the Bob moves — the maximum of $$$dp[l'][r']$$$. Among the Alice's moves we choose the better one — the minimum one.
Overall complexity: $$$O(n^2)$$$ per testcase.