Playing with a card algorithm

Question

I played with the following problem and had brute force, but could not find a suitable solution. The problem is this:

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

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

Given these rules and the order in which your opponents play cards there, what is the maximum amount of winnings that you can get.

Example:

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

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

My ideas: divide your cards into two piles, your larger and lower numbers. Then determine the optimal match.

Pseudo-code / algorithmic ideas are welcome.

EDIT: A total of N rounds. First N / 2 rounds: win wins. Last N / 2 rounds: win the bottom card. N must be even.

Answer 1

I suggest:

• Divide your cards into 2 piles larger / lower
• sort them
• Sorting large enemy cards by value (first rounds)
• from card to nearest card:
  if your remaining max is less than the opponent’s card, play the lowest card (Lose)
  otherwise play your highest card (Win)

Similarly for the bottom pile, inverting the order.

Answer 2

First, create an array of N elements (one per round). Each element is a list of "winning cards" for this round, i.e. Set of your cards to win this round. In your example, you will get {{2567},{},{2},{2}} .

The following list shows some situations in which a card must be “assigned” to a round. This means that we decide that we will play this card in this round, and after that nothing will change. After a card is assigned, the algorithm should continue after removing the assigned round from the set of rounds and the assigned card from the set of winning cards for any round.

Obviously, applying any of these rules in any situation will never reduce the number of possible victories, so making the most of them before starting brute force is always a good idea.

• If card C can win round R and card C cannot win any other round, assign card C to round R.
• If card C cannot win in any round, and round R cannot win on any card, assign card C to round R.
• If card C can win in some first N / 2 rounds, but card C cannot 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 very the difficult round in which she wins (i.e. the highest of your opponent’s cards with which card C wins).
• If card C can win in some of the last N / 2 rounds, but card C cannot 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 the difficult round in which he wins (i.e. the lowest of your opponent cards to which card C wins).

Please note: when assigning a card to a round, both the rounds and the cards that win in each round change, therefore, even if one of these rules is not applicable, it may become applicable after applying any other rule. Thus, they should be tried iteratively until a complete iteration on all of them leads to new assignments.

This is not the final decision, but, of course, it will facilitate the process of the final step of brute force.