10837. Pebble
This summer, Antun and Branka discovered an
unusual beach, entirely covered with plastic pebbles washed ashore from
containers that had fallen off cargo ships. They decided to take n of
these pebbles with them: some red and some blue.
In autumn, while reminiscing about the warm
days, Antun and Branka invented a game with these pebbles. At the beginning,
they arrange all n pebbles in a row. Then the players take turns: on
each move, a player must remove one pebble from either end of the row. The
player who first collects k red pebbles loses
the game. Antun always makes the first move, and he wonders: can he guarantee
victory regardless of Branka's moves? Your task is to help him answer this
question.
Input. The first line contains two integers n and k (1 ≤ k < n ≤ 350).
The second line contains a sequence of n characters C or P, where C denotes a red pebble and P denotes
a blue pebble. It is guaranteed that the character C appears
at least 2 * k – 1 times.
Output. Print “DA” if Antun can win regardless of Branka’s
moves, and “NE” otherwise.
|
Sample
input 1 |
Sample
output 1 |
|
4 1 CCCP |
DA |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
8 2 PCPPCCCC |
DA |
|
|
|
|
Sample
input 3 |
Sample
output 3 |
|
9 1 PPCPPCPPC |
NE |
dynamic programming
Since the symbol C appears at least 2 * 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 red stones. That would mean the total
number of red stones in the game is at most 2k – 2, which contradicts the given condition.
Let’s construct a prefix array in
order to quickly determine the number of red stones on any subsegment [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] 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 uk red stones.
·
The function returns 1 if Antun can
guarantee a win from this position; otherwise, it returns 0.
Game termination
conditions:
·
If uk >= 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) or from the
right moving to (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
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 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;
·
red_left – the number of red stones in the
current interval [l, r];
·
total_red – red_left – uk = the number
of red stones that will remain for the opponent (Branka), given that Antun has
already collected uk.
Thus,
the game is reduced to a recursive dynamic programming problem with three
parameters:
·
(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:
·
prefix – the prefix sums of red stones.
·
dp – 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 uk
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 red_left are in the interval [l, r];
Compute
how many red stones total_red – red_left – uk will remain for the
opponent (Branka / Antun), given that Antun / Branka has already collected uk.
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
uk >= 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)
or from the right (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;
}
The main part of the program. Read the input data.
memset(dp, -1, sizeof(dp));
cin >> n >> k;
cin >> str;
Compute the prefix array prefix.
·
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;