Educational Codeforces 73 E. Game With String

https://codeforces.com/contest/1221/standings

First, if there is a segment whose length x is B <= x < A, the second player always wins. That's why the number of possible movements of the second player is always larger than the first player if the second player moves optimally. This is a really important property, so it appears again and again.

Second, if there are two or more segments whose length x is 2B, the second player always wins. The optimal movement of the second player is to make segment of length B.

One of the simplest situation is all segments belong to the group [A,2*B) the winner is decided by the parity of the its number. Last, we consider the situation that the only single segment belongs to the group [2*B,inf) and the others belong to the group [A,2*B). Let c be the number of segments [A,2*B) and v denotes the length of the segment of [2*B,inf). If c is even, the first player should split v into [0,B) and [0,B) or [A,2*B) and [A,2*B). In the both cases, we should divide the segment equally. Next, consider the case that c is odd. In this case, the first player should split v into [0,B) and [A,2*B). Let x be the length of the part of [0,B) and y be the length of the part of [A,2*B). The analysis of this case is a little difficult without algebra.

List the conditions x and y must follows.

\begin{gather}
x+y+A = v,\\
0 \le x < B, \\
A \le y < 2B
\end{gather}

We then have

\begin{gather}
0 \le x \lt B, \\
- 2B + v - A \lt x \le - 2 A + v.
\end{gather}

We now have all pieces to solve this problem. All we have to do is to implement conditions described above.

#include <bits/stdc++.h>
 
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()
 
using namespace std;
using ll = long long;
 
bool overlap(int a, int b, int c, int d) {
  return max(a, c) <= min(b, d);
}
 
bool solve() {
  int A, B; cin >> A >> B;
  string S; cin >> S;
  const int N = S.size();
  vector<int> val;
  for (int i = 0; i < N;) {
    if (S[i] == 'X') {
      i++;
      continue;
    }
    int j = i;
    while (i < N && S[i] == '.') i++;
    if (i - j >= B) {
      if (i - j < A) return false;
      val.push_back(i - j);
    }
  }
  int cnt = 0;
  for (int x : val) cnt += x >= 2 * B;
  if (cnt >= 2) return false;
  int v = 0;
  for (int x : val) if (x >= 2 * B) v = x;
  int l = (v - A) / 2;
  int r = (v - A + 1) / 2;
  if (r < B && val.size() % 2 == 1) return true;
  if (A <= l && l < 2*B && A <= r && r < 2*B && val.size() % 2 == 1) return true;
  if (val.size() % 2 == 0 & overlap(0, B-1, -A-2*B+1+v, -2*A+v)) return true;
  return false;
}
 
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int Q; cin >> Q;
  while (Q--) {
    cout << (solve() ? "YES" : "NO") << '\n';
  }
}