algoadvance

LeetCode Problem 1753: Maximum Score From Removing Stones

You are playing a solitaire game with three piles of stones. Each pile has a positive integer number of stones a, b, and c respectively. The objective of the game is to remove stones in such a way that maximizes your score. In each move, you can choose any two piles and remove one stone from each.

Your score is the total number of stones you have removed. You need to return the maximum score you can obtain.

Clarifying Questions

1. Input Constraints:
   • What are the ranges for a, b, and c?
     • The values of a, b, and c are positive integers ranging from 1 to 10^5.
2. Edge Cases:
   • What if all piles have the same number of stones?
     • The game will proceed as usual until no more pairs of piles have stones left.

Strategy

To maximize the score from removing stones, we can follow these steps:

1. Sort the Piles: First, sort the piles in non-increasing order to simplify the game logic (i.e., make sure a >= b >= c after sorting).

2. Remove Stones from Two Largest Piles: Always remove stones from the two largest piles. This approach works because it maximizes the number of moves before any pile becomes empty.

3. Adjust the Piles: After each removal, re-sort the piles to maintain the non-increasing order property.

4. Termination Condition: The game stops when one or more piles have no stones left or when no pairs of piles with stones can be found.

Algorithm:

1. Sort a, b, and c in non-increasing order.
2. While there are at least two piles with stones:
   • Remove one stone each from the two largest piles.
   • Re-sort the piles.
3. Count the total number of removed stones and return that as the score.

Time Complexity

• Sorting the piles after each removal operation may seem expensive but because we are only sorting three elements, this is effectively a constant time operation.
• Therefore, the overall time complexity is O(a + b + c), where a, b, and c are the sizes of the piles since we perform a constant time operation per each removal.

def maximumScore(a: int, b: int, c: int) -> int:
    # Initial piles of stones
    piles = sorted([a, b, c], reverse=True)
    score = 0

    while piles[1] > 0:  # We need at least two non-zero piles to continue
        # Take one stone from the two largest piles
        piles[0] -= 1
        piles[1] -= 1
        # Increase the score by one
        score += 1
        # Re-sort the piles after removing one stone from the two largest
        piles = sorted(piles, reverse=True)
    
    return score

# Example usage
print(maximumScore(2, 4, 6))  # Expected output: 6
print(maximumScore(4, 4, 6))  # Expected output: 7
print(maximumScore(1, 8, 8))  # Expected output: 8

Here is a Python implementation for the problem following the strategy outlined above. The code first sorts the stones, and then continuously removes one stone from the two largest piles, re-sorts the piles, and increments the score until no more pairs with stones can be selected.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?