Leetcode 1686. Stone Game VI

Problem explanation:

In this problem, Alice and Bob are playing a game where they take turns to pick stones from a pile. Each stone has a specific value for Alice and Bob. We need to determine the outcome of the game based on the given values of the stones.

Each player tries to maximize their own total value. They play optimally, meaning they will always pick the stone which adds the maximum value to their score. If Alice starts the game, they both alternately pick up the stones until all stones have been taken.

We are given Alice's values of the stones in aliceValues and Bob's values in bobValues. We have to return 1 if Alice wins (i.e., her total value is more than Bob's), -1 if Bob wins, and 0 if the game ends in a draw.

For example, if aliceValues = [1,3] and bobValues = [2,1], Alice will win by picking the second stone (value 3 for Alice) first, Bob picks the other stone resulting in Alice 3, Bob 2. We return 1 as output.

Solution approach:

The main part of the solution is the strategy to play the game optimally. The strategy here is to maximize the total value at every turn, considering the difference in values of the stones for Alice and Bob. Since Alice goes first, if, for a stone, the sum of Alice and Bob's values is the same, Alice would benefit more by choosing that stone. Thus, sort the stones based on the sum of Alice and Bob's values.

In the solution, we push both Alice and Bob's values of each stone into a 2D vector. We then sort this vector in descending order based on the total value of each stone for both Alice and Bob. Next, we iterate over the sorted vector, Alice picks the stones at even indices and Bob at odd indices. We keep adding the values to their total scores. Finally, compare Alice and Bob's total scores to determine the winner.

Python Solution:

1
2python
3class Solution:
4    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
5        n = len(aliceValues)
6        values = [[aliceValues[i]+bobValues[i], aliceValues[i], bobValues[i]] for i in range(n)]
7        values.sort(reverse=True)
8
9        aliceTotal = sum(values[i][1] for i in range(0, n, 2))
10        bobTotal = sum(values[i][2] for i in range(1, n, 2))
11
12        if aliceTotal > bobTotal:
13            return 1
14        elif aliceTotal < bobTotal:
15            return -1
16        else:
17            return 0

Java Solution:

1
2java
3import java.util.*;
4
5class Solution {
6    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
7        int n = aliceValues.length;
8        int[][] values = new int[n][3];
9        
10        for (int i = 0; i < n; i++) {
11            values[i][0] = aliceValues[i] + bobValues[i];
12            values[i][1] = aliceValues[i];
13            values[i][2] = bobValues[i];
14        }
15        
16        Arrays.sort(values, (a, b) -> b[0] - a[0]);
17        
18        int aliceTotal = 0;
19        int bobTotal = 0;
20        for (int i = 0; i < n; i++) {
21            if (i % 2 == 0) {
22                aliceTotal += values[i][1];
23            } else {
24                bobTotal += values[i][2];
25            }
26        }
27        
28        return Integer.compare(aliceTotal, bobTotal);
29    }
30}

JavaScript Solution:

1
2javascript
3var stoneGameVI = function(aliceValues, bobValues) {
4    let n = aliceValues.length;
5    let values = new Array(n).fill(0).map(() => new Array(3).fill(0));
6    
7    for (let i = 0; i < n; i++) {
8        values[i][0] = aliceValues[i] + bobValues[i];
9        values[i][1] = aliceValues[i];
10        values[i][2] = bobValues[i];
11    }
12    
13    values.sort((a, b) => b[0] - a[0]);  
14    
15    let aliceTotal = 0;
16    let bobTotal = 0;
17    for (let i = 0; i < n; i++) {
18        if (i % 2 == 0)
19            aliceTotal += values[i][1];
20        else
21            bobTotal += values[i][2];
22    }
23
24    return aliceTotal === bobTotal ? 0 : aliceTotal > bobTotal ? 1 : -1;
25};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
6        const int n = aliceValues.size();
7        vector<vector<int>> values;
8        int a = 0;
9        int b = 0;
10
11        for (int i = 0; i < n; ++i)
12          values.push_back({aliceValues[i] + bobValues[i], aliceValues[i], bobValues[i]});
13
14        sort(values.begin(), values.end(), greater<vector<int>>());
15
16        for (int i = 0; i < n; ++i) {
17            if (i % 2 == 0) a += values[i][1];
18            else b += values[i][2];
19        }
20
21        if (a == b) return 0;
22        return a > b ? 1 : -1;
23    }
24};

C# Solution:

1
2csharp
3public class Solution {
4    public int StoneGameVI(int[] aliceValues, int[] bobValues) {
5        int n = aliceValues.Length;
6        int[][ ] values = new int[n][ ]; 
7
8        for (int i = 0; i < n; i++) {
9            values[i] = new int[] {aliceValues[i] + bobValues[i], aliceValues[i], bobValues[i]};
10        }
11
12        Array.Sort(values, (a, b) => b[0] - a[0]);
13
14        int aliceTotal = 0, bobTotal = 0;
15        for (int i = 0; i < n; i++) {
16            if (i % 2 == 0) aliceTotal += values[i][1];
17            else bobTotal += values[i][2];
18        }
19
20        return aliceTotal.CompareTo(bobTotal);
21    }
22}

These are optimal strategies to play the game in Python, Java, JavaScript, C++, and C#. Each solution first creates a list that contains both Alice's and Bob's values for each stone, sorted in descending order. Then, it iterates over this sorted list, respectively accumulating Alice's and Bob's scores when the index is even or odd. In the end, it compares the totals and returns the result.

Notably, this strategy guarantees that each player will always make the best possible move - maximizing their overall value. Furthermore, by storing both players' stone values in a combined list and sorting it, the solution ensures that if there is a tie in total stone value, Alice will get the advantage - since she moves first, and the stones are sorted in descending order.

Some minor language-specific differences exist in the solutions:

• In Python, Python's built-in sorting for lists of lists allows for easy separation and sorting.
• In C++, we utilize the vector to achieve the same functionality.
• JavaScript leverages JavaScript's built-in sort for arrays of arrays.
• Java makes use of a 2D array and Java's (Array) built-in sort method.
• C# solution follows the same strategy, employing a jagged array and the built-in Array sort method.

In conclusion, this problem illustrates an optimal strategy in a competitive game scenario. The mechanism highlights the interplay of array manipulation, sorting techniques, and game theory elements. This solution pattern can be used in similar game-theoretic settings or problems involving competitive simultaneous maximization.