Card Pairing
Contest: Educational Codeforces Round 165 (Rated for Div. 2)
Difficulty rating: 3000
Tags: dp, greedy, hashing, implementation

There is a deck of $$$n$$$ cards, each card has one of $$$k$$$ types. You are given the sequence $$$a_1, a_2, \dots, a_n$$$ denoting the types of cards in the deck from top to bottom. Both $$$n$$$ and $$$k$$$ are even numbers.

You play a game with these cards. First, you draw $$$k$$$ topmost cards from the deck. Then, the following happens each turn of the game:

- you choose exactly two cards from your hand and play them. If these cards have the same type, you earn a coin;
- then, if the deck is not empty, you draw exactly two top cards from it;
- then, if both your hand and your deck are empty, the game ends. Otherwise, the new turn begins.

You have to calculate the maximum number of coins you can earn during the game.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 1000$$$, both $$$n$$$ and $$$k$$$ are even).

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$).

Output format:
Print one integer — the maximum number of coins you can earn.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
4 2
1 2 1 2

Example output:
0

Example input:
8 2
2 1 2 2 1 2 1 2

Example output:
1

Editorial:
It's pretty obvious that every time we have a pair of equal cards in hand, we should play one of these pairs. If you're interested in a formal proof, please read the paragraph in italic, otherwise skip it.
Formal proof: suppose we have a pair of cards of type $$$x$$$, but we play a card of type $$$y$$$ and a card of type $$$z$$$ in the optimal solution, where $$$z \ne x$$$ and $$$z \ne y$$$. Let's show that playing a pair of cards of type $$$x$$$ can also be optimal. If $$$y = x$$$, then let's find the next moment when we play a card of type $$$x$$$. By swapping that card with a card of type $$$z$$$, we "fix" the current pair and possibly "break" the pair from which we took the card of type $$$x$$$, so our number of coins won't go down.
If $$$y \ne x$$$, almost the same proof can be used: find the first two cards of type $$$x$$$ we play after that moment. Either they are played at the same moment, then we can swap the pairs we used at the current moment and at that moment. Or they are played at different moments $$$t_1$$$ and $$$t_2$$$; by swapping these two cards with cards of type $$$y$$$ and $$$z$$$, we "fix" the pair we played at the current moment, we might "break" the pair played at the moment $$$t_2$$$, but we cannot "break" the pair played at the moment $$$t_1$$$, since the cards played at that moment are different.
Whenever we have a pair of equal cards, we will always play it at some moment and earn a coin, and it does not matter in which order we play different pairs. So we have to make a meaningful choice about which cards we play only when all $$$k$$$ cards in our hand are different.
In the ideal situation, if there are $$$c_i$$$ cards of type $$$i$$$, we want to earn $$$\lfloor\frac{c_i}{2}\rfloor$$$ coins by playing these cards. But whenever we play only one card of type $$$i$$$ and there is an odd number of cards of type $$$i$$$ left (both in hand and in deck), we "lose" a coin, because the number of pairs we can make decreases by $$$1$$$. Let's calculate the answer as the maximum possible number of pairs we can form (equal to $$$\sum\limits_{i=1}^{k} \lfloor\frac{c_i}{2}\rfloor$$$), minus the minimum number of coins we "lose" in such a way.
Since we play a pair when we have at least one pair, we can "lose" coins only when all cards in our hand are different. So, let's try to use a dynamic programming of the form: $$$dp_i$$$ is the minimum number of coins we could lose when we have drawn $$$i$$$ first cards from the deck, and all cards in our hand are different.
Let's analyze the transitions of this dynamic programming. When transitioning out of $$$dp_i$$$, we can iterate on the pair of cards we play (since we consider the situation when all cards in our hand are different, we can play any pair of different cards); for each of these two cards, check if we "lose" a coin by playing them, and try to find the next moment when all $$$k$$$ cards in our hand will be different (or update the answer if there is no such moment).
However, when implemented naively, it is too slow (might take up to $$$O(n^5)$$$). We can use the following optimizations to improve it:
• XOR Hashing: this is one of my favorite techniques. Let's assign each card type a random $$$64$$$-bit number (let it be $$$h_i$$$ for type $$$i$$$). Then, let $$$p_i$$$ be the XOR of the numbers assigned to the first $$$i$$$ cards in the deck. Suppose we are considering transitions from $$$dp_i$$$; we try to play cards of type $$$x$$$ and $$$y$$$; when will be the next moment when we have all $$$k$$$ types of cards? If this moment is $$$j$$$, then we need to take an odd number of cards of type $$$x$$$ and $$$y$$$ from moment $$$i$$$ to moment $$$j$$$, and an even number of cards for all other types. So, we can see that $$$p_j = p_i \oplus h_x \oplus h_y$$$, and this allows us to locate the next moment when we have $$$k$$$ different cards more easily, in $$$O(n)$$$ or even $$$O(\log n)$$$.
• Reducing the number of transitions: we have up to $$$O(k^2)$$$ pairs of cards we can play from each state, but only $$$O(n)$$$ different states we can go into, and no two transitions lead to the same state. Let's try to make only $$$O(n)$$$ transitions from each state. When considering a state, we can split all $$$k$$$ cards into two types: the ones that make us lose a coin when we play them (group $$$1$$$), and all the others (group $$$2$$$). First, let's try to play two cards from the group $$$2$$$; if we find a combination of them such that, after playing it, we never have $$$k$$$ different cards in our hand — we don't need any other transitions from this state, because this transition updates the answer directly without any increases. Otherwise, perform all transitions with pairs of cards from group $$$2$$$, and try to play a pair of cards from different groups. If we find a combination that updates the answer directly, we again can stop considering transitions, the next transitions we use won't be more optimal. And then we do the same with transitions where we use a pair of cards of group $$$1$$$. This way, we will consider at most $$$n+1$$$ transitions from each state.
Combining these two optimizations results in a solution in $$$O(n^3)$$$ or $$$O(n^2 \log n)$$$, but there are other optimizations you can try.