PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: gunpoint_88
Tester: jay_1048576
Preparer & Editorialist: iceknight1093
DIFFICULTY:
3262
PREREQUISITES:
The minimax algorithm.
PROBLEM:
There is a strip of N cells, some empty and some blocked.
Alice and Bob play a game, with Alice starting first.
On their turn, a player does the following:
- Choose K contiguous empty cells on the strip, and place dominoes on these K cells.
- A domino placed on turn T will disappear at the start of turn T+D.
A player who cannot make a move loses.
Find out the winner with optimal play; or whether the game will go on infinitely.
EXPLANATION:
As a first observation, note that if the game hasn’t finished by the end of the D-th turn (under optimal play), it will go on forever.
This is because, on the (D+i)-th turn, the dominos placed on the i-th turn will disappear; so the current player will always have a move to make.
This means we can discard the ‘disappearing’ part entirely, and just work with placing normal dominoes.
The ‘normal’ game will, of course, have a unique winner — and obviously, this person is the only one who has a chance of winning the disappearing game as well.
We only need to check at the end whether the winner can force a win in \lt D moves; if they can’t, it’s a draw.
This also tells us what each player’s strategy is.
Suppose Alice wins the normal game. Then,
- Alice will make a move that allows her to force a victory in the minimum number of moves.
- Bob will make a move that allows him to prolong the game as much as possible; in an attempt to reach a draw.
If Bob wins, the roles reverse.
Together, this tells us the two pieces of information we need to know:
- Who the winner of the normal game is; and
- The least number of moves they need to obtain victory.
Both of these can be found using dynamic programming.
Each state of the strip can be represented using N-bit bitmasks.
We will compute the following pieces of information for each bitmask:
- \text{winner}[mask], which is a boolean value.
A value of 1 orTruemeans that the person who plays first on this mask will win it; while a value of 0 orFalsemeans that the person going second wins.
A mask will be called a winning state if \text{winner}[mask] = 1, and a losing state otherwise. - \text{time}[mask], which is the ‘optimal’ number of turns for this mask for the first player.
That means the following:- If \text{winner}[mask] = 1, the \text{time}[mask] is the minimum time needed for victory.
- Otherwise, \text{time}[mask] is the maximum amount of time the game can be prolonged for.
These values can be computed as follows:
- If no moves can be made from mask, then \text{winner}[mask] = 0 and \text{time}[mask] = 0.
- Otherwise, let S_{mask} be the set of states that can be reached from mask by making exactly one move.
If S_{mask} contains any losing state, then \text{winner}[mask] = 1; otherwise \text{winner}[mask] = 0. - If \text{winner}[mask] = 0, then \text{time}[mask] = 1 + \max(\text{time}[nxt]) across all nxt\in S_{mask}.
That is, if the current state is losing, then the player will choose to make a move such that the opponent needs as many possible moves to win. - If \text{winner}[mask] = 1, then \text{time}[mask] = 1 + \min(\text{time}[nxt]) across all nxt \in S_{mask}, such that \text{winner}[nxt] = 0.
That is, if the current state is winning, the player will choose to make a move such that they can win in as little time as possible; while also ensuring that they move to a losing state before passing the turn.
If the \text{winner} and \text{time} values are memoized, performing the above computations recursively is enough to solve the problem.
However, a little care is needed with implementation.
In particular, you might notice that there are technically 2^N possible bitmasks; and for N = 30 we certainly can’t compute the answers for them all quickly enough.
However, in most cases, the set of bitmasks that are actually reachable is generally much smaller because we place multiple dominoes at the same time.
For example, with N = 30, K = 2 and a completely empty starting strip, the real number of reachable states is only slightly more than 10^6 which is very manageable.
The only outlier is if K = 1, in which case every mask can indeed be reached since we place dominoes one at a time.
However, K = 1 can be handled separately: if there are \geq D empty spaces, the game is a draw; otherwise the winner is decided uniquely by the parity of the number of empty cells (Alice if odd, Bob if even).
For K \geq 2, recursively processing all reachable bitmasks and using a hashmap for memoization is good enough to get AC.
TIME COMPLEXITY
About 10^7 hashset/hashmap operations, in the worst case.
CODE:
Tester's code (C++)
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007
unordered_map<int,int> dp;
vector<int> next_states(int state,int n,int k)
{
int mask = (1<<k)-1;
vector<int> states;
for(int i=0;i<=n-k;i++)
if((state&(mask<<i))==0)
states.push_back(state|(mask<<i));
return states;
}
int endstate(int state,bool player,int n,int k,int d)
{
if(d==0)
return 0;
int mask = (1<<k)-1;
bool ended = true;
for(int i=0;i<=n-k;i++)
if((state&(mask<<i))==0)
ended = false;
if(ended)
{
if(player)
return -1;
else
return 1;
}
else
return 2;
}
string binary(int x)
{
string s = "";
while(x>0)
{
s=s+(char)('0'+x%2);
x/=2;
}
while(s.length()<30)
s+='0';
reverse(s.begin(),s.end());
return s;
}
int minimax(int state,bool player,int n,int k,int d)
{
if(dp.find(state)!=dp.end())
return dp[state];
int es = endstate(state,player,n,k,d);
if(es!=2)
return dp[state]=es;
vector<int> states = next_states(state,n,k);
int res;
if(player)
{
res=-1;
for(auto i:states)
res = max(res,minimax(i,0,n,k,d-1));
}
else
{
res=1;
for(auto i:states)
res = min(res,minimax(i,1,n,k,d-1));
}
return dp[state]=res;
}
void solve(int tc)
{
int n,k,d;
cin >> n >> k >> d;
string s;
cin >> s;
int state=0,c=0;
for(int i=0;i<n;i++)
{
if(s[i]=='1')
{
c++;
state|=(1<<i);
}
}
if(k==1)
{
if(d+c<=n)
cout << "Draw\n";
else if((n-c)%2==0)
cout << "Bob\n";
else
cout << "Alice\n";
return;
}
int ans = minimax(state,1,n,k,min(d,n+1));
if(ans==1)
cout << "Alice\n";
else if(ans==0)
cout << "Draw\n";
else
cout << "Bob\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc=1;
// cin >> tc;
for(int ttc=1;ttc<=tc;ttc++)
solve(ttc);
return 0;
}
Editorialist's code (Python)
def gen(mask, dp):
if mask in dp:
return dp[mask]
ret = [0, 0]
mn = float('inf')
mx = 0
add = filler
while add <= lim:
if (mask & add) == 0:
get = gen(mask | add, dp)
ret[0] |= get[0] ^ 1
if get[0]:
mx = max(mx, get[1] + 1)
else:
mn = min(mn, get[1] + 1)
add *= 2
if ret[0]:
ret[1] = mn
else:
ret[1] = mx
dp[mask] = ret
return ret
n, k, d = map(int, input().split())
s = input()
if k == 1:
empty = s.count('0')
if empty < d:
if empty % 2 == 0:
print("Bob")
else:
print("Alice")
else:
print("Draw")
exit()
basemask = 0
for i in range(n):
basemask |= int(s[i]) << i
lim = (1 << n)
filler = (1 << k) - 1
dp = {}
ans = gen(basemask, dp)
if ans[0] == 0: # Bob
if ans[1] < d:
print("Bob")
else:
print("Draw")
else: # Alice
if ans[1] < d:
print("Alice")
else:
print("Draw")