Stone Game VI
Alice and Bob take turns picking stones from a collection, with Alice going first.
Each stone i has two values: aliceValues[i] (how much Alice values it) and bobValues[i] (how much Bob values it). On a player's turn, that player picks one remaining stone. Each player's total score is the sum of how they value the stones they picked.
Assuming both play optimally to maximize their own score, determine the result:
- Return
1if Alice's total is greater than Bob's. - Return
-1if Bob's total is greater. - Return
0if they are equal.
Examples
Input: [[1,3],[2,1]]
Output: 1
Input: [[1,2],[3,1]]
Output: 0
Hints
This is not a standard minimax on raw values. The key is to sort stones by the sum `aliceValues[i] + bobValues[i]` descending.
The optimal strategy for both players is to pick the stone with the highest combined value. This is because each player cares about both their own gain and denying the opponent.
Sort by sum descending, then alternate picks. Alice gets the even-indexed stones and Bob gets odd-indexed stones from the sorted list.
Related Problems
Stone Game VI
Alice and Bob take turns picking stones from a collection, with Alice going first.