Stone Game VI — Alghoritms&Visualizations

Introduction
Throughout this article, we are going to be analyzing an interesting coding challenge that I’ve recently happened to solve. Those of you who love problem visualization as I do might end up being disappointed because this time I didn’t manage to come up with a satisfying visualization of the problem, however, I’ll try my best to run you through the thoughts that led me to the solution.

The problem
As usual, this is one of the problems that I found while brushing up my algorithmic skilled on LeetCode. This medium difficulty problem is titled “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.

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.

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

Example:
Input: aliceValues = [2,4,3], bobValues = [1,6,7]
Output: -1

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.

First Approach
The first idea crossing my mind when I read the problem description was to compute all the possible combinations and eventually return the final result.
aliceValues = [2,4,3], bobValues = [1,6,7]

Following the tree, at each step, Alice tries to maximize her score, and Bob tries to maximize his, which also means minimizing Alice’s.

Let’s go through the above tree to better understand the idea.
At first, Alice has to take one of the three possible stones. Which one should she choose? We said the one that brings to her biggest score. So let’s try to follow the path starting with taking Stone1.
It’s Bob’s turn now, not differently from Alice, he wants to maximize his score, or in other words, minimize Alice’s. He has got two possibilities:
> Bob picks Stone2 and makes $6, while Alice makes $5
> Bob picks Stone3 and makes $7, while Alice makes $6
So in this case, we can easily see that, if Alice takes Stone1, Bob will take Stone3 or Stone2, winning the game.

It should be quite clear by now, but I don’t want to take anything for granted, so let’s analyze another possible branch of the tree, the one starting with Alice taking Stone2. Also in this case Bob has been left with two remaining choices:
> Bob picks Stone1 and makes $1, while Alice makes $7
> Bob picks Stone3 and makes $7, while Alice makes $6
Not differently from before, there’s no way for Alice to win this game by firstly picking the Stone1 because eventually, Bob will go with Stone3 winning the game.

A tad different from the previous scenario though, if Bob didn’t make the best decision, he would happen to lose, because taking Stone1 would make him lose.

I’ll let you analyze the third and last branch, which doesn’t differ much from the first one. As you can see, poor Alice can’t beat Bob, it doesn’t matter what choice she makes. Consequently, the output for the given input is -1.

The Issue
Searching the whole solution space brings us to the correct solution, nevertheless, this approach is quite heavy. The time complexity is O(2^n), where n is the number of stones, and even with modest inputs, we will wind up having too many operations to get to the solution.

Concretely, an array of 105 stones (the limit given by the constraints) requires 2¹⁰⁵ steps. And if 2¹⁰⁵ doesn’t scare you, perhaps 40,564,819,207,303,340,847,894,502,572,032 does.

It’s written 2¹⁰⁵, but we read Time Limited Exceeded.

The second approach
Ok, the previous approach goes down any possibilities. It wasn’t incorrect, but too expensive, we need something faster.

Let’s take some extra time to think of a better solution. Is there a way to know that a stone is better than another one?
If the stones had the same values for Alice and Bob, we would always take the most valuable one, right?
Unfortunately, as the two players don’t share the values for the same stones, at each step they need to consider both the stones that enable them to make as much money as possible, but also make sure to not allow the other player to pick the stones which are of great value for her/him.

Let’s consider an example:
aliceValues = [5, 10]
bobValues = [100000, 3]

Picking the most valuable stone is obviously not the best strategy, as a matter of fact, it would make Alice take Stone2, making $10, but allowing Bob to make $1000000 out of Stone1.
On the other hand, if Alice went with Stone1, she would make half of the money -$5 - but win the game.

At this point, it might be of interest to understand when it would make sense for Alice to change her mind and pick Stone2 instead. Let’s consider:
aliceValues=[5, 100001]
bobValues=[100000, 3]

What would you do if you were in Alice? If you went with Stones2, I have bad news for you! Your choice has probably been influenced by the word “money”. Sure, if Alice picked Stone2, she would win and make $100001. But let’s check out Bob’s final status as well. He would conclude the game with $100000. I know, probably both the players would be happy, even the loser.
Let’s remove the word “money” from this context now, and focus on the real problem. When you play a two-player game, your goal is not to make as many points as you can! The best strategy is the one that maximizes the final difference between your score and the opponent's when you win and minimize it when you lose.

Think about it. If you are watching a football match, would you rather see your team winning 1000001 to 1000000 or 10 to 0? And if you were supporting the losing team?
Let’s go back to our example:
aliceValues=[5, 100001]
bobValues=[100000, 3]

By now, we should agree on the fact that the best choice for Alice is still taking Stone1. We haven’t replied to our first question yet: When would taking Stone2 make sense for Alice?
aliceValues=[5, 100003]
bobValues=[100000, 3]

What about this situation? If Alice picks Stone2, she will win up by 3. If she picks Stone1, she will win up by 2. So finally we have found when Alice should decide to firstly choose Stone2, leaving Stone1 to Bob.

Interesting, isn’t it? At this point, you might be falling into the trap of wanting to sort the stones by the difference between the player given values to each stone. Please don't do it! once again:
aliceValues=[5, 100001]
bobValues=[100000, 3]

If Alice picked the stone with the maximum difference between the values, she would pick Stone2 (because |100001–3|>|5–100000|), which is the wrong choice as we already asserted.

Some of you might have already seen the pattern. If you haven’t yet, no worries, let’s have a deeper step-by-step look:

aliceValues=[5, 99999]
bobValues=[1000000, 3]
Alice prefers Stone1

aliceValues=[5, 1000000]
bobValues=[1000000, 3]
Alice prefers Stone1

aliceValues=[5, 1000001]
bobValues=[1000000, 3]
Alice prefers Stone1

aliceValues=[5, 1000002]
bobValues=[1000000, 3]
Alice doesn't have a favorite stone

aliceValues=[5, 1000003]
bobValues=[1000000, 3]
!!Alice prefers Stone2!!

The solution to this problem boils down to understanding what is the threshold that, once gets passed, makes Alice swap from Stone1 to Stone2.

If you have seen it, you can go straight to the code, otherwise, let me try to write down some other examples that helped me out solve the problem:

aliceValues=[0, 8]
bobValues=[10, 1]
Alice prefers Stone1

aliceValues=[0, 9]
bobValues=[10, 1]
Alice doesn’t have a favorite stone

aliceValues=[0, 10]
bobValues=[10, 1]
!!Alice prefers Stone2!!

It’s weird, I know, but Alice might prefer picking a stone that has no value for her because that would be a better choice in terms of the final score.
Ok, if you can’t see the pattern, don’t worry, it can happen! Let me disclose the key idea:

Each player prefers to pick the stone whose sum of the given player values is the biggest.

If you are not sold yet, let me give you a quick mathematical demonstration:
Alice score: aliceValues[StoneA]+aliceValues[StoneZ]+aliceValues[StoneC]+…
Bob score: bobValues[StoneB]+bobValues[StoneE]+bobValues[StoneK]+…
(Where “StoneA” doesn’t represent the first stone, but just one of the stones)

The goal of Alice is to end up having AliceScore > BobScore. Or in other words AliceScore-BobScore>0

It’s easy to see that, adding and subtracting some extra values to the initial equation (the red elements), we end up having an equation that Alice can maximize by choosing the stones which have the biggest aliceValues[StoneX]+bobValues[StoneX] value.

It’s obvious that also Bob follows the same strategy to maximize his score, meaning that he will pick the stone with the biggest sum

The code

Conclusions
We are done! I hope you enjoyed the article and learned how to solve these kinds of problems. If you liked it, check out my profile. Have a good one!

“Sometimes, if you look very carefully at the stones, you can understand the ocean” — Terry Pratchett