Pebble#10837

Pebble (Editorial)

Since the symbol $C$ appears at least $2 \cdot k - 1$ 2 \cdot k - 1 times, the game will necessarily end in a win. The game would not end in a win only if each participant had at most $k - 1$ k - 1 red stones. That would mean the total number of red stones in the game is at most $2 k - 2$ 2k - 2, which contradicts the given condition.

Let's construct a $p r e f i x$ prefix array in order to quickly determine the number of red stones on any subsegment $[l, r]$ [l, r]:

prefix[0] = (str[0] == 'C')
prefix[i] = prefix[i-1] + (str[i] == 'C')

Then the number of red stones on the subsegment $[l, r]$ [l, r] can be computed in $O (1)$ time:

red_left = prefix[r];
if (l) red_left -= prefix[l-1];

Consider the following function:

int can_win(int l, int r, int uk)

It is currently Antun's turn (the first player).
The current subsegment of stones is from index $l$ to $r$ .
Antun already has $u k$ red stones.
The function returns $1$ if Antun can guarantee a win from this position; otherwise, it returns $0$ .

Game termination conditions:

If $u k \geq k$ uk \ge k, then Antun has already collected $k$ red stones, which means he loses.
If Branka is guaranteed to collect $k$ red stones, then Antun wins.

The players take turns making moves:

Antun can take a stone from the left moving to $(l + 1)$ (l + 1) or from the right moving to $(r - 1)$ (r - 1).
In order for Antun to guarantee a win, at least one of his moves must lead to a position in which Branka does not have a winning strategy.

if (!can_win(l + 1, r, other_red) || !can_win(l, r - 1, other_red))
  res = 1;
else
  res = 0;

Here $o t h er_r e d$ other\_red is the number of red stones that Branka will accumulate. In other words, we model the situation as: "I make a move, then the opponent makes a move". If there exists at least one move after which the opponent is not guaranteed to win, then Antun wins.

The value of $o t h er_r e d$ other\_red is computed as follows:

int total_red = prefix[n - 1]; // total number of red stones in the string
int red_left = prefix[r];    // number of red stones up to position r
if (l) red_left -= prefix[l - 1]; // number of red stones in [l, r]
int other_red = total_red - red_left - uk;

$r e d_l e f t$ red\_left — the number of red stones in the current interval $[l, r]$ [l, r];
$t o t a l_r e d - r e d_l e f t - u k$ total\_red - red\_left - uk = the number of red stones that will remain for the opponent (Branka), given that Antun has already collected $u k$ .

Thus, the game is reduced to a recursive dynamic programming problem with three parameters:

$(l, r, u k)$ (l, r, uk) — the current subsegment and the number of red stones collected by Antun.

Call the function and print the result:

if (can_win(0, n - 1, 0))
  puts("DA");  // Antun can guarantee a win
else
  puts("NE");  // no

Algorithm implementation

Let us declare the following arrays:

$p r e f i x$ prefix — the prefix sums of red stones.
$d p$ — the memoization table for the dynamic programming solution of the game.

#define MAX 352
int prefix[MAX], dp[MAX][MAX][MAX];

The function can_win returns $1$ , if the current player (Antun or Branka) can guarantee a win from this position; otherwise, it returns $0$ .

It is currently Antun's / Branka's turn.
The current subsegment of stones is from $l$ to $r$ .
Antun / Branka already has $u k$ red stones.

int can_win(int l, int r, int uk)
{
  int& res = dp[l][r][uk];

If the value of the function has not been computed yet.

  if (res == -1)
  {

Compute how many red stones $r e d_l e f t$ red\_left are in the interval $[l, r]$ [l, r];

Compute how many red stones $t o t a l_r e d - r e d_l e f t - u k$ total\_red - red\_left - uk will remain for the opponent (Branka / Antun), given that Antun / Branka has already collected $u k$ .

    int total_red = prefix[n - 1];
    int red_left = prefix[r];
    if (l) red_left -= prefix[l - 1];
    int other_red = total_red - red_left - uk;

If $u k \geq k$ uk \ge k, then Antun / Branka has already collected $k$ red stones, which means he /she loses.

    if (uk >= k)
      res = 0;

If Branka / Antun is guaranteed to collect $k$ red stones, then Antun / Branka wins.

    else if (other_red >= k)
      res = 1;
    else
    {

Antun / Branka can take a stone from the left $(l + 1)$ (l + 1) or from the right $(r - 1)$ (r - 1). In order for Antun to guarantee a win, at least one of his moves must lead to a position in which Branka / Antun does not have a winning strategy.

      if (!can_win(l + 1, r, other_red) || 
          !can_win(l, r - 1, other_red))
        res = 1;
      else
        res = 0;
    }
  }
  return res;
}

C++

The main part of the program. Read the input data.

memset(dp, -1, sizeof(dp));
cin >> n >> k;
cin >> str;

Compute the prefix array $p r e f i x$ prefix.

$p r e f i x [i]$ prefix[i] contains the number of red stones in positions from $0$ to $i$ inclusive.

prefix[0] = (str[0] == 'C');
for (i = 1; i < n; i++) prefix[i] = prefix[i - 1] + (str[i] == 'C');

Call the function and print the result.

if (can_win(0, n - 1, 0))
  cout << "DA" << endl;
else
  cout << "NE" << endl;