Card Algorithm Game

Question

I was playing with the following problem and have a brute force approach but could not come up with a nice solution. The problem is as follows:

There are 2*N cards. You and your opponent split them up (N cards to you and N to them). You know exactly what cards they have and what order they will play them in.

The rules of the game are as follows: For the first N/2 rounds, the person with the highest card wins and for last N/2 rounds, the person with the lowest card wins.

Given these rules and the order your opponents plays there cards, what is the maximum amount of wins you can get.

Example:

You have the cards: 2, 5, 6, 7. Your opponent has the cards: 1, 8, 4, 3 and plays them in that order.

The maximum score you can get is 2 since you play a 7 to their 1, lose the 2nd and 3rd round, and then play 2 in the last round to win.

My ideas: split your cards into two piles, your larger numbered and lower numbered ones. Then figure out an optimum matching up.

Pseudocode/algorithmic ideas would be greatly appreciated.

EDITS: There are a total of N rounds. The first N/2 rounds: the higher card wins. The last N/2 rounds: the lower card wins. N must be even.

Answer 1

I suggest:

• Split your cards in 2 piles greater/lower
• sort them
• Sort greater cards of opponent by value (first rounds)
• from biggest to lower opponent card:
  if your remaining max is lower than opponent card, play lowest card (Lose)
  else play your highest card (Win)

Similar for lower pile, inverting order.

Answer 2

First, create an array of N items (one per round). Each item is a list of "winning cards" for that round, i.e. the set of your cards which would win that round. In your example, you'd get {{2567},{},{2},{2}}.

The following list gives some situations in which a card should be "assigned" to a round. This means that we decide that we'll play that card on that round and nothing can change that afterwards. After a card is assigned, the algorithm should go on after removing the assigned round from the set of rounds and the assigned card from the set of winning cards for any round.

It should be obvious that applying any of these rules in any situation would never reduce the number of possible wins, so applying them as much as possible before starting brute force is always a good idea.

• If card C can win round R, and card C can win no other round, assign card C to round R.
• If card C can't win in any round, and round R can't be won by any card, assign card C to round R.
• If card C can win in some of the first N/2 rounds, but card C can't win in any of the last N/2 rounds, and card C is the highest of your cards that has this property, assign card C to the most difficult round in which it wins (i.e. the highest of your opponent's cards to which card C wins).
• If card C can win in some of the last N/2 rounds, but card C can't win in any of the first N/2 rounds, and card C is the lowest of your cards that has this property, assign card C to the most difficult round in which it wins (i.e. the lowest of your opponent's cards to which card C wins).

Note that assigning a card to a round changes both the rounds and the cards that win in each round, so even if one of these rules is not applicable, it could become applicable after applying some other rule. So they must be tried iteratively until a full iteration on all of them produces no new assignments.

This is not a definitive solution but it surely will make things much easier for the final bruteforce step.