<p>You are given an integer array <code>rewardValues</code> of length <code>n</code>, representing the values of rewards.</p>

<p>Initially, your total reward <code>x</code> is 0, and all indices are <strong>unmarked</strong>. You are allowed to perform the following operation <strong>any</strong> number of times:</p>

<ul>
	<li>Choose an <strong>unmarked</strong> index <code>i</code> from the range <code>[0, n - 1]</code>.</li>
	<li>If <code>rewardValues[i]</code> is <strong>greater</strong> than your current total reward <code>x</code>, then add <code>rewardValues[i]</code> to <code>x</code> (i.e., <code>x = x + rewardValues[i]</code>), and <strong>mark</strong> the index <code>i</code>.</li>
</ul>

<p>Return an integer denoting the <strong>maximum </strong><em>total reward</em> you can collect by performing the operations optimally.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">rewardValues = [1,1,3,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<p>During the operations, we can choose to mark the indices 0 and 2 in order, and the total reward will be 4, which is the maximum.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">rewardValues = [1,6,4,3,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">11</span></p>

<p><strong>Explanation:</strong></p>

<p>Mark the indices 0, 2, and 1 in order. The total reward will then be 11, which is the maximum.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rewardValues.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= rewardValues[i] &lt;= 5 * 10<sup>4</sup></code></li>
</ul>

class Solution:
    def maxTotalReward(self, rewards: List[int]) -> int:

        # Inspired by this write-up
        # https://leetcode.com/problems/maximum-total-reward-using-operations-ii/solutions/5282370/bitset-trick-include-similar-question/

        #
        # You don't have to keep duplicates, but doing so won't invalidate this.
        # This is because the question has two red herrings:
        #
        #   - "You can do an operation any number of times" => you can only use one idx because
        #     right after, it mentions "choosing an unmarked index" which necessarily means the
        #     indices (aka individual reward positions) can only be used one
        #
        #   - You can only choose reward values greater than the current accrued sum. Because
        #     for all reward values r, assuming current accrued reward x satisfies x < r, taking
        #     the reward will always invalidate future reward values of the same size.
        #
        #     In other words, if you have rewards = [1,2,4,10,10,10,10,10], and then collect
        #     1, 2, and then 4 and get 7, it doesn't matter which or how many "10"s you then pick:
        #     because every value in the array is positive, you will never be able to add 10 to
        #     anything and still be less than 10.
        #
        #     Therefore, we will only ever be able to take a unique cardinal value once.
        #
        # The metagame behind contest questions is that they are oftentimes existing LC questions
        # but reskinned with red herrings meant to distract you. The game is now decloaking these.
        #
        # This is inevitable: there are over 3000 questions on the site! Per pigeonhole principle,
        # you're bound to see something again eventually.
        #
        rewards = sorted(set(rewards))

        #
        # We use a bitset instead of a normal set, where the existence of an element n in the set
        # is represented as the presence of a 1-bit at offset (1 << n).
        #
        # We want to iterate over the elements in the set, so we must include an identity element.
        # In this case, that identity element is the sum of 0, our starting point. We thus use
        # 0-indexing for this bitset's data representation, which means 0b00000001 is our initial.
        #
        all_total_reward_sums = 1  # Or 0b00000001 if you want to be explicit

        for reward in rewards:
            
            #
            # Let reward be represented by (1 << r), aka a single bit set r positions left.
            #
            #   0b0000010000000
            #
            # Every number that is less than this reward is to the right. When we have a single
            # bit and want every bit to its right, we subtract 1:
            #
            #   0b0000001111111
            #
            # Therefore, only the values in all_total_reward_sums at those positions 1 are valid.
            #
            mask = (1 << reward) - 1

            #
            # Given number n in the bitset, adding 1 to n would result in a number at the position
            # to its immediate left. If n is 10, then its position is (1 << 10). If n is 11, then
            # it's (1 << 11). In order to therefore add 5 to 10, we set (1 << 15).
            #
            # This means given the group of "valid" positions we just calculated, we can instantly
            # calculate the sums of all of them by shifting the entire group by the value of the
            # reward:
            #
            #   0b0000011111     Group consisting of [0, 1, 2, 3, 4]
            #   0b1111100000     To add 5 to this and get [5, 6, 7, 8, 9], we shift 5 left
            #
            # We take the group of valid existing elements by performing AND with the mask with the
            # elements strictly less than current reward.
            #
            valid_existing_elements = mask & all_total_reward_sums

            #
            # We then perform shift by the reward, `reward` positions left.
            # We take the answer and perform the bitwise OR in order to add the elements, but not
            # removing them as future elements may want to use the previous elements as alternate
            # decision points in our "bitset DP".
            #
            all_total_reward_sums |= (valid_existing_elements << reward)
        
        #
        # What we have left is a large set containing every possible total reward value. In Python
        # you find the first set bit (ftz) by performing (n & -n).bit_length() - 1, but to find the
        # last set bit (aka the largest element in the bitset), we need the bit_length() - 1.
        #
        # This is because for positive ints, Python only needs space to store the highest set bit,
        # so for 0b101001 the bit_length() is 6 which means the highest set bit is at position 6.
        # As we use this bitset with zero-indexing, this means the actual value is 1 fewer.
        #
        return all_total_reward_sums.bit_length() - 1
25200