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 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!
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.
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
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 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?
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?
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
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.
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.
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 :)
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.
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?
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
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.
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?
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/
