<p>Alice and Bob take turns playing a game, with <strong>Alice</strong><strong>&nbsp;starting first</strong>.</p>

<p>You are given a string <code>num</code> of <strong>even length</strong> consisting of digits and <code>&#39;?&#39;</code> characters. On each turn, a player will do the following if there is still at least one <code>&#39;?&#39;</code> in <code>num</code>:</p>

<ol>
	<li>Choose an index <code>i</code> where <code>num[i] == &#39;?&#39;</code>.</li>
	<li>Replace <code>num[i]</code> with any digit between <code>&#39;0&#39;</code> and <code>&#39;9&#39;</code>.</li>
</ol>

<p>The game ends when there are no more <code>&#39;?&#39;</code> characters in <code>num</code>.</p>

<p>For Bob&nbsp;to win, the sum of the digits in the first half of <code>num</code> must be <strong>equal</strong> to the sum of the digits in the second half. For Alice&nbsp;to win, the sums must <strong>not be equal</strong>.</p>

<ul>
	<li>For example, if the game ended with <code>num = &quot;243801&quot;</code>, then Bob&nbsp;wins because <code>2+4+3 = 8+0+1</code>. If the game ended with <code>num = &quot;243803&quot;</code>, then Alice&nbsp;wins because <code>2+4+3 != 8+0+3</code>.</li>
</ul>

<p>Assuming Alice and Bob play <strong>optimally</strong>, return <code>true</code> <em>if Alice will win and </em><code>false</code> <em>if Bob will win</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;5023&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> There are no moves to be made.
The sum of the first half is equal to the sum of the second half: 5 + 0 = 2 + 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;25??&quot;
<strong>Output:</strong> true
<strong>Explanation: </strong>Alice can replace one of the &#39;?&#39;s with &#39;9&#39; and it will be impossible for Bob to make the sums equal.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;?3295???&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> It can be proven that Bob will always win. One possible outcome is:
- Alice replaces the first &#39;?&#39; with &#39;9&#39;. num = &quot;93295???&quot;.
- Bob replaces one of the &#39;?&#39; in the right half with &#39;9&#39;. num = &quot;932959??&quot;.
- Alice replaces one of the &#39;?&#39; in the right half with &#39;2&#39;. num = &quot;9329592?&quot;.
- Bob replaces the last &#39;?&#39; in the right half with &#39;7&#39;. num = &quot;93295927&quot;.
Bob wins because 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= num.length &lt;= 10<sup>5</sup></code></li>
	<li><code>num.length</code> is <strong>even</strong>.</li>
	<li><code>num</code> consists of only digits and <code>&#39;?&#39;</code>.</li>
</ul>

class Solution:
    def sumGame(self, num: str) -> bool:
        # Alice starts
        #
        # given num of even length, digits plus ?
        #
        # each turn: player will
        #    > choose index i where num[i] == '?'
        #    > replace num[i] == 0..9 (player's choice)
        # game ends when num[i] has no ? left
        #
        # Bob wins if sum of digits in first half of num == sum of digits in second half

        # so winner of game depends on whose turn it is, we'll need a player flag
        #
        # for 1e5 we can't afford a classic exhaustive search unless we're clever about it
        # only the sums of the first and second half matter, which helps
        # and only the *difference* in the sums of the first and second half matter which helps even more

        # suppose there are L ? in the left half, R ? in the right half, current difference sum(L)-sum(R) is D
        #
        #     player can set a ? in L to d: D+d, L-1, R    if L > 0
        #                 or a ? in R to d: D-d, L, R-1    if R > 0
        #
        # Some ideas:
        #    > if L==R then the plays can alternate D + d - d + d - d etc. or -d+d-d+d..
        #        > if Alice plays next, and the current difference is 0, she loses: whatever she plays, bob plays the opposite
        #                                                           !=0: she wins: she plays +9 and bob can only do -9
        #    > if L > R: does it devolve to R,R and L-R, 0 phases?
        #         we have to play ALL rounds, so probably
        #
        #       so I think the Nim-ish game here devolves to some clever edge case checking

        N = len(num)
        L = sum(num[i] == '?' for i in range(N//2))
        R = sum(num[i] == '?' for i in range(N//2, N))

        D = sum(int(num[i]) if num[i] != '?' else 0 for i in range(N//2))
        D -= sum(int(num[i]) if num[i] != '?' else 0 for i in range(N//2, N))

        print(f"{L=}, {R=}, {D=}")

        # if D == 0:
        #     if L == R: return False # if alice changes D by +-d, Bob can do a corresponding -+d
        #     else:
        #         # wlog let L > R, else flip the signs but the idea is the same
        #         # while R: alice picks 9, Bob picks -9 for L-=1 and R-=1
        #         # eventually L is nonzero and it's Alice's turn. She picks d=9 again and wins
        #         return True
        # elif D > 0:
        #     if L == R: return True # same idea as D==0 and L==R, except Alice forces a win by picking +9
        #     elif L > R: return True
        #         # Alice can pick +9 every time. Bob at best picks -9 as long as possible leading to L-R,0. Then it's all positive picks from there
        #     else:
        #         # Alice picks +9 every time to avoid hitting zero
        #         # Bob picks -9 every time until we get to 0, R-L
        #         # then we get a classic Nim game on R-L choices to hit 0 exactly
        #         R -= L
        #         # alice plays first
        #         # if Alice also plays last then she wins, probably, because no matter what Bob achieves for the last play,
        #         # alice has 9 options
        #         if R & 1: return True

        #         # else there are an even number of plays
        #         # no matter what Alice plays, Bob can play the "9s complement", alice plays -= d and Bob plays -= (9-d)
        #         # Alice can force a win by
        #         #      A. playing -9 every turn, dropping D below 0
        #         #      B. playing 0 every turn, keeping D above 0
        #         # if R//2 * 9 > D: return True # -9 every turn, Alice forces final score below 0
        #         # elif R//2 * 9 < D: return True # Alice plays -0 every turn, Bob picks -9, final score above 0
        #         # else: return False # D == R//2 * 9: if Alice reduces D by d, Bob reduces by 9-d | every turn reduces by 9 exactly
        #         return R//2 * 9 != D
        # else:
        #     # D > 0, L >= R is isomorphic to D < 0, R <= L
        #     if R >= L: return True # alice wins by picking -9 every turn, Bob at best (L==R) can end with D==R, else D at end < current D
        #     else:
        #         # D < 0 and L > R, same as above but Bob is trying to increase D to zero instead of decrease it
        #         L -= R
        #         if L & 1: return True # Alice has the last play so she can spoil whatever Bob sets up
                
        #         return L//2 * 9 == -D # same idea as R>L and D>0: if L//2 rounds times 9 is D, bob can force a drop of D every turn and win, else Alice wins
        #         #                       by picking 0 every turn to keep D < 0, or +9 every turn to get +D

        ### FIX: not sure what's wrong above, probably a basic error. Let's canonicalize as much as possible.
        
        ## no matter what D is, Alice wants to keep D != 0 so she'll oppose Bob's changes to move D toward zero
        # so she'll pick +9 or -9 according to the sign of D, and Bob will oppose it: D doesn't change, L and R -= 1 each turn
        if L > R:
            L -= R
            R = 0
        else:
            R -= L
            L = 0

        if R:
            # L=0,R,D is isomorphic to R,R=0,-D: for 0,R,D Bob will decrease D toward 0, or for R,0,-D he'll increase it
            L = R
            D = -D

        # now we've canonicalized to L,0,D

        # if D > 0: Alice picks +9 every turn for the win
        # if L&1: Alice gets the last play, no matter what D is after Bob's turn, Alice just has to pick d != D to win;
        #    she has 9 choices so by the pigeonhole principle she has at LEAST 8 winning plays
        if D > 0 or L&1: return True # already positive, nothing Bob can do. Or Alice gets the last play and spoil's Bob's efforts in the last play

        # if L//2*9 > 0: alice plays +9 every time to force a final score above 0
        # if L//2*9 < 0: Alice plays 0 every time, Bob plays +9 every turn but it's not enough to get to 0
        # else: if Alice plays d, Bob plays 9-d for an increase of 9 on each of the L//2 rounds. L//2*9 == -D means this lets Bob force a final score of 0
        return L//2*9 != -D
170