Palindrome Game (hard version)
Contest: Codeforces Round 721 (Div. 2)
Difficulty rating: 1900
Tags: constructive algorithms, games

The only difference between the easy and hard versions is that the given string $$$s$$$ in the easy version is initially a palindrome, this condition is not always true for the hard version.

A palindrome is a string that reads the same left to right and right to left. For example, "101101" is a palindrome, while "0101" is not.

Alice and Bob are playing a game on a string $$$s$$$ of length $$$n$$$ consisting of the characters '0' and '1'. Both players take alternate turns with Alice going first.

In each turn, the player can perform one of the following operations:

1. Choose any $$$i$$$ ($$$1 \le i \le n$$$), where $$$s[i] =$$$ '0' and change $$$s[i]$$$ to '1'. Pay 1 dollar.
2. Reverse the whole string, pay 0 dollars. This operation is only allowed if the string is currently not a palindrome, and the last operation was not reverse. That is, if Alice reverses the string, then Bob can't reverse in the next move, and vice versa.

Reversing a string means reordering its letters from the last to the first. For example, "01001" becomes "10010" after reversing.

The game ends when every character of string becomes '1'. The player who spends minimum dollars till this point wins the game and it is a draw if both spend equal dollars. If both players play optimally, output whether Alice wins, Bob wins, or if it is a draw.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$). Then $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^3$$$).

The second line of each test case contains the string $$$s$$$ of length $$$n$$$, consisting of the characters '0' and '1'. It is guaranteed that the string $$$s$$$ contains at least one '0'.

Note that there is no limit on the sum of $$$n$$$ over test cases.

Output format:
For each test case print a single word in a new line:

- "ALICE", if Alice will win the game,
- "BOB", if Bob will win the game,
- "DRAW", if the game ends in a draw.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case of example,

- in the $$$1$$$-st move, Alice will use the $$$2$$$-nd operation to reverse the string, since doing the $$$1$$$-st operation will result in her loss anyway. This also forces Bob to use the $$$1$$$-st operation.
- in the $$$2$$$-nd move, Bob has to perform the $$$1$$$-st operation, since the $$$2$$$-nd operation cannot be performed twice in a row. All characters of the string are '1', game over.

In the second test case of example,

- in the $$$1$$$-st move Alice has to perform the $$$1$$$-st operation, since the string is currently a palindrome.
- in the $$$2$$$-nd move Bob reverses the string.
- in the $$$3$$$-rd move Alice again has to perform the $$$1$$$-st operation. All characters of the string are '1', game over.

Example input:
3
3
110
2
00
4
1010

Example output:
ALICE
BOB
ALICE

Editorial:
Solution 1:
The case when $$$s$$$ is a palindrome is discussed in B1. Otherwise, Alice will win or the game will end with a draw.
Proof
• If it is optimal for Alice to perform operation $$$1$$$ in the first move, she will perform it else she will perform operation $$$2$$$ forcing Bob to perform operation $$$1$$$ (which is not optimal otherwise Alice would have performed it in the first move).
Optimal Strategy for Alice
• Alice will keep reversing the string till string $$$s$$$ is one move short to become a palindrome with an even number of zeros. This time Alice will perform operation $$$1$$$ instead of reversing and will make string $$$s$$$ a palindrome. Now, string $$$s$$$ is a palindrome containing an even number of zeros, with Bob's turn. Here, Alice can take $$$2$$$ dollars advantage using the strategy mentioned in B1. This way Bob will spend at least $$$1$$$ dollars more than Alice resulting in Alice's win.
• In some cases like '1100', '1001110' Alice will just keep on reversing the string and Bob has to change all '0' to 1'.
Solution 2:
As constraints on $$$n$$$ were small, the problem can also be solved using dynamic programming.
Following parameters of string $$$s$$$ is enough define current state of game:
• $$$cnt00$$$ = count of symmetric $$$00$$$ pair ($$$s[i]=$$$'0' as well as $$$s[n-i+1]=$$$'0')
• $$$cnt01$$$ = count of symmetric $$$01$$$ or $$$10$$$ pair ($$$s[i]$$$ is not equal to $$$s[n-i+1]$$$)
• $$$mid$$$ = $$$True$$$ if mid character exists (length of string is odd) and it is '0' else $$$False$$$
• $$$rev$$$ = $$$True$$$ if previous move was operation $$$2$$$ else $$$False$$$If any player encounters the game state $$$\{cnt00,cnt01,mid,rev\}$$$, we define $$$dp_{cnt00,cnt01,mid,rev}$$$ to be the minimum cost difference he/she can achieve from here.Transition is pretty simple   if $$$rev$$$ is $$$False$$$ and $$$cnt01>0$$$: $$$dp_{cnt00,cnt01,mid,rev} = \min(dp_{cnt00,cnt01,mid,rev},-dp_{cnt00,cnt01,mid,True} )$$$  if $$$cnt00>0$$$: $$$dp_{cnt00,cnt01,mid,rev} = \min(dp_{cnt00,cnt01,mid,rev},1-dp_{cnt00-1,cnt01+1,mid,False})$$$  if $$$cnt01>0$$$: $$$dp_{cnt00,cnt01,mid,rev} = \min(dp_{cnt00,cnt01,mid,rev},1-dp_{cnt00,cnt01-1,mid,False})$$$  if $$$mid$$$ is $$$True$$$: $$$dp_{cnt00,cnt01,mid,rev} = \min(dp_{cnt00,cnt01,mid,rev},1-dp_{cnt00,cnt01,False,False})$$$  Finally,   If $$$dp_{cnt00,cnt01,mid,rev}<0$$$, Alice wins  If $$$dp_{cnt00,cnt01,mid,rev}>0$$$, Bob wins  If $$$dp_{cnt00,cnt01,mid,rev}=0$$$, Draw  We can precompute this dp and answer all test cases in $$$O(n)$$$. Overall time complexity - $$$O(n^{2})$$$
• if $$$rev$$$ is $$$False$$$ and $$$cnt01>0$$$: $$$dp_{cnt00,cnt01,mid,rev} = \min(dp_{cnt00,cnt01,mid,rev},-dp_{cnt00,cnt01,mid,True} )$$$
• if $$$cnt00>0$$$: $$$dp_{cnt00,cnt01,mid,rev} = \min(dp_{cnt00,cnt01,mid,rev},1-dp_{cnt00-1,cnt01+1,mid,False})$$$
• if $$$cnt01>0$$$: $$$dp_{cnt00,cnt01,mid,rev} = \min(dp_{cnt00,cnt01,mid,rev},1-dp_{cnt00,cnt01-1,mid,False})$$$
• if $$$mid$$$ is $$$True$$$: $$$dp_{cnt00,cnt01,mid,rev} = \min(dp_{cnt00,cnt01,mid,rev},1-dp_{cnt00,cnt01,False,False})$$$
• If $$$dp_{cnt00,cnt01,mid,rev}<0$$$, Alice wins
• If $$$dp_{cnt00,cnt01,mid,rev}>0$$$, Bob wins
• If $$$dp_{cnt00,cnt01,mid,rev}=0$$$, Draw