A solution for this problem. It is recommended that you read through and attempt the problem for a while.

In hindsight, this algorithm is rather inefficient.

We first observe that N, the number of cards is very small - 13. An \(O( 3^N )\) solution will pass. So will a \(O(N^{2}2^{N})\). As with many problems, it helps to first ensure some quality is constant. Let’s fix the cards that we will lose/not lose - there are \(2^N\) possible combinations because each of the N bids has 2 different states.

# Aside

We can think of these combinations as a string of 0s and 1s (aka a “bitmask”) - a character is 0 if we lose the corresponding card, 1 if we don’t. In practice, bitmasks can be represented by integers (because the machine also stores them as sequences of 0s and 1s). So iterating through all possible masks of size 13 corresponds to iterating through all binary integers 0000000000000 to 1111111111111.

# Back to the main solution

If we know we are going to lose some number (\(L\)) of cards, clearly we should not be wasting valuable bids on them. In other words we’ll assign our worst bids (\(1,2,3...L\)) to the \(L\) cards we will lose.

Now, for the remaining cards we know we MUST win/draw the card. At this point we have \(N-L\) bids left: \(L+1,L+2...N\).

Claim: It is optimal to assign L+1 to the lowest opponent bid, L+2 to the second lowest bid…etc… Explanation: The claim can be rephrased as if bid i < j, then value of the card assigned to i must be < value of card assigned to j. Let’s say this wasn’t the case for some i,j. You can easily swap i, j without affecting your overall profit.

After this it is a matter of simulating the above process \(2^N\) times (\(O(NlogN)\) each time) and outputting your maximum profit.

An extra nuance: in some cases we might assume we have “lost” some cards when it is possible to not lose these cards. This does not affect the correctness of the solution as the solution would then be found in other cases where we assume we don’t lose those cards.

Formal proof and implementation is left as an exercise to the reader (I promise, it’s not that bad).