Bag of Tokens

Problem Statement

In this challenge, you begin with a given amount of "power," a score initialized to '0', and an array of values referred to as "tokens." Each value in the tokens array represents a distinct token. Your objective is to reach the highest possible score by strategically using these tokens. There are two specific moves available:

• Face-up: If your power is sufficient (i.e., equals or exceeds the value of the token), you can play the token in a face-up position, which decreases your power by the token’s value but increases your score by one.
• Face-down: If your score is at least one (indicating you've previously earned a score from playing another token face-up), you can play a token face-down. This move increases your power by the token's value but costs you one score.

The final return value should be the maximum score achievable through any sequence of plays.

Examples

Example 1

Input:

tokens = [100], power = 50

Output:

0

Explanation**:**

Since your score is `0` initially, you cannot play the token face-down. You also cannot play it face-up since your power (`50`) is less than `tokens[0]` (`100`).

Example 2

Input:

tokens = [200,100], power = 150

Output:

1

Explanation:

Play token*1* (`100`) face-up, reducing your power to `50` and increasing your score to `1`.

There is no need to play token*0*, since you cannot play it face-up to add to your score. The maximum score achievable is `1`.

Example 3

Input:

tokens = [100,200,300,400], power = 200

Output:

2

Explanation:

Play the tokens in this order to get a score of `2`:

1. Play token*0* (`100`) face-up, reducing power to `100` and increasing score to `1`.
2. Play token*3* (`400`) face-down, increasing power to `500` and reducing score to `0`.
3. Play token*1* (`200`) face-up, reducing power to `300` and increasing score to `1`.
4. Play token*2* (`300`) face-up, reducing power to `0` and increasing score to `2`.

The maximum score achievable is `2`.

Constraints

• 0 <= tokens.length <= 1000
• 0 <= tokens[i], power < 104

Approach and Intuition

Understanding the problem involves recognizing that it blends elements of resource management (power and score) with decision-making to maximize an outcome (the score). Here's an optimal way to think about approaching the problem:

1. Sort the Token Array: Start by sorting the tokens. Lower values should ideally be used face-up to quickly gain scores without losing too much power, and higher values can be reserved for face-down plays if needed to regain power.

2. Implement a Two-pointer Technique: By initiating one pointer at the start (to potentially play face-up for not losing much power and gaining scores) and another at the end (for potentially playing face-down to gain significant power if your score allows it), you can efficiently decide the order of play.

3. Maximize Score by Strategic Play:

   • Play the lowest token face-up if your power allows. This minimizes power reduction while increasing the score.
   • If you find yourself unable to play the next lowest token face-up due to insufficient power but have at least one score, consider playing the highest token face-down. This will increase your power significantly at the expense of reducing your score momentarily.
   • Repeat this strategy, adjusting power and scoring tactically, maximizing score capability by leveraging the trade-offs between the two move options.

4. Edge Cases:

   • If the array is empty, the highest score is obviously 0.
   • If all tokens are greater than the available power and the score is 0, no moves can be made, and the result remains 0.

This logic effectively incorporates greedy methodology for initial moves (lower tokens face-up) and strategic recovery (higher tokens face-down) to optimize end results.

Solutions

class Solution {
public:
    int maxScore(vector<int>& coins, int energy) {
        int points = 0;
        sort(coins.begin(), coins.end());
        deque<int> tokenDeck(coins.begin(), coins.end());
    
        while (!tokenDeck.empty()) {
            if (energy >= tokenDeck.front()) {
                energy -= tokenDeck.front();
                tokenDeck.pop_front();
                points += 1;
            } else if (tokenDeck.size() > 1 && points > 0) {
                energy += tokenDeck.back();
                tokenDeck.pop_back();
                points -= 1;
            } else {
                return points;
            }
        }
        return points;
    }
};