Stone Game VI

Firdausia Fatima
Last Updated: May 13, 2022

 

Introduction

I'm sure you've heard of Alice and Bob. They are two well-known hypothetical kids in the world of computer science problems which are always engaged in some strange game. I'm curious as to where they derive their game's ideas. They're both brilliant, so they'll play to their strengths, and we'll have to figure out who will win.

The problem we'll be discussing today is one such problem involving these children.

This problem can also be classified as an array problem, and if it is, it is always a good idea to try to include sorting into the solution; this method mainly works.

Let us now define the problem.

Problem Statement

Alice and Bob are playing a stone game, and Alice starts first. 

Stone game

There is a pile of ‘N’ stones. Each player takes a turn removing a stone from the pile and collecting the value of that stone.  And they both value the stones differently. You are given two integer arrays of length ‘N’, ‘ALICE_VALUE’ and ‘BOB_VALUE’ where each ALICE_VALUE[i] and BOB_VALUE[i] represent what Alice and Bob have scored the ith stone.

The winner is the person who has the most points after all of the stones have been chosen. If they both have the same number of points, the game ends in a tie.

Game Result

  • 1 - Alice wins.
  • -1 - Bob wins.
  • 0 - Game results in a draw.

Now that we've defined the problem let's see how to solve it.

Intuition

Let’s understand how the game will be played optimally with an example.

If I am Alice, then I’ll try to pick the stone with the maximum value, i.e., the third stone with a value of 7, but then Bob will, in his turn, pick the first stone with a value of 8. So I not only have to maximize my score but to minimize Bob’s score. So my score for ith stone is the summation of both my and Bob’s value for ith stone.

Hence Alice and Bob both will pick stones with maximum value, both their values combined.

Lets ALICE_SCORE be Alice’s scores and BOB_SCORE be bob’s scores. At the start of the game, both their scores are zero.

  1. First Pick: Alice will pick the first stone with a score of 13. So ALICE_SCORE=13.
  2. Second Pick: Bob will pick the fourth stone with a score of 10. So BOB_SCORE=10.
  3. Third Pick: Alice will pick the third stone and ALICE_SCORE = (13 + 9) = 22.
  4. Fourth Pick: Bob picks the fifth stone, and BOB_SCORE = (10 + 5) = 15.
  5. Fifth Pick: Alice picks the second stone, and ALICE_SCORE = (22 + 3) = 25.

Hence Alice Wins.

Approach 1- Brute force

We’ve seen in the above intuition that both players will pick the stones based on both their values on that stone. So we will make an array SUM_SCORE, where SUM_SCORE[i] = ALICE_VALUE[i] + BOB_VALUE[i]. And in each round, we will find the best sum score stone to pick, and this value will be added to the player’s score.

Let’s see the algorithm in depth.

  • Create an array SUM_SCORE of length ‘N’.
  • Loop from 0 to N - 1 and Intilize SUM_SCORE= ALICE_VALUE[i] + BOB_VALUE[i].
  • Next, loop from 1 to 'N' and find the best possible stone to pick in each round, which will again require loop through the whole array.
  • And add this amount to the player's score. We can see in all odd rounds, ALICE_SCORE will be updated, and in even rounds, BOB_SCORE will be updated.

Program

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Function to compute who will win the game, if both Alice and Bob play optimally.
int stoneGameVI(vector<int> &aliceValue, vector<int> &bobValue)
{
   // Number of stones.
   int n = aliceValue.size();
   
   // Initialize vector to store the summation of both Alice and Bob's stone values.
   vector<int> sumScore(n);
   
   // Now compute the 'SUM_SCORE' value.
   for (int i = 0; i < n; i++)
   {
       sumScore[i] = aliceValue[i] + bobValue[i];
   }
   
   int x, mn;
   
   // Initialize both 'ALICE_SCORE' and 'BOB_SCORE'.
   int aliceScore = 0, bobScore = 0;
   
   // Loop through the rounds.
   for (int i = 1; i <= n; i++)
   {
       mn = INT_MIN;
       x = -1;
       
       // And in each round find the most optimal stone to pick.
       for (int j = 0; j < n; j++)
       {
           // Check if the stone is previously visited or not.
           if (sumScore[j] != -1 && mn < sumScore[j])
           {
               mn = sumScore[j];
               x = j;
           }
       }
       
       // Mark this stone visited.
       sumScore[x] = -1;
       
       // If it's an odd round update ALICE_SCORE.
       if (i & 1)
       {
           aliceScore += aliceValue[x];
       }
       
       // If it's an even round, update BOB_SCORE.
       else
       {
           bobScore += bobValue[x];
       }
   }
   
   // Check is ALICE_SCORE is greater than BOB_SCORE then return 1.
   if (aliceScore > bobScore)
       return 1;
      
   // And if BOB_SCORE is greater than ALICE_SCORE then return -1.
   else if (aliceScore < bobScore)
       return -1;
       
   // If they both have equal score return 0.
   return 0;
}

int main()
{
   int n;
   cout << "Enter the value of N: ";
   cin >> n;
   
   vector<int> aliceValue(n), bobValue(n);
   cout << "Enter stone values for Alice: ";
   for (int i = 0; i < n; i++)
   {
       cin >> aliceValue[i];
   }
   
   cout << "Enter stone values for Bob: ";
   for (int i = 0; i < n; i++)
   {
       cin >> bobValue[i];
   }
   
   int winner = stoneGameVI(aliceValue, bobValue);
   if (winner == 1)
   {
       cout << "Alice wins.\n";
   }
   else if (winner == -1)
   {
       cout << "Bob wins.\n";
   }
   else
   {
       cout << "Game results in a draw.\n";
   }
   return 0;
}

Input

Enter the value of N: 6
Enter stone values for Alice: 6 3 9 12 1 2 
Enter stone values for Bob:  2 8 4 1 12 18

Output

Bob wins.

Time Complexity

O(N^2), where ‘N’ is the number of stones.

Since each 'N' round takes O(N) time to compute the most optimum stone to pick. Hence the time complexity is O(N^2).

Space Complexity

O(N), where ‘N’ is the number of stones.

Since we are creating an array SUM_SCORE of size ‘N’.

Approach 2- Sorting

As we have seen in the previous approach, we have to find the most optimum stone to pick next, the one with the maximum combined value of Alice and bob. So what we can do is sort the array by SUM_SCORE, and then we will have to pick the stones one by one and add them to ALICE_SCORE and BOB_SCORE. 

Example

Now let’s see the algorithm in depth.

  • Initialize an array of pairs where pair.first will be the sum of stone values and pair.second will be the index.
  • Next, sort this array in descending order.
  • Once you've sorted the array, loop through it and add values of stone alternatively to ALICE_SCORE and BOB_SCORE such that every element at 0,2,4 and even position will be added in ALICE_SCORE, and values at every odd position will be added in BOB_SCORE.
  • Next, compare the scores of Alice and Bob and decide the winner.

Program

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to compute who will win the game if both Alice and Bob play optimally.
int stoneGameVI(vector<int> aliceValue, vector<int> bobValue)
{
   // Number of stones.
   int n = aliceValue.size();
   
   // Initialize vector to store the summation of both Alice and Bob's stone values and corresponding returns indices.
   vector<pair<int, int>> sumScore(n);
   
   // Now compute the SUM_SCORE value.
   for (int i = 0; i < n; i++)
   {
       sumScore[i] = make_pair(aliceValue[i] + bobValue[i], i);
   }
   
   // Sort the SUM_SCORE array by their first values.
   sort(sumScore.begin(), sumScore.end(), greater<pair<int, int>>());
   
   // Initialize both ALICE_SCORE and BOB_SCORE.
   int aliceScore = 0, bobScore = 0;
   
   // Loop through the SUM_SCORE array.
   for (int i = 0; i < n; i++)
   {
       // If its corresponding returns, an even round update ALICE_SCORE.
       if (i % 2 == 0)
       {
           aliceScore += aliceValue[sumScore[i].second];
       }
       // If it’s an odd round, update BOB_SCORE.
       else
       {
           bobScore += bobValue[sumScore[i].second];
       }
   }
   
   // Check if ALICE_SCORE is greater than BOB_SCORE, then return 1.
   if (aliceScore > bobScore)
       return 1;
       
   // And if BOB_SCORE is greater than the ALICE_SCORE, then return -1.
   else if (aliceScore < bobScore)
       return -1;
       
   // If they both have equal score return 0.
   return 0;
}

int main()
{
   int n;
   cout << "Enter the value of N: ";
   cin >> n;
   
   vector<int> aliceValue(n), bobValue(n);
   cout << "Enter stone values for Alice: ";
   for (int i = 0; i < n; i++)
   {
       cin >> aliceValue[i];
   }
   
   cout << "Enter stone values for Bob: ";
   for (int i = 0; i < n; i++)
   {
       cin >> bobValue[i];
   }
   
   int winner = stoneGameVI(aliceValue, bobValue);
   if (winner == 1)
   {
       cout << "Alice wins\n";
   }
   else if (winner == -1)
   {
       cout << "Bob wins\n";
   }
   else
   {
       cout << "Game results in a draw\n";
   }
}

Input

Enter the value of N: 8
Enter stone values for Alice: 7 2 5 8 1 8 12 1
Enter stone values for Bob:  4 1 3 8 7 11 7 5

Output

Alice wins.

Time Complexity

O(N*log(N)), where ‘N’ is the number of stones.

As we are sorting an array of size 'N', which takes O(N*log(N)) time, and we are looping through the array once and adding values to scores that take O(N) time.

Hence time complexity=O(N*log(N)) + O(N) = O(N * log(N)).

Space Complexity

O(N), where ‘N’ is the number of stones. 

Since we are creating an array SUM_SCORE of size ‘N’.

Approach 3- Multimap

Any sorting algorithm can also be implemented using a map because, in a map, values are sorted by keys. So we'll try to implement the above algorithm using a map. But since the sum of two stone values can be the same so we'll use a multimap.

Let’s see how the algorithm will work.

  • First, we will create a multimap, ‘MP’. 
  • Insert elements in ‘MP’ such that MP.key = ALICE_VALUE[i] + BOB_VALUE[i] and MP.value = i that is the index.
  • Since elements are sorted in the map, we don't have to sort them explicitly.
  • Next, loop through the map and add values to ALICE_SCORE and BOB_SCORE alternatively.
  • Lastly, we will compare the scores of Alice and Bob to find the winner.

Program

#include <iostream>
#include <vector>
#include <map>
using namespace std;

// Function to compute who will win the game if both Alice and Bob play optimally.
int stoneGameVI(vector<int> aliceValue, vector<int> bobValue)
{
   // Number of stones.
   int n = aliceValue.size();
   
   // Initialize the map, 'MP'.
   multimap<int, int> mp;
   
   // Now insert value in 'MP' such that MP.key = ALICE_VALUE[i] + BOB_VALUE[i] and MP.value = i.
   for (int i = 0; i < n; i++)
   {
       mp.insert(make_pair(-(aliceValue[i] + bobValue[i]), i));
   }
  
   // Initialize both 'ALICE_SCORE' and 'BOB_SCORE'.
   int aliceScore = 0, bobScore = 0;
   
   // Boolean to see if it's Alice's turn to play or Bob's turn to play.
   bool flag = true;
   
   //Loop through the map, 'MP'.
   for (auto stone: mp)
   {
       // If the flag is true, we know it's Alice's turn, so we update 'ALICE_SCORE'.
       if (flag)
       {
           aliceScore += aliceValue[stone.second];
       }
       // If the flag is false, we know it's Bob's turn, so we update 'BOB_SCORE'.
       else
       {
           bobScore += bobValue[stone.second];
       }
       flag = !flag;
   }
   
   // Check is ALICE_SCORE is greater than BOB_SCORE then return 1.
   if (aliceScore > bobScore)
       return 1;
       
   // And if BOB_SCORE is greater the ALICE_SCORE then return -1.
   else if (aliceScore < bobScore)
       return -1;
       
   // If they both have equal score return 0.
   return 0;
}

int main()
{
   int n;
   cout << "Enter the value of N: ";
   cin >> n;
   
   vector<int> aliceValue(n), bobValue(n);
   cout << "Enter stone values for Alice: ";
   for (int i = 0; i < n; i++)
   {
       cin >> aliceValue[i];
   }
   
   cout << "Enter stone values for Bob: ";
   for (int i = 0; i < n; i++)
   {
       cin >> bobValue[i];
   }
   
   int winner = stoneGameVI(aliceValue, bobValue);
   if (winner == 1)
   {
       cout << "Alice wins\n";
   }
   else if (winner == -1)
   {
       cout << "Bob wins\n";
   }
   else
   {
       cout << "Game results in a draw\n";
   }
}

Input

Enter the value of N: 6
Enter stone values for Alice: 7 2 5 8 1 8 
Enter stone values for Bob:   4 1 3 8 7 11

Output

Alice wins.

Time Complexity

O(N*log(N)), where ‘N’ is the number of stones.

We are creating a multimap, and insertion in multimap takes O(N*log(N)) time.

Space Complexity

O(N), where ‘N’ is the number of stones. 

Since we are creating a multimap MP of size ‘N’.

Key Takeaways

We've seen how to approach an array problem and determine whether sorting can help; if so, we can usually implement it with a map or a multimap.

On the Coding Ninjas Platform, we have a variety of such problems and blogs. Additionally, Coding Ninjas recently introduced the CodeStudio Test Series, a mainly developed test series for acing tech interviews.

Thanks for reading. I hope you’ve gained a lot from this blog.

Was this article helpful ?
0 upvotes