Really good point. I think i missed that because leetcode will accept any solution that evaluates to "true" in this case lol. I think the simplest fix would be to change the max() function to min() for ONLY when Bob is choosing. When Alice chooses it stays max(). Correct me if i'm missing something tho..
@@NeetCode yeah, as long as minimizing Alice means maximizing Bob, which I believe is true since it's a zero sum game? And I couldn't figure out your even odd formula so I just put in another boolean parameter to toggle between Alice and bob
Alice is to pick first so she can decide to pick all the odds or all the even. Pick left for odd and pick right for even. The rest can just follow Bob, if Bob pick left she pick left, if Bob pick right she pick right. So she only need to calculate if sum(odd) > sum(even).
i feel like with the sum(even) !- sum(odd) we just overcomplicate the return True aspect. If the basis of the problem is that Alice can try every combination, winning combinations are a subset of all the combinations, hence Alice is always winning.
I couldn't do the Stone Game ii in daily challenge. So I came to review the Stone Game. And This is literally the best intuitive explanation that was ever possible. I look up to you man!
INCORRECT SOLUTION!!! You can try with this array [5, 2, 100, 6] You defined dfs(l, r) as what alice will get at the end of the game. It should be 105. But running through your code, we will get 106 instead. I think your solution is just greedily looking for max returns.
I saw this Neetcode's reply in one of the comments.. and I think it fixes the problem, @NeetCode I think the simplest fix would be to change the max() function to min() for ONLY when Bob is choosing. When Alice chooses it stays max(). Correct me if i'm missing something tho.. Here's the implementation, class Solution: def stoneGame(self, piles: List[int]) -> bool: dp = {}
def dfs(l, r): if l > r: return 0 if (l,r) in dp: return dp[(l,r)] even = True if (r-l)%2 else False left = piles[l] if even else 0 right = piles[r] if even else 0 # in bob's turn, minimize alice's score if left == 0 and right == 0: dp[(l,r)] = min(dfs(l+1, r), dfs(l, r-1)) return dp[(l,r)] dp[(l,r)] = max(dfs(l+1, r) + left, dfs(l, r-1)+right) return dp[(l,r)] aliceMaxScore = dfs(0, len(piles)-1) return aliceMaxScore > sum(piles)//2
I have a doubt. consider the leetcode example [5,3,4,5]. Alice should start first . As per your code, even is True when (l-i)%2==0. When the game starts, i=0 , l= len(A)-1=3 . (3-0) is odd, so even gets False, which means Bob is going for turn 1. Could you please explain my confusion?
for once, i think your solution is not exactly correct. You can try with this array [5, 2, 100, 6] You defined dfs(l, r) as what alice will get at the end of the game. By inspection, it should be 105. But running through your code, we will get 106 instead. I think your solution is just greedily looking for max returns, but happen to be ok for leetcode as they are only asking for true/false. (its always true) Please double check !! I think the right solution should be considering Alice and Bob turn to be min-max problem.
Hi buddy. Very great explaining the DP solution. But seems like your DFS function just returns the max value of Alice choice. We implicitly understand based on the restrictions of this problem Alice always win, but for extensions any idea how can we compare Alice's max choice value and Bob's?
Awesome video my dude, it takes me a bit to get the idea of the code, Roy Tushar video of bottom up visualization is a good compliment with this solution
I don't get it why we are narrowing the choices between first + third, second + fourth piles. It says Alice will always pick third one if she picks first pile initially. Pile 1, 2, 3 , 4. Alice can pick first pile. Say Bob picks fourth pile. Alice can pick second pile at the next turn. So it is first+second for Alice.
Hey, I came up with this code before I saw your video. Can you elaborate if this is incorrect or suboptimal? class Solution: def stoneGame(self, piles: List[int]) -> bool: resA, resB = 0, 0 l, r = 0, len(piles)-1 i = 0 while l piles[r]: resA += piles[l] l += 1 else: resA += piles[r] r -= 1 else: if piles[l] > piles[r]: resB += piles[l] l += 1 else: resB += piles[r] r -= 1 return True if resA > resB else False Thankyou :)
I have a doubt if it is bob and max(dfs(l+1,r),dfs(l,r-1) means bob if choosing such a way alex get max no of piles but bob should such that alex stones should be minimized...im confused
This question is flawed so result verification cannot identify bugs. However, I think the solution presented is also flawed, because Bob does not make any choice at all. This is because *left* and *right* are going to be 0 for Bob and the *max()* expression is just going to channel Alice's next choice. If Bob did not make a choice, then you can't tell what Alice would be left with to pick from. Also, *even* is incorrectly calculated, should be *l - r + 1* A better approach is to have dfs() return a tuple of (player1, player2) sum, but then alternate every dfs call to a different player making the choice. In this way, you do give Bob a choice to pick a pile.
This is not the way you solve game theory . You could have introduced Bob's role of selecting maximum for himself and leaving Alice the minimum... This shows the wrong answer dude.. anyways appreciate your content
What if Alice wins only if Bob has less value? In your code you are only computing the maximal value Alice can obtain. How can you know if she obtained more than Bob?
1.create a dictionary 2. iterate throught your input array 3. if the element is not present in dictionary then assign the value as 1 4. if it's present in the dictionary then increment the value by 1 5. print all the items from the dictionary having value>1.
why are we taking only alice optimal approach here. Like we are finding all the approaches in which alice can find asnwer and then we are just getting max of it. I get it but why not also take bobs optimal approach.
Hi NeetCode, I think there is a flaw in the logic of your dynamic programming approach. Your current approach seems to always return the highest possible choice between: a) piles[left] + dfs(left + 1, right) b) piles[right] + dfs(left, right - 1) However, you always add 0 if it is Bob's turn. In reality, we should be adding the value from piles[left/right] to Bob's score (or subtracting the value from piles[left/right] from a score that's shared between Alice and Bob) instead of adding zero to the score. Otherwise, when we add 0 to the score, it's as if we skipped this index entirely and ignored Bob's turn. Your solution is always going to be accepted under the current constraints of the problem because Alice will always win, but in a situation where it was actually possible for Bob to win, Bob would never win because we always ignore values from piles when it's his turn. For instance, if the problem wasn't only limited to even lengths and we had the following input: piles = {1,4,2} Your solution will say that Alice should win, but in reality it should be Bob who wins. I think a correct approach to this problem which accounts for the possibility that Bob could win would look something like this: leetcode.com/problems/stone-game/solutions/4219547/readable-top-down-dp-solution-with-explanation/
We can create a 2D array, which is L * R size. When l = r, means there is only one pile to choose. So dp[L][R] should be same as the piles When L > R, non sense When L < R, we compute: dp = [[0] * len(piles) for _ in range(len(piles))] for i, pile in enumerate(piles): dp[i][i] = pile for l in range(len(piles) - 2, -1, -1): for r in range(l + 1, len(piles)): even = True if (r - l) % 2 else False left = piles[l] if even else 0 right = piles[r] if even else 0 dp[l][r] = max(dp[l + 1][r] + left, dp[l][r - 1] + right) return dp[0][len(piles) - 1] > (sum(piles) / 2) And the 1D array, is similar with 2D solution. Since we know the new DP is only related with dp[l + 1][r] and dp[l][r - 1]. We do not need to create a new nextDP array, you will see in the code. Then we get below: dp = piles.copy() for l in range(len(piles) - 2, -1, -1): for r in range(l + 1, len(piles)): even = True if (r - l) % 2 else False left = piles[l] if even else 0 right = piles[r] if even else 0 dp[r] = max(dp[r] + left, dp[r - 1] + right) return dp[len(piles) - 1] > (sum(piles) / 2) Actually, the graph is like a reversed triangle. And they are much more efficient.
The only way I think O(1) is possible is for even length array with odd sum. For odd length, it will fail : example 3,100,4. No matter what alice peeks, she is bound to lose
The question asks if it is possible for alice to win at least one game, here's how she can pick to win [3,100,4], say alice picks 3, and then bob picks 4, then alice picks 100, remember out of every possible way bob and alice can pick the stones, there does exist a way that alice can win Anyways what's more weird about this question is the statement "Assuming Alice and Bob play optimally" - if a DP approach considers all possibilities then one of those possibilities would include the case where alice wins which is the same as saying where bob does NOT play optimally, because he lost, that is what "optimally" means right? i.e to win?
Just letting you know you are single-handedly saving my CS career.
Adding the line " both Alice and Bob knows the content of the array" in the question would've made this easier.
That's true, leetcode problem statements can be pretty confusing at times.
For the dp solution, it seems you did not assume Bob to play optimally?
Really good point. I think i missed that because leetcode will accept any solution that evaluates to "true" in this case lol.
I think the simplest fix would be to change the max() function to min() for ONLY when Bob is choosing. When Alice chooses it stays max(). Correct me if i'm missing something tho..
@@NeetCode yeah, as long as minimizing Alice means maximizing Bob, which I believe is true since it's a zero sum game? And I couldn't figure out your even odd formula so I just put in another boolean parameter to toggle between Alice and bob
@@NeetCode a small doubt, why should it be min() and not max() for bob? he also wants to maximize his score right..? I'm confused
@@sanjanar9198
public boolean stoneGame(int[] piles) {
int[][][] dp = new int[piles.length+1][piles.length+1][2];
for(int i=1;i
@@sanjanar9198 same confuse...
Alice is to pick first so she can decide to pick all the odds or all the even. Pick left for odd and pick right for even. The rest can just follow Bob, if Bob pick left she pick left, if Bob pick right she pick right. So she only need to calculate if sum(odd) > sum(even).
LOL, so then we can basically always return true because the inputs are specially formulated so alice always wins.
even = True if (r - l + 1)%2 == 0 else False , if we are checking the widow size if it is even or not ,shouldn't it be like this ?
i feel like with the sum(even) !- sum(odd) we just overcomplicate the return True aspect.
If the basis of the problem is that Alice can try every combination, winning combinations are a subset of all the combinations, hence Alice is always winning.
I couldn't do the Stone Game ii in daily challenge. So I came to review the Stone Game. And This is literally the best intuitive explanation that was ever possible. I look up to you man!
INCORRECT SOLUTION!!!
You can try with this array [5, 2, 100, 6]
You defined dfs(l, r) as what alice will get at the end of the game. It should be 105. But running through your code, we will get 106 instead.
I think your solution is just greedily looking for max returns.
I saw this Neetcode's reply in one of the comments.. and I think it fixes the problem,
@NeetCode
I think the simplest fix would be to change the max() function to min() for ONLY when Bob is choosing. When Alice chooses it stays max(). Correct me if i'm missing something tho..
Here's the implementation,
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
dp = {}
def dfs(l, r):
if l > r:
return 0
if (l,r) in dp:
return dp[(l,r)]
even = True if (r-l)%2 else False
left = piles[l] if even else 0
right = piles[r] if even else 0
# in bob's turn, minimize alice's score
if left == 0 and right == 0:
dp[(l,r)] = min(dfs(l+1, r), dfs(l, r-1))
return dp[(l,r)]
dp[(l,r)] = max(dfs(l+1, r) + left, dfs(l, r-1)+right)
return dp[(l,r)]
aliceMaxScore = dfs(0, len(piles)-1)
return aliceMaxScore > sum(piles)//2
I have a doubt. consider the leetcode example [5,3,4,5]. Alice should start first . As per your code, even is True when (l-i)%2==0.
When the game starts, i=0 , l= len(A)-1=3 . (3-0) is odd, so even gets False, which means Bob is going for turn 1. Could you please explain my confusion?
should be (l - r + 1), I verified the results in IDE.
for once, i think your solution is not exactly correct.
You can try with this array [5, 2, 100, 6]
You defined dfs(l, r) as what alice will get at the end of the game. By inspection, it should be 105. But running through your code, we will get 106 instead.
I think your solution is just greedily looking for max returns, but happen to be ok for leetcode as they are only asking for true/false. (its always true)
Please double check !!
I think the right solution should be considering Alice and Bob turn to be min-max problem.
I agree. I think his code is working perfectly because Alice always wins but the logic is wrong I guess.
Yep. Logic is incorrect.
Can you also do more stone games? stone game 2, 3, and more? I'm hard stuck on stone game 2 lol
I was just searching for this problem. Then, you uploaded.
th-cam.com/channels/yoFQsVztx2oHWq14nY8A6A.html
Hi buddy.
Very great explaining the DP solution. But seems like your DFS function just returns the max value of Alice choice. We implicitly understand based on the restrictions of this problem Alice always win, but for extensions any idea how can we compare Alice's max choice value and Bob's?
we can calculate bob's value from total - alice = bob, and then compare
Awesome video my dude, it takes me a bit to get the idea of the code, Roy Tushar video of bottom up visualization is a good compliment with this solution
When even is false, isn't B maximizing A's value and not their own?
I don't get it why we are narrowing the choices between first + third, second + fourth piles. It says Alice will always pick third one if she picks first pile initially.
Pile 1, 2, 3 , 4. Alice can pick first pile. Say Bob picks fourth pile. Alice can pick second pile at the next turn. So it is first+second for Alice.
Hey, I came up with this code before I saw your video. Can you elaborate if this is incorrect or suboptimal?
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
resA, resB = 0, 0
l, r = 0, len(piles)-1
i = 0
while l piles[r]:
resA += piles[l]
l += 1
else:
resA += piles[r]
r -= 1
else:
if piles[l] > piles[r]:
resB += piles[l]
l += 1
else:
resB += piles[r]
r -= 1
return True if resA > resB else False
Thankyou :)
Wrong bro.. u went for greedy approach🙃.. here greedy approach is not always optimal..
@@CSBAjay but it passes all test cases on Leetcode ?
I have a doubt if it is bob and max(dfs(l+1,r),dfs(l,r-1) means bob if choosing such a way alex get max no of piles but bob should such that alex stones should be minimized...im confused
Haha what coincidence, I requested for you to cover stone game in a comment on a recent vid. Thanks!!
This question is flawed so result verification cannot identify bugs.
However, I think the solution presented is also flawed, because Bob does not make any choice at all.
This is because *left* and *right* are going to be 0 for Bob and the *max()* expression is just going to channel Alice's next choice. If Bob did not make a choice, then you can't tell what Alice would be left with to pick from.
Also, *even* is incorrectly calculated, should be *l - r + 1*
A better approach is to have dfs() return a tuple of (player1, player2) sum, but then alternate every dfs call to a different player making the choice. In this way, you do give Bob a choice to pick a pile.
This is not the way you solve game theory . You could have introduced Bob's role of selecting maximum for himself and leaving Alice the minimum... This shows the wrong answer dude.. anyways appreciate your content
Such an amazing explanation! Thanks!
thanks for this amazing explanation sir.
I like the fact that over 2% of solutions is still faster than your "return True" 😁
code:
class Solution {
public:
bool stoneGame(vector& piles) {
return true;
}
};
Apparently, there are some solutions that are faster than just returning True.
Why are we trying to return the max value when Bob is making a turn? bob tries to reduce Alice score, so bob should return the min score?
What if Alice wins only if Bob has less value? In your code you are only computing the maximal value Alice can obtain. How can you know if she obtained more than Bob?
Please explain how to find all duplicates in an array, please
1.create a dictionary
2. iterate throught your input array
3. if the element is not present in dictionary then assign the value as 1
4. if it's present in the dictionary then increment the value by 1
5. print all the items from the dictionary having value>1.
why are we taking only alice optimal approach here. Like we are finding all the approaches in which alice can find asnwer and then we are just getting max of it. I get it but why not also take bobs optimal approach.
I like your teaching bro
Hi NeetCode,
I think there is a flaw in the logic of your dynamic programming approach. Your current approach seems to always return the highest possible choice between:
a) piles[left] + dfs(left + 1, right)
b) piles[right] + dfs(left, right - 1)
However, you always add 0 if it is Bob's turn. In reality, we should be adding the value from piles[left/right] to Bob's score (or subtracting the value from piles[left/right] from a score that's shared between Alice and Bob) instead of adding zero to the score. Otherwise, when we add 0 to the score, it's as if we skipped this index entirely and ignored Bob's turn.
Your solution is always going to be accepted under the current constraints of the problem because Alice will always win, but in a situation where it was actually possible for Bob to win, Bob would never win because we always ignore values from piles when it's his turn. For instance, if the problem wasn't only limited to even lengths and we had the following input:
piles = {1,4,2}
Your solution will say that Alice should win, but in reality it should be Bob who wins. I think a correct approach to this problem which accounts for the possibility that Bob could win would look something like this: leetcode.com/problems/stone-game/solutions/4219547/readable-top-down-dp-solution-with-explanation/
We can create a 2D array, which is L * R size.
When l = r, means there is only one pile to choose. So dp[L][R] should be same as the piles
When L > R, non sense
When L < R, we compute:
dp = [[0] * len(piles) for _ in range(len(piles))]
for i, pile in enumerate(piles):
dp[i][i] = pile
for l in range(len(piles) - 2, -1, -1):
for r in range(l + 1, len(piles)):
even = True if (r - l) % 2 else False
left = piles[l] if even else 0
right = piles[r] if even else 0
dp[l][r] = max(dp[l + 1][r] + left, dp[l][r - 1] + right)
return dp[0][len(piles) - 1] > (sum(piles) / 2)
And the 1D array, is similar with 2D solution. Since we know the new DP is only related with dp[l + 1][r] and dp[l][r - 1]. We do not need to create a new nextDP array, you will see in the code.
Then we get below:
dp = piles.copy()
for l in range(len(piles) - 2, -1, -1):
for r in range(l + 1, len(piles)):
even = True if (r - l) % 2 else False
left = piles[l] if even else 0
right = piles[r] if even else 0
dp[r] = max(dp[r] + left, dp[r - 1] + right)
return dp[len(piles) - 1] > (sum(piles) / 2)
Actually, the graph is like a reversed triangle. And they are much more efficient.
The only way I think O(1) is possible is for even length array with odd sum.
For odd length, it will fail : example 3,100,4. No matter what alice peeks, she is bound to lose
The question asks if it is possible for alice to win at least one game, here's how she can pick to win [3,100,4], say alice picks 3, and then bob picks 4, then alice picks 100, remember out of every possible way bob and alice can pick the stones, there does exist a way that alice can win
Anyways what's more weird about this question is the statement "Assuming Alice and Bob play optimally" - if a DP approach considers all possibilities then one of those possibilities would include the case where alice wins which is the same as saying where bob does NOT play optimally, because he lost, that is what "optimally" means right? i.e to win?
It needs to have an even number of piles, based on the question. Therefore, 3,100,4 is not a valid input because it's odd.
so this game is rigged and whoever plays first always wins?
correct solution
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
dp={}
def dfs(l,r):
if l>r:
return 0
if (l,r) in dp:
return dp[(l,r)]
alice_turn=True if (r-l+1)%2==0 else False
left=piles[l]
right=piles[r]
if alice_turn:
dp[(l,r)]=max(dfs(l+1,r)+left,dfs(l,r-1)+right)
else:
dp[(l,r)]=min(dfs(l+1,r)-left,dfs(l,r-1)-right)
return dp[(l,r)]
return dfs(0,len(piles)-1)>0
poor ternary usage
Im first 😁😁
wife, husband = "Alice", "Bob". Isn't the answer obvious?😜
Everything was going well and then you started coding in Python 🤮.