AlgoMaster Sheet – Maximum Score From Removing Stones

Problem Statement: You are playing a solitaire game with three piles of stones of sizes a​​​​​​, b,​​​​​​ and c​​​​​​ respectively. Each turn you choose two different non-empty piles, take one stone from each, and add 1 point to your score. The game stops when there are fewer than two non-empty piles (meaning there are no more available moves).

Given three integers a​​​​​, b,​​​​​ and c​​​​​, return the maximum score you can get.

Example 1:

Input: a = 2, b = 4, c = 6
Output: 6
Explanation: The starting state is (2, 4, 6). One optimal set of moves is:
- Take from 1st and 3rd piles, state is now (1, 4, 5)
- Take from 1st and 3rd piles, state is now (0, 4, 4)
- Take from 2nd and 3rd piles, state is now (0, 3, 3)
- Take from 2nd and 3rd piles, state is now (0, 2, 2)
- Take from 2nd and 3rd piles, state is now (0, 1, 1)
- Take from 2nd and 3rd piles, state is now (0, 0, 0)
There are fewer than two non-empty piles, so the game ends. Total: 6 points.

Example 2:

Input: a = 4, b = 4, c = 6
Output: 7
Explanation: The starting state is (4, 4, 6). One optimal set of moves is:
- Take from 1st and 2nd piles, state is now (3, 3, 6)
- Take from 1st and 3rd piles, state is now (2, 3, 5)
- Take from 1st and 3rd piles, state is now (1, 3, 4)
- Take from 1st and 3rd piles, state is now (0, 3, 3)
- Take from 2nd and 3rd piles, state is now (0, 2, 2)
- Take from 2nd and 3rd piles, state is now (0, 1, 1)
- Take from 2nd and 3rd piles, state is now (0, 0, 0)
There are fewer than two non-empty piles, so the game ends. Total: 7 points.

Example 3:

Input: a = 1, b = 8, c = 8
Output: 8
Explanation: One optimal set of moves is to take from the 2nd and 3rd piles for 8 turns until they are empty.
After that, there are fewer than two non-empty piles, so the game ends.

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Practice Questions   Maximum Score From Removing Stones

Solution 1: Greedy Approach

As we need to maximize the score we need to think greedily. At every move, we will always choose the pile with the maximum number of stones and the pile with the second maximum number of stones. This approach will always lead to the maximum score. We can use a priority queue/heap to implement this approach : 

• Declare ans and initialize it with zero.
• Insert size of three piles of stones in a priority queue/heap.
• Run a loop till the priority queue/heap contains only one pile with non zero stones
  • Extract the second largest and largest pile of stones.
  • Remove them from the priority queue/heap.
  • Decrease the size of both piles of stones by 1. Insert them back in the priority queue/heap.
  • Increase ans by 1.
• Return ans .

Time Complexity: of the solution: O(k logn), where k is the answer which is how many times the while loop runs.
Space Complexity: O(n)

#include <bits/stdc++.h>
using namespace std;
int maximumScore(int a, int b, int c)
{
    // we will make a max heap and push all the elements into it
    priority_queue<int> basket;
    basket.push(a);
    basket.push(b);
    basket.push(c);
    int ans = 0;     //make ans = 0

    // we will pop the top most elements of the heap(top max element)
    // subtract one from each of them and insert them again in the heap, if they are not equal to 0
    //  we will continue the same operation until the size of the basket remains greater than 1
    while (basket.size() > 1)
    {
        // taking the top 2 greater elements out of the max heap
        int left = basket.top();
        basket.pop();
        int right = basket.top();
        basket.pop();

        // subtracting one from each of the greatest elements
        left--;
        right--;

        // increasing the answer score at each iteration of the loop
        ans++;

        // if the elements that we took out are still greater than 1 after subtraction operation then we have to insert them again
        if (left != 0)
            basket.push(left);
        if (right != 0)
            basket.push(right);
    }
    //return ans
    return ans;
};

int main()
{
    cout << "Enter  three piles of stones of sizes: " << endl;
    int piles1, piles2, piles3;
    cin >> piles1 >> piles2 >> piles3;            //{4, 4, 6}
    cout << "There are fewer than two non-empty piles, so the game ends. Total: " << maximumScore(piles1, piles2, piles3) << " points";
}

Output:

There are fewer than two non-empty piles, so the game ends. Total: 7 points

To master AlgoMaster Sheet – Maximum Score From Removing Stones  in the most efficient and effective way, do check out this:

This article is contributed by : Sayan Dutta to this article on csforall.in