1872. Merge Stone Game

Stone Game VIII

Problem 1872 is a DP problem that creates a particularly deep impression on me.

LeetCode's super popular Alice & Bob game.

Alice Always Goes First

As LeetCode's tradition, Alice moves first just like ladies first.

So let's put ourselves in Alice's shoes and think about her opening move.

The simplest first move is for Alice to merge all stones into one in 1 sweep, bringing the game to an end with only one stone remaining.

Alice earns $\text{sum}(stones)$ points this way.

Bob, having no turn, scores 0 of course.

Alice's sweep gives a score difference of $D_{n - 1} = \text{sum}(stones)$,

where the subscript indicates this merge included the $(n - 1)^{\text{th}}$ stone.

But What If There Are $\geq 3$ Stones?

Other Options Arise

With $\geq 3$ stones, Alice has more than just that one-and-done sweep.

She can also leave out some stones, letting Bob come up to merge and score.

Suppose Alice chooses to merge only up to the $(n - 2)^{\text{th}}$ stone.

She earns $\text{sum}(stones[:n - 1])$ points.

Two stones remain on the table: the rightmost with value $stones[n - 1]$,

and the merged one Alice just created with value $\text{sum}(stones[:n - 1])$.

Now Bob must merge both (no passing allowed), earning:

$\text{sum}(stones[:n - 1]) + stones[n - 1] = \text{sum}(stones)$

The score difference is $D_{n - 2} = \text{sum}(stones[:n - 1]) - \text{sum}(stones)$.

Notably, $D_{n - 2}$ can be rewritten using $D_{n - 1} = \text{sum}(stones)$ as:

$D_{n - 2} = \text{sum}(stones[:n - 1]) - D_{n - 1}$

Should Alice Switch Options?

Now we have a binary choice: $D_{n - 2}$ vs. $D_{n - 1}$.

(1). If $D_{n - 2} > D_{n - 1}$, Alice abandons that one-and-done merger,

and chooses to merge only up to $(n - 2)^{\text{th}}$ stone, leaving out $(n - 1)^{\text{th}}$.

Recall $D_{n - 2} = \text{sum}(stones[:n - 1]) - D_{n - 1}$

$D_{n - 2} > D_{n - 1}$ is equivalent to $\text{sum}(stones[:n - 1]) - D_{n - 1} > D_{n - 1}$

One conversation to describe: "To my dear opponent: I'll give you $D_{n - 1}$.

That's because I have an even stronger option $D_{n - 2}$ ~~ so strong that even after your $D_{n - 1}$ offset, my net differential still exceeds what I'd get if taking $D_{n - 1}$ directly."

(2). Conversely, if $D_{n - 2} \leq D_{n - 1}$, Alice merges everything.

From the same equation: $D_{n - 2} \leq D_{n - 1}$ means $\text{sum}(stones[:n - 1]) - D_{n - 1} \leq D_{n - 1}$

In translation: "Merging only up to $(n - 2)^{\text{th}}$ stone earns me $\text{sum}(stones[:n - 1])$,

but my opponent earns $D_{n - 1}$. After offsetting, my net lead is $\text{sum}(stones[:n - 1]) - D_{n - 1}$.

Comparing these two, I find out it's better to also include $(n - 1)^{\text{th}}$ stone in my merger,

taking $D_{n - 1}$ as my net differential."

Because of this reasoning, $D_{n - 2}$ must be assigned the value of $D_{n - 1}$,

reflecting a key insight: when only $(n - 2)^{\text{th}}$ and $(n - 1)^{\text{th}}$ stones remain unmerged,

based on the score comparison, merging both is better than leaving out $(n - 1)^{\text{th}}$ stone.

So the option to stop at $(n - 2)^{\text{th}}$ stone is eliminated. This elimination is due to our problem's own rule: each player plays optimally.

Deriving the Transition from Here

By the same logic, if there's an option to merge only up to $(n - 3)^{\text{th}}$ stone:

$D_{n - 3} = \text{sum}(stones[:n - 2]) - D_{n - 2}$

This gives us a binary choice between $D_{n - 3}$ and $D_{n - 2}$.

You've probably spotted the pattern. The transition equation is:

$D_{i} = \max(D_{i + 1}, \; \text{sum}(stones[:i + 1]) - D_{i + 1})$

where the index range is $1 \leq i \leq n - 2$. Why this range?

(1). Index 0 is excluded because the problem requires merging at least 2 stones each time.

(2). Index $n - 1$ is also excluded because it's the base case:

merging all stones at once, covering up to the $(n - 1)^{\text{th}}$ stone.

Base Case: $D_{n - 1} = \text{sum}(stones)$

Understanding the Transition

I once found a description that captures the stories behind quite well:

Given that when only stones $i + 1, \ldots, n - 1$ remain, the current player will earn a net differential of $D_{i + 1}$.

If I merge only up to $i^{th}$ stone and earn $\text{sum}(stones[:i + 1])$,

can my earning still beat $D_{i + 1}$ after being offset?

I. If yes: I'm willing to play a bigger game by seemingly making a sacrifice here.

Give up the known gain in exchange for an even greater upcoming gain.

II. If no: I can't let my opponent take that $D_{i + 1}$.

Better put it into my pocket now to be my net differential.

You'll also notice our transition here is a bit unusual:

it moves from larger indices to smaller indices.

So when computing, traverse from larger to smaller indices,

rather than using extra DFS and cache which would cost $O(n)$ space......

Also, the transition equation tells us each index's state only depends on the immediately previous index, so there's no need to maintain an array costing $O(n)$ space.

C++

#include <numeric>
#include <vector>
using namespace std;

int maximizeScoresDifference(vector<int>& stones) // LeetCode Q.1872.
{
    int prefixSum = 0;
    for (const auto& stone : stones)
        prefixSum += stone;

    // Base case: Alice merges everything as the only attempt.
    int maxScoreDiff = prefixSum;

    prefixSum -= stones.back();

    for (int idx = stones.size() - 2; idx >= 1; idx--) {
        if (prefixSum - maxScoreDiff > maxScoreDiff)
            maxScoreDiff = prefixSum - maxScoreDiff;

        prefixSum -= stones[idx];
    }

    return maxScoreDiff;
}

Python

def maximize_scores_difference(stones: list[int]) -> int:  # LeetCode Q.1872.
    prefix_sum = sum(stones)

    # Base case: Alice merges everything as the only attempt.
    max_score_diff = prefix_sum

    prefix_sum -= stones[-1]

    for idx in range(len(stones) - 2, 0, -1):
        if prefix_sum - max_score_diff > max_score_diff:
            max_score_diff = prefix_sum - max_score_diff

        prefix_sum -= stones[idx]

    return max_score_diff

Just use a variable called max_score_diff to track $D_i$.

Time complexity $O(n)$, space complexity $O(1)$.

Follow-up Problems

I. How would you modify the code above to print out all "scoring plays"?

A scoring play is defined as when any player merges some stones and earns points.

II. To make the game more exciting, our goal is to maximize the number of scoring plays.

What input array stones should you design to achieve this?