Leetcode 1686: Stone Game VI
Alice and Bob take turns playing a game with a pile of
n stones, each having a value assigned by both players. They play optimally and aim to maximize their total points by choosing stones with the highest value for each player.Problem
Approach
Steps
Complexity
Input: Two arrays are given: `aliceValues` and `bobValues`. Both arrays represent how Alice and Bob value the stones, respectively. Each player will pick stones optimally to maximize their score.
Example: aliceValues = [3, 2], bobValues = [1, 4]
Constraints:
• 1 <= n <= 10^5
• 1 <= aliceValues[i], bobValues[i] <= 100
Output: Return `1` if Alice wins, `-1` if Bob wins, or `0` if the game results in a draw.
Example: Output: 1
Constraints:
Goal: Calculate the optimal moves for Alice and Bob and determine the winner based on the total scores.
Steps:
• Use a priority queue to prioritize stones based on their combined value to both players.
• Simulate the turns, assigning points to Alice and Bob based on the stone they pick, starting with Alice.
Goal: The input arrays `aliceValues` and `bobValues` must have equal length and contain values between 1 and 100.
Steps:
• n == aliceValues.length == bobValues.length
• 1 <= n <= 10^5
• 1 <= aliceValues[i], bobValues[i] <= 100
Assumptions:
• Both players play optimally and have full knowledge of each other's values.
• Input: Input: aliceValues = [5, 1], bobValues = [3, 6]
• Explanation: Alice starts first and chooses the stone with value 5. Bob then takes the stone with value 6. The final score comparison shows Bob winning.
Approach: The goal is to maximize the total points for each player by taking the stones with the highest combined value first.
Observations:
• Both players can see each other's values, and they will prioritize stones based on their combined value.
• Simulate the game using a priority queue where each turn picks the stone with the maximum combined value for both players.
Steps:
• Create a priority queue that holds the stones and their combined values from both players.
• Simulate the game by alternating between Alice and Bob, assigning them the points from the stones they pick.
Empty Inputs:
• The input arrays should never be empty as per the problem constraints.
Large Inputs:
• For large inputs (up to 10^5 stones), ensure that the solution remains efficient.
Special Values:
• If all the values in both arrays are the same, the game will always result in a draw.
Constraints:
• The solution must efficiently handle the maximum array size of 10^5.
int stoneGameVI(vector<int>& alice, vector<int>& bob) {
int ap = 0, bp = 0;
int n = alice.size();
/*
Take out stones with max points (alice[i] + bob[i])
It either increase our winning chance
or reduces the opponents winning chance
*/
priority_queue<pair<int,int>, vector<pair<int,int>>, less<pair<int,int>>> pq;
for(int i = 0; i < n; i++) {
pq.push({alice[i] + bob[i], i});
}
bool isA = true;
while(!pq.empty()) {
auto tmp = pq.top();
pq.pop();
if(isA) {
ap += alice[tmp.second];
} else {
bp += bob[tmp.second];
}
isA = !isA;
}
// cout << ap << " " << bp;
return ap > bp ? 1 : ap < bp ? -1: 0;
}
1 : Function Definition
int stoneGameVI(vector<int>& alice, vector<int>& bob) {
Define the function 'stoneGameVI' that takes two vectors 'alice' and 'bob', representing the points for each player on each stone, and returns the outcome of the game.
2 : Variable Initialization
int ap = 0, bp = 0;
Initialize variables 'ap' and 'bp' to 0. These will hold the cumulative scores for Alice and Bob, respectively.
3 : Size Calculation
int n = alice.size();
Determine the size of the 'alice' vector, which is the same as the 'bob' vector, and store it in variable 'n'.
4 : Priority Queue Declaration
priority_queue<pair<int,int>, vector<pair<int,int>>, less<pair<int,int>>> pq;
Declare a priority queue 'pq' to store pairs of integers, where the first value is the combined score of a stone (alice[i] + bob[i]) and the second value is the index of the stone. The queue is sorted in descending order based on the combined score.
5 : Loop Through Stones
for(int i = 0; i < n; i++) {
Start a loop to iterate through all the stones.
6 : Push to Priority Queue
pq.push({alice[i] + bob[i], i});
Push a pair consisting of the combined score of the stone (alice[i] + bob[i]) and its index into the priority queue.
7 : Turn Indicator
bool isA = true;
Initialize a boolean variable 'isA' to true, indicating that it's Alice's turn to pick a stone.
8 : While Loop
while(!pq.empty()) {
Start a while loop that continues until the priority queue is empty, meaning all stones have been picked.
9 : Get Top Stone
auto tmp = pq.top();
Get the stone with the highest combined score (top of the priority queue).
10 : Pop from Priority Queue
pq.pop();
Remove the top stone from the priority queue.
11 : Check Turn
if(isA) {
If it's Alice's turn (isA is true), proceed to update Alice's score.
12 : Update Alice's Score
ap += alice[tmp.second];
Add the score of the current stone for Alice (alice[tmp.second]) to her total score (ap).
13 : Else Condition
} else {
If it's not Alice's turn (it's Bob's turn), update Bob's score.
14 : Update Bob's Score
bp += bob[tmp.second];
Add the score of the current stone for Bob (bob[tmp.second]) to his total score (bp).
15 : Toggle Turn
isA = !isA;
Toggle the turn indicator (isA) to switch turns between Alice and Bob.
16 : Return Statement
return ap > bp ? 1 : ap < bp ? -1: 0;
Return 1 if Alice has a higher score than Bob, -1 if Bob has a higher score, or 0 if their scores are equal (a draw).
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is O(n log n) due to the priority queue operations.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) to store the priority queue and other intermediate data.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus