Game With String (Codeforces 1221E)
Tags: Others, games

Alice and Bob play a game. Initially they have a string $$$s_1, s_2, \dots, s_n$$$, consisting of only characters . and X. They take alternating turns, and Alice is moving first. During each turn, the player has to select a contiguous substring consisting only of characters . and replaces each of them with X. Alice must select a substing of length $$$a$$$, and Bob must select a substring of length $$$b$$$. It is guaranteed that $$$a > b$$$.For example, if $$$s =$$$ ...X.. and $$$a = 3$$$, $$$b = 2$$$, then after Alice's move string can turn only into XXXX... And if it's Bob's turn and the string $$$s =$$$ ...X.., then after Bob's move the string can turn into XX.X.., .XXX.. or ...XXX.Whoever is unable to make a move, loses. You have to determine who wins if they both play optimally.You have to answer $$$q$$$ independent queries.

Input: The first line contains one integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.The first line of each query contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le b < a \le 3 \cdot 10^5$$$).The second line of each query contains the string $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$), consisting of only characters . and X.It is guaranteed that sum of all $$$|s|$$$ over all queries not exceed $$$3 \cdot 10^5$$$.

Output: For each test case print YES if Alice can win and NO otherwise.You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

Note: In the first query Alice can select substring $$$s_3 \dots s_5$$$. After that $$$s$$$ turns into XXXXX...XX...X. After that, no matter what move Bob makes, Alice can make the move (this will be her second move), but Bob can't make his second move.In the second query Alice can not win because she cannot even make one move.In the third query Alice can choose substring $$$s_2 \dots s_6$$$. After that $$$s$$$ turns into .XXXXX.X..X, and Bob can't make a move after that.

Sample Inputs:
3
3 2
XX......XX...X
4 2
X...X.X..X
5 3
.......X..X

Sample Outputs:
YES
NO
YES

Solution (Python):
def sol():
    (a, b) = map(int, input().split())
    s = input().replace('X', ' ')
    small_segs = 0
    critical_region = -1
    for p in map(len, s.split()):
        if p < b:
            continue
        if p < a and p >= b:
            return False
        if (p - a) % 2 == 0 and p >= a + 4 * b or ((p - a) % 2 == 1 and p >= a + 4 * b - 1):
            return False
        if p >= 2 * b:
            if critical_region != -1:
                return False
            critical_region = p
        elif p >= a:
            small_segs += 1
    if critical_region == -1:
        return small_segs % 2 == 1
    can = [0] * 3
    for l in range(critical_region + 1 - a):
        r = critical_region - l - a
        if l >= b and l < a or l >= 2 * b:
            continue
        if r >= b and r < a or r >= 2 * b:
            continue
        canl = int(l >= a)
        canr = int(r >= a)
        can[canl + canr] = 1
    for (choice, val) in enumerate(can):
        if val and (small_segs + choice) % 2 == 0:
            return True
    return False
n = int(input())
for _ in range(n):
    print('YES' if sol() else 'NO')

Solution (Python):
def sol():
    (a, b) = map(int, input().split())
    s = input().replace('X', ' ')
    small_segs = 0
    critical_region = -1
    for p in map(len, s.split()):
        if p < b:
            continue
        if p < a and p >= b:
            return False
        if (p - a) % 2 == 0 and p >= a + 4 * b or ((p - a) % 2 == 1 and p >= a + 4 * b - 1):
            return False
        if p >= 2 * b:
            if critical_region != -1:
                return False
            critical_region = p
        elif p >= a:
            small_segs += 1
    if critical_region == -1:
        return small_segs % 2 == 1
    can = [0] * 3
    for l in range(critical_region + 1 - a):
        r = critical_region - l - a
        if l >= b and l < a or l >= 2 * b:
            continue
        if r >= b and r < a or r >= 2 * b:
            continue
        canl = int(l >= a)
        canr = int(r >= a)
        can[canl + canr] = 1
    for (choice, val) in enumerate(can):
        if val and (small_segs + choice) % 2 == 0:
            return True
    return False
n = int(input())
for _ in range(n):
    print('YES' if sol() else 'NO')

Solution (Python):
def removeX(s, p):
    if p == len(s):
        return s
    while s[p] != 'X':
        p += 1
        if p == len(s):
            return s
    j = 0
    while s[p + j] == 'X':
        j += 1
        if p + j == len(s):
            break
    return removeX(s[0:p + 1] + s[p + j:], p + 1)

def doable(lenght, a, b, parity):
    for x in range((lenght - a) // 2 + 1):
        y = lenght - a - x
        if (not (x >= b) & (x < a)) & (not x >= 2 * b) & (not (y >= b) & (y < a)) & (not y >= 2 * b):
            e = 0
            if (x >= a) & (x < 2 * b):
                e += 1
            if (y >= a) & (y < 2 * b):
                e += 1
            if (parity + e) % 2 == 0:
                return 1
    return 0
for i in range(int(input())):
    (a, b) = [int(x) for x in input().split()]
    v = [0, 0, 0]
    s = removeX(input(), 0)
    for y in s.split('X'):
        k = len(y)
        if (k >= b) & (k < a):
            v[0] += 1
        elif (k >= a) & (k < 2 * b):
            v[1] += 1
        elif k >= 2 * b:
            v[2] += 1
            lenght = k
    if (v[0] > 0) | (v[2] > 1):
        print('NO')
    elif v[2] == 1:
        if lenght - a >= 4 * b:
            print('NO')
        elif doable(lenght, a, b, v[1] % 2) == 1:
            print('YES')
        else:
            print('NO')
    elif v[1] % 2 == 0:
        print('NO')
    else:
        print('YES')