# Stone Game VI
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/stone-game-vi)
Canonical: https://scaleengineer.com/dsa/problems/stone-game-vi
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Arcesium](https://scaleengineer.com/companies/arcesium)
---
## Problem
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`

# Approaches
## Dynamic Programming with Bitmasking
This problem can be modeled as a typical impartial game, which can be solved using the minimax algorithm. Since the game has overlapping subproblems (the state of the game is defined by the set of remaining stones), we can use dynamic programming with memoization to avoid recomputing results for the same subproblems. This approach guarantees finding the optimal strategy for both players but is computationally expensive.
**Time:** O(N * 2^N). There are `2^N` possible states (masks). For each state, we iterate through up to `N` stones to decide the next move. · **Space:** O(2^N). This is for the memoization table `memo` which stores the result for each of the `2^N` possible masks.
**Pros:** It's a standard and robust way to solve impartial games.; It correctly models the optimal, turn-by-turn decision-making process and guarantees a correct solution.
**Cons:** The exponential time and space complexity make it infeasible for the given constraints (`n <= 10^5`). It will result in a 'Time Limit Exceeded' or 'Memory Limit Exceeded' error on a platform like LeetCode.
### Explanation
We define a function, say `solve(mask)`, which calculates the maximum score difference the current player can achieve given a `mask` representing the stones that have already been taken. A bitmask is a natural way to represent the subset of taken stones, where the i-th bit is set if the i-th stone is taken.

The turn of the player can be determined by the number of set bits in the mask. If the count is even, it's Alice's turn; if odd, it's Bob's turn.

The recurrence relation works as follows: The current player tries every available stone `i`. By picking stone `i`, they get some points, and the game transitions to the opponent's turn with a new mask. The value of this move is the points gained from stone `i` minus the score difference the opponent can achieve in the subsequent subgame. The player chooses the move that maximizes this value.

The base case for the recursion is when all stones are taken (mask is all 1s), where the score difference is 0. The final answer is the result of the initial call `solve(0)`.

```java
class Solution {
    // This solution is correct but will time out for the given constraints.
    // It's suitable for smaller N (e.g., N <= 20).
    Integer[] memo;
    int n;
    int[] aliceValues;
    int[] bobValues;

    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        this.n = aliceValues.length;
        this.aliceValues = aliceValues;
        this.bobValues = bobValues;
        // The state space 2^n is too large for n > 20.
        if (n > 20) {
            // This DP approach is not feasible. The greedy approach should be used.
            // This code block is for demonstrating the DP logic on small inputs.
            return 0; // Placeholder
        }
        this.memo = new Integer[1 << n];
        
        int diff = solve(0);
        
        if (diff > 0) return 1;
        if (diff < 0) return -1;
        return 0;
    }

    // Returns the score difference for the current player relative to the opponent
    // for the subgame where 'mask' represents taken stones.
    private int solve(int mask) {
        if (mask == (1 << n) - 1) {
            return 0;
        }
        if (memo[mask] != null) {
            return memo[mask];
        }

        int numTaken = Integer.bitCount(mask);
        boolean isAliceTurn = (numTaken % 2 == 0);
        
        int maxVal = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            // If stone i is not taken yet
            if ((mask & (1 << i)) == 0) {
                int currentPoints = isAliceTurn ? aliceValues[i] : bobValues[i];
                // The recursive call returns the difference for the *next* player.
                // We subtract it to get the difference from the *current* player's perspective.
                // my_score - opponent_score = currentPoints + my_sub_score - opponent_sub_score
                // = currentPoints - (opponent_sub_score - my_sub_score)
                // = currentPoints - solve(new_mask)
                int currentDiff = currentPoints - solve(mask | (1 << i));
                if (currentDiff > maxVal) {
                    maxVal = currentDiff;
                }
            }
        }
        
        return memo[mask] = maxVal;
    }
}
```
### Algorithm
- Define a recursive function `solve(mask)` that returns the maximum score difference the current player can obtain from the set of available stones (represented by the inverse of `mask`).
- Use a memoization table `memo` to store the results for each `mask` to avoid recomputing.
- In `solve(mask)`, determine the current player based on the number of stones already taken (`Integer.bitCount(mask)`). An even count means it's Alice's turn.
- Iterate through all untaken stones `i`.
- For each stone `i`, the current player gets their points for that stone, and the game transitions to the opponent's turn. The value of this move is `points[i] - solve(mask | (1 << i))`, where `solve(mask | (1 << i))` is the score difference the opponent will achieve in the subgame.
- The current player will choose the stone `i` that maximizes this value.
- Store the result in `memo[mask]` and return it.
- The initial call is `solve(0)`. The sign of the result determines the winner.

## Greedy Approach based on Sum of Values
A much more efficient solution can be found by analyzing the value of each move. When a player chooses a stone `i`, they not only gain points for themselves (`aliceValues[i]` or `bobValues[i]`) but also prevent their opponent from gaining points from that same stone. The total impact of choosing stone `i` on the game's outcome is related to the sum of the values, `aliceValues[i] + bobValues[i]`. Both players, playing optimally, will want to secure the stones with the highest combined value.
**Time:** O(N log N). The dominant operation is sorting the `N` stones. The subsequent iteration takes `O(N)` time. · **Space:** O(N). We need extra space to store the stones along with their values to facilitate sorting. If we sort indices instead, it would still be O(N).
**Pros:** Highly efficient and passes within the time limits for the given constraints.; The logic is straightforward to implement once the greedy criterion is understood.
**Cons:** The greedy choice is not always obvious in game theory problems. Its correctness relies on the specific structure of the score calculation in this problem and may not be generalizable to other game variants.
### Explanation
Let's analyze the game from the perspective of maximizing the score difference. Alice wants to maximize `A_score - B_score`.
Let `S_A` be the set of stones Alice takes and `S_B` be the set for Bob.
`A_score - B_score = sum_{i in S_A} a_i - sum_{j in S_B} b_j`.
We know that `S_A` and `S_B` form a partition of all stones. So, `sum_{j in S_B} b_j = sum_{all k} b_k - sum_{i in S_A} b_i`.
Substituting this, Alice wants to maximize:
`sum_{i in S_A} a_i - (sum_{all k} b_k - sum_{i in S_A} b_i) = sum_{i in S_A} (a_i + b_i) - sum_{all k} b_k`
Since `sum_{all k} b_k` is a constant, Alice's goal is equivalent to maximizing `sum_{i in S_A} (a_i + b_i)`. This means Alice wants to pick stones that have the highest `a_i + b_i` sum.

Similarly, Bob wants to maximize `B_score - A_score`, which is equivalent to minimizing `A_score - B_score`. This means Bob also wants to prevent Alice from getting stones with high `a_i + b_i` values, so he will also try to pick them first.

Since both players have the same priority—to pick the available stone with the highest `aliceValues[i] + bobValues[i]`—the optimal strategy for both is a greedy one. They will take turns picking the best available stone from a list sorted by this combined value.

```java
import java.util.Arrays;

class Solution {
    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        int n = aliceValues.length;
        int[][] stones = new int[n][2];
        for (int i = 0; i < n; i++) {
            stones[i][0] = aliceValues[i];
            stones[i][1] = bobValues[i];
        }

        // Sort stones by the sum of their values in descending order.
        // The value of a stone to the game is a_i + b_i.
        Arrays.sort(stones, (a, b) -> Integer.compare(b[0] + b[1], a[0] + a[1]));

        int aliceScore = 0;
        int bobScore = 0;

        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) { // Alice's turn
                aliceScore += stones[i][0];
            } else { // Bob's turn
                bobScore += stones[i][1];
            }
        }

        return Integer.compare(aliceScore, bobScore);
    }
}
```
### Algorithm
- Create a data structure to hold the values of each stone, for example, a 2D array `stones[i] = {aliceValues[i], bobValues[i]}`.
- Sort this structure in descending order based on the sum of Alice's and Bob's values for each stone (`aliceValues[i] + bobValues[i]`).
- Initialize `aliceScore` and `bobScore` to 0.
- Iterate through the sorted stones from index 0 to `n-1`.
- On even turns (indices 0, 2, 4, ...), it's Alice's turn. Add the `aliceValue` of the current stone to `aliceScore`.
- On odd turns (indices 1, 3, 5, ...), it's Bob's turn. Add the `bobValue` of the current stone to `bobScore`.
- After iterating through all stones, compare the final scores.
- Return `1` if `aliceScore > bobScore`, `-1` if `bobScore > aliceScore`, and `0` for a draw.

# Solutions
### Java

```java
class Solution { public int stoneGameVI ( int [] aliceValues , int [] bobValues ) { int n = aliceValues . length ; int [][] arr = new int [ n ][ 2 ]; for ( int i = 0 ; i < n ; ++ i ) { arr [ i ] = new int [] { aliceValues [ i ] + bobValues [ i ], i }; } Arrays . sort ( arr , ( a , b ) -> b [ 0 ] - a [ 0 ]); int a = 0 , b = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int j = arr [ i ][ 1 ]; if ( i % 2 == 0 ) { a += aliceValues [ j ]; } else { b += bobValues [ j ]; } } if ( a == b ) { return 0 ; } return a > b ? 1 : - 1 ; } }
```

### CPP

```cpp
class Solution {
public:
  int stoneGameVI(vector<int> &aliceValues, vector<int> &bobValues) {
    int n = aliceValues.size();
    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; ++i) {
      arr[i] = {aliceValues[i] + bobValues[i], i};
    }
    sort(arr.rbegin(), arr.rend());
    int a = 0, b = 0;
    for (int i = 0; i < n; ++i) {
      int j = arr[i].second;
      if (i % 2 == 0) {
        a += aliceValues[j];
      } else {
        b += bobValues[j];
      }
    }
    if (a == b)
      return 0;
    return a > b ? 1 : -1;
  }
};

```

### Python

```python
class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int: arr = [(a + b, i) for i, (a, b) in enumerate(zip(aliceValues, bobValues))] arr . sort(reverse=True) a = sum(aliceValues[v[1]] for i, v in enumerate(arr) if i % 2 == 0) b = sum(bobValues[v[1]] for i, v in enumerate(arr) if i % 2 == 1) if a > b: return 1 if a < b: return - 1 return 0

```