{x}
blog image

Stone Game VI

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones in a pile. On each player's turn, they can remove a stone from the pile and receive points based on the stone's value. Alice and Bob may value the stones differently.

You are given two integer arrays of length n, aliceValues and bobValues. Each aliceValues[i] and bobValues[i] represents how Alice and Bob, respectively, value the ith stone.

The winner is the person with the most points after all the stones are chosen. If both players have the same amount of points, the game results in a draw. Both players will play optimally. Both players know the other's values.

Determine the result of the game, and:

  • If Alice wins, return 1.
  • If Bob wins, return -1.
  • If the game results in a draw, return 0.

 

Example 1:

Input: aliceValues = [1,3], bobValues = [2,1]
Output: 1
Explanation:
If Alice takes stone 1 (0-indexed) first, Alice will receive 3 points.
Bob can only choose stone 0, and will only receive 2 points.
Alice wins.

Example 2:

Input: aliceValues = [1,2], bobValues = [3,1]
Output: 0
Explanation:
If Alice takes stone 0, and Bob takes stone 1, they will both have 1 point.
Draw.

Example 3:

Input: aliceValues = [2,4,3], bobValues = [1,6,7]
Output: -1
Explanation:
Regardless of how Alice plays, Bob will be able to have more points than Alice.
For example, if Alice takes stone 1, Bob can take stone 2, and Alice takes stone 0, Alice will have 6 points to Bob's 7.
Bob wins.

 

Constraints:

  • n == aliceValues.length == bobValues.length
  • 1 <= n <= 105
  • 1 <= aliceValues[i], bobValues[i] <= 100

Solution Explanation for Stone Game VI

This problem explores the concept of a strategic game between two players, Alice and Bob, who have different valuations for a set of stones. The goal is to determine the winner based on optimal play from both sides. A greedy approach combined with sorting proves efficient.

Approach: Greedy Strategy with Sorting

The core idea lies in recognizing that the optimal strategy involves selecting stones that maximize the difference between your score and your opponent's. We don't need to explore every possible game path; a greedy strategy suffices because of the nature of the problem.

  1. Combined Value: For each stone, calculate the sum of Alice's and Bob's valuations. This represents the total potential points available for that stone.

  2. Sorting: Sort the stones in descending order based on their combined values. This prioritizes stones with higher overall value, ensuring that the highest-value stones are picked first.

  3. Alternating Turns: Alice and Bob take turns picking stones, starting with Alice. They will always choose the stone with the highest remaining combined value.

  4. Score Calculation: Alice accumulates the points from her chosen stones (using aliceValues), and Bob accumulates points from his choices (using bobValues).

  5. Determining the Winner: After all stones are picked, compare Alice's and Bob's total scores. Return 1 if Alice wins, -1 if Bob wins, and 0 for a draw.

Time and Space Complexity

  • Time Complexity: O(n log n), dominated by the sorting step. The other operations (creating the combined value array, iterating for score calculation) are linear, O(n).

  • Space Complexity: O(n) to store the vals array (or a similar data structure to hold combined values and indices)

Code Implementation (Python)

class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
        n = len(aliceValues)
        vals = []  #List to store (combined value, original index) pairs
        for i in range(n):
            vals.append((aliceValues[i] + bobValues[i], i))
        
        vals.sort(reverse=True) #Sort in descending order of combined value
 
        alice_score = 0
        bob_score = 0
        for i in range(n):
            combined_value, index = vals[i]
            if i % 2 == 0: #Alice's turn
                alice_score += aliceValues[index]
            else: #Bob's turn
                bob_score += bobValues[index]
        
        if alice_score > bob_score:
            return 1
        elif alice_score < bob_score:
            return -1
        else:
            return 0

The code in other languages (Java, C++, Go, TypeScript) follows a similar structure, adapting the syntax and data structures appropriately, but the core algorithm remains consistent. The comments in the Python code clearly explain each step of the process.