Engineer bro!
Wed Nov 17 2021 (2 years ago)
Engineer by mistake!
I am a software engineer by passion
In this article, you'll learn that how can you use DP to reduce the execution time.
Alice and Bob take turns playing a game, with Alice starting first.
Initially, there is a number n on the chalkboard. On each player's turn, that player makes a move consisting of:
Choosing any with and .
Replacing the number n on the chalkboard with n - x.
Also, if a player cannot make a move, they lose the game.
Return true
if and only if Alice wins the game, assuming both players play optimally.
Input: n = 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.
Input: n = 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.
Suppose you have a number . As per the problem description, Alice will start playing first. For , there is no x such that (), hence Alice will lose the game.
Suppose, you have a number . First, Alice can choose and make . Now, Bob has and he can not make any move. So, Bob lose the game.
Suppose, you have a number . This time Alice can choose either or . Now the real DP game begains
.
When you see the above image, then you can see at each level either Alice or Bob is present.
Steps
Alice started the game, now he can choose either 1 or 2
Alice chooses 1
and it's Bob's turn. He can choose 1 and n becomes 2
and it's Alice's turn. He can choose 1 and n becomes 1
and it's Bob's turn. He can not choose any x and Bob loses the game
Alice chooses 2
and it's Bob's turn. He can choose 1 and n becomes 1
and it's Alice's turn. He can not choose any x, so he loses the game.
You can observe that initially if Alice were not played optimally and choose 2 then Alice would have to lose.
From the above explanation, you can see that at each step you have to make a decision. The decision should be optimal, so the current player wins the game.
You are given a number and you have to return true
if Alice will win the game or false
.
Alice can win the game if and only if there is a possibility where can Bob loses the game.
Let's is a set of number which can divide and .
Now, (for each x of set X), check if Alice is going to win or not
Do the same thing
Implementation
bool wins(int n){
// if a player has 1, then he/she can not make any move
if(n==1)
return false;
// if a player has 2, then he/she can make it 1 and opponent will lose the game
if(n==2)
return true;
for(int i=1; i<n; i++){
// !wins(n-x) -> if opponent will lose the game then current player will win
if(n%i == 0 && !wins(n-x))
return true;
}
return false;
}
At each step, every we are creating subtrees, where is the number of divisions of .
So, the time complexity would be exponential.
You can see in the above image, while creating left subtree we are processing . The same is being processed while generating the right subtree.
So, we can remember the previous value of to get rid of calculating it again.
Rest of the explanation can be found in the code
class Solution {
public:
bool divisorGame(int n) {
if(n==1)
return false;
vector<int>wins(n+1,-1);
wins[1] = 0;
wins[2] = 1;
return meWins(n,wins);
}
bool meWins(int n, vector<int>&wins){
// the maximum number which can devide n can be either sqrt(n) or less than sqrt(n)
int sq = ceil(sqrt(n));
for(int i=1; i<=sq; i++){
// if i can not divide n, then don't do anything
if(n%i != 0){
continue;
}
// if the current subtree value is not present into wins, then call the function again
if(wins[n-i] == -1){
meWins(n-i, wins);
continue;
}
// if next player is going to loose, then current is going to win
if(!wins[n-i]){
wins[n-i] = 1;
return true;
}
}
// this player can't not win
wins[n-1] = 0;
return false;
}
};
© 2021 dsabyte. All rights reserved