Subtle Substring Subtraction (Codeforces 1673A)
Tags: Greedy, games

Alice and Bob are playing a game with strings. There will be $$$t$$$ rounds in the game. In each round, there will be a string $$$s$$$ consisting of lowercase English letters. Alice moves first and both the players take alternate turns. Alice is allowed to remove any substring of even length (possibly empty) and Bob is allowed to remove any substring of odd length from $$$s$$$.More formally, if there was a string $$$s = s_1s_2 \ldots s_k$$$ the player can choose a substring $$$s_ls_{l+1} \ldots s_{r-1}s_r$$$ with length of corresponding parity and remove it. After that the string will become $$$s = s_1 \ldots s_{l-1}s_{r+1} \ldots s_k$$$.After the string becomes empty, the round ends and each player calculates his/her score for this round. The score of a player is the sum of values of all characters removed by him/her. The value of $$$\texttt{a}$$$ is $$$1$$$, the value of $$$\texttt{b}$$$ is $$$2$$$, the value of $$$\texttt{c}$$$ is $$$3$$$, $$$\ldots$$$, and the value of $$$\texttt{z}$$$ is $$$26$$$. The player with higher score wins the round. For each round, determine the winner and the difference between winner's and loser's scores. Assume that both players play optimally to maximize their score. It can be proved that a draw is impossible.

Input: The first line of input contains a single integer $$$t$$$ ($$$1\leq t\leq 5\cdot 10^4$$$) denoting the number of rounds.Each of the next $$$t$$$ lines contain a single string $$$s$$$ ($$$1\leq |s|\leq 2\cdot 10^5$$$) consisting of lowercase English letters, denoting the string used for the round. Here $$$|s|$$$ denotes the length of the string $$$s$$$.It is guaranteed that the sum of $$$|s|$$$ over all rounds does not exceed $$$2\cdot 10^5$$$.

Output: For each round, print a single line containing a string and an integer. If Alice wins the round, the string must be "Alice". If Bob wins the round, the string must be "Bob". The integer must be the difference between their scores assuming both players play optimally.

Note: For the first round, $$$\texttt{"aba"}\xrightarrow{\texttt{Alice}}\texttt{"}{\color{red}{\texttt{ab}}}\texttt{a"}\xrightarrow{} \texttt{"a"}\xrightarrow{\texttt{Bob}}\texttt{"}{\color{red}{\texttt{a}}}\texttt{"}\xrightarrow{}\texttt{""}$$$. Alice's total score is $$$1+2=3$$$. Bob's total score is $$$1$$$.For the second round, $$$\texttt{"abc"}\xrightarrow{\texttt{Alice}}\texttt{"a}{\color{red}{\texttt{bc}}}\texttt{"}\xrightarrow{} \texttt{"a"}\xrightarrow{\texttt{Bob}}\texttt{"}{\color{red}{\texttt{a}}}\texttt{"}\xrightarrow{}\texttt{""}$$$. Alice's total score is $$$2+3=5$$$. Bob's total score is $$$1$$$.For the third round, $$$\texttt{"cba"}\xrightarrow{\texttt{Alice}}\texttt{"}{\color{red}{\texttt{cb}}}\texttt{a"}\xrightarrow{} \texttt{"a"}\xrightarrow{\texttt{Bob}}\texttt{"}{\color{red}{\texttt{a}}}\texttt{"}\xrightarrow{}\texttt{""}$$$. Alice's total score is $$$3+2=5$$$. Bob's total score is $$$1$$$.For the fourth round, $$$\texttt{"n"}\xrightarrow{\texttt{Alice}}\texttt{"n"}\xrightarrow{} \texttt{"n"}\xrightarrow{\texttt{Bob}}\texttt{"}{\color{red}{\texttt{n}}}\texttt{"}\xrightarrow{}\texttt{""}$$$. Alice's total score is $$$0$$$. Bob's total score is $$$14$$$.For the fifth round, $$$\texttt{"codeforces"}\xrightarrow{\texttt{Alice}}\texttt{"}{\color{red}{\texttt{codeforces}}}\texttt{"}\xrightarrow{} \texttt{""}$$$. Alice's total score is $$$3+15+4+5+6+15+18+3+5+19=93$$$. Bob's total score is $$$0$$$.

Sample Inputs:
5
aba
abc
cba
n
codeforces

Sample Outputs:
Alice 2
Alice 4
Alice 4
Bob 14
Alice 93

Solution (Python):
""""""

def i():
    s = input()
    c = {}
    tp = 0
    if len(s) % 2:
        tp -= (ord(min(s[0], s[-1])) - 96) * 2
    for x in s:
        if x in c:
            c[x] += 1
        else:
            c[x] = 1
    for x in c.keys():
        tp += (ord(x) - 96) * c[x]
    if tp > 0:
        return f'Alice {tp}\n'
    return f'Bob {abs(tp)}\n'
t = int(input())
a = []
for _ in range(t):
    a.append(i())
print(''.join(a), end='')

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from collections import Counter
import math

def score(s):
    cnt = 0
    for n in s:
        cnt += ord(n) - ord('a') + 1
    return cnt

def solve(case, s):
    if len(s) % 2 == 0:
        ans = score(s)
        res = 'Alice ' + str(ans)
    elif len(s) == 1:
        ans = score(s)
        res = 'Bob ' + str(ans)
    else:
        if ord(s[0]) > ord(s[-1]):
            ans = score(s[:-1]) - score(s[-1])
        else:
            ans = score(s[1:]) - score(s[0])
        res = 'Alice ' + str(ans)
    print(res)

def main():
    for i in range(int(input())):
        s1 = input()
        solve(i, s1)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
import sys

def get_ints():
    return map(int, sys.stdin.readline().strip().split())

def get_list():
    return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
    return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
    return sys.stdin.readline().strip()

def get_int():
    return int(sys.stdin.readline().strip())

def get_print_int(x):
    sys.stdout.write(str(x) + '\n')

def get_print(x):
    sys.stdout.write(x + '\n')

def get_print_int_same(x):
    sys.stdout.write(str(x) + ' ')

def get_print_same(x):
    sys.stdout.write(x + ' ')

def solve():
    for _ in range(get_int()):
        s = get_string()
        n = len(s)
        summ = 0
        for i in s:
            summ += ord(i) - ord('a') + 1
        if n % 2 == 0:
            get_print('Alice {}'.format(summ))
        else:
            a1 = summ - (ord(s[0]) - ord('a') + 1)
            a2 = summ - (ord(s[-1]) - ord('a') + 1)
            b1 = summ - a1
            b2 = summ - a2
            if a1 > b1 and a2 > b2:
                get_print('Alice {}'.format(max(a1 - b1, a2 - b2)))
            elif a1 > b1:
                get_print('Alice {}'.format(a1 - b1))
            elif a2 > b2:
                get_print('Alice {}'.format(a2 - b2))
            else:
                get_print('Bob {}'.format(min(b1 - a1, b2 - a2)))
solve()