We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Stone Game VI

Number: 1788

Difficulty: Medium

Paid? No

Companies: Arcesium

Problem Description

Alice and Bob play a game where they alternately remove stones from a pile. Each stone has two different values: one for Alice and one for Bob. When a player removes a stone, they add the corresponding stone's value (according to their own valuation) to their score. The players play optimally, and the goal is to determine the winner by comparing the final scores. If Alice’s score is higher, return 1; if Bob’s score is higher, return -1; otherwise, return 0.

Key Insights

  • Both players know the value of each stone from both perspectives.
  • Sorting stones by the sum of both players' values (aliceValues[i] + bobValues[i]) in descending order maximizes the potential points swing.
  • On each turn, the currently active player takes the best available option from the sorted order.
  • Simulation of stone picks in sorted order reflects optimal gameplay for both players.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the stones based on combined values. Space Complexity: O(n) for storing the combined stone values and indices.

Solution

The fundamental idea is to sort the stones by the total value that both players can obtain (i.e., aliceValues[i] + bobValues[i]) in descending order. This is because stones with a higher combined value are more critical in affecting the outcome, and both players will prioritize them.

After sorting:

  • Simulate the turns. Since Alice starts, she picks all stones at even indices of the sorted list while Bob picks those at odd indices.
  • Each player accumulates their score based on their own valuation for their chosen stones.
  • After all moves, compare the scores:
    • If Alice’s score is higher, she wins.
    • If Bob’s score is higher, he wins.
    • Otherwise, it’s a draw.

This approach guarantees that both players are playing optimally under the assumption of a greedy strategy driven by the combined value of each stone.

Code Solutions

# Python solution for Stone Game VI

def stoneGameVI(aliceValues, bobValues):
    n = len(aliceValues)
    # Create a list of tuples: (combined_value, alice_value, bob_value)
    stones = [(aliceValues[i] + bobValues[i], aliceValues[i], bobValues[i]) for i in range(n)]
    # Sort stones in descending order by combined value
    stones.sort(key=lambda x: x[0], reverse=True)

    aliceScore, bobScore = 0, 0
    # Simulate picking the stones in sorted order. Alice picks first.
    for i, stone in enumerate(stones):
        if i % 2 == 0:  # Alice's turn
            aliceScore += stone[1]
        else:           # Bob's turn
            bobScore += stone[2]

    # Compare final scores to determine the outcome
    if aliceScore > bobScore:
        return 1
    elif bobScore > aliceScore:
        return -1
    else:
        return 0

# Example usage:
# result = stoneGameVI([1,3], [2,1])
# print(result)  # Output should be 1 if Alice wins.
← Back to All Questions