Boring Card Game
Contest: Codeforces Global Round 11
Difficulty rating: 3200
Tags: data structures, greedy, trees

When they are bored, Federico and Giada often play the following card game with a deck containing $$$6n$$$ cards.

Each card contains one number between $$$1$$$ and $$$6n$$$ and each number appears on exactly one card. Initially the deck is sorted, so the first card contains the number $$$1$$$, the second card contains the number $$$2$$$, $$$\dots$$$, and the last one contains the number $$$6n$$$.

Federico and Giada take turns, alternating; Federico starts.

In his turn, the player takes $$$3$$$ contiguous cards from the deck and puts them in his pocket. The order of the cards remaining in the deck is not changed. They play until the deck is empty (after exactly $$$2n$$$ turns). At the end of the game both Federico and Giada have $$$3n$$$ cards in their pockets.

You are given the cards in Federico's pocket at the end of the game. Describe a sequence of moves that produces that set of cards in Federico's pocket.

Input format:
The first line of the input contains one integer $$$n$$$ ($$$1\le n \le 200$$$).

The second line of the input contains $$$3n$$$ numbers $$$x_1, x_2,\ldots, x_{3n}$$$ ($$$1 \le x_1 < x_2 <\ldots < x_{3n} \le 6n$$$) – the cards in Federico's pocket at the end of the game.

It is guaranteed that for each test there is at least one sequence of moves that produces such set of cards in Federico's pocket.

Output format:
Print $$$2n$$$ lines, each containing $$$3$$$ integers.

The $$$i$$$-th line should contain, in increasing order, the integers $$$a_i<b_i<c_i$$$ written on the three cards taken by the player during the $$$i$$$-th turn (so taken by Federico if $$$i$$$ is odd and by Giada if $$$i$$$ is even).

If there is more than one possible sequence of moves, you can print any.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Explanation of the first testcase: Initially the deck has $$$12 = 2\cdot 6$$$ sorted cards, so the deck is $$$[1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12]$$$.

- During turn $$$1$$$, Federico takes the three cards $$$[9\ 10\ 11]$$$. After his move, the deck is $$$[1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 12]$$$.
- During turn $$$2$$$, Giada takes the three cards $$$[6\ 7\ 8]$$$. After her move, the deck is $$$[1\ 2\ 3\ 4\ 5\ 12]$$$.
- During turn $$$3$$$, Federico takes the three cards $$$[2\ 3\ 4]$$$. After his move, the deck is $$$[1\ 5\ 12]$$$.
- During turn $$$4$$$, Giada takes the three cards $$$[1\ 5\ 12]$$$. After her move, the deck is empty.

Example input:
2
2 3 4 9 10 11

Example output:
9 10 11
6 7 8
2 3 4
1 5 12

Example input:
5
1 2 3 4 5 9 11 12 13 18 19 20 21 22 23

Example output:
19 20 21
24 25 26
11 12 13
27 28 29
1 2 3
14 15 16
18 22 23
6 7 8
4 5 9
10 17 30

Editorial:
Before describing the solution, let us comment it.
The solution is naturally split in two parts:
• Solving the problem without the "alternating turns" constraint.
• Noticing that a simple greedy is sufficient to take care of the "alternating turns" constraint.
The first part of the solution is a rather standard greedy approach with complexity $$$O(n)$$$. It is quite easy (considering that this is problem F) to guess that such a greedy approach works. On the other hand, the second part of the solution (i.e. noticing that Giada takes the last turn and this imposes a condition on the appropriate forest provided by the first part of the solution) is still a greedy with $$$O(n)$$$ complexity, but harder to guess and less standard.
The constraint on $$$n$$$ is very low as we did not want to implicitly hint towards a greedy approach. Moreover the greedy used in the first part of the solution can be replaced with an $$$O(n^3)$$$ dynamic-programming approach (which fits in the timelimit if implemented carefully) and the greedy described in the second part of the solution is slightly easier to implement with complexity $$$O(n^2)$$$.
Simpler problem, not alternating turns
Let us first consider a different (and easier) problem. Federico and Giada don't take turns, they take $$$3$$$ cards in the order they prefer (so at the end they may have a different number of cards). You are given a final situation (that is, the cards in Federico's pocket at the end) and you have to produce a sequence of moves that generates that set of cards at the end of the game. We assume that the final situation is fixed, hence each card is assigned to either Federico or Giada.
We are going to describe what is natural to call the stack-partitioning. The stack-partitioning is a particular partition of the deck into $$$2n$$$ groups of $$$3$$$ cards each (not necessarily contiguous) such that each group of cards contain cards taken by the same player (either all $$$3$$$ by Federico or all $$$3$$$ by Giada). A priori the stack-partitioning might fail, not producing the described partition (but we will se that if the set of cards in Federico's pocket is achievable then the stack-partitioning does not fail).
In order to create the stack-partitioning we iterate over the cards in the deck (hence the numbers from $$$1$$$ to $$$6n$$$) and we keep a stack of partial groups (i.e. of groups of less than $$$3$$$ cards). When we process a card,
• if it was taken by the same player that took the cards in the group at the top of the stack, then we add it to that group. If the group has now $$$3$$$ cards, we pop it from the stack and it becomes a group in the stack-partitioning.
• if it was taken by the other player, we add it on top of the stack (as a group with just that card).
For example, if $$$n=2$$$ and the cards in Federico's pocket are $$$\{1,5,8,9,10,12\}$$$ then the stack-partitioning works and produces the partition $$$$$$\{\{2,3,4\},\{8,9,10\},\{6,7,8\},\{1,5,12\}\} \,.$$$$$$
The fundamental observation is:
Lemma: Let us fix a possible final situation. Let us perform the stack-partition starting with a nonempty stack, i.e. at the beginning the stack already contains some partial groups assigned to either Federico and Giada (these groups do not correspond to cards in the deck). At the end of the algorithm the stack will be as it was at the beginning, i.e., same number of partial groups, with same sizes and assigned to the same player.
proof: The proof is by induction on the number of cards in the deck. Since it is not hard and quite standard, we leave it to the reader.
Corollary: A final situation (i.e., a set of cards in Federico's pocket) is possible if and only if the stack-partitioning works. Moreover the stack-partitioning yields a way to produce the final situation.
proof: If the stack-partitioning works, then it clearly yields a way to produce the final situation (players take the groups of three cards in the same order as they are popped out of the stack). The other implication follows directly from the Lemma.
Original problem
Now, we can go back to the original statement. Let us notice a couple more properties of the stack-partitioning (both observations are valid both in the simpler version of the problem and in the harder):
• The stack-partitioning produces a forest where each node is a group of $$$3$$$ cards taken by the same player (hence we will say that a node is owned by Federico or Giada). More precisely any group $$$G$$$ of $$$3$$$ cards is son of the group of $$$3$$$ cards at the top of the stack after $$$G$$$ is popped out (or $$$G$$$ is a root if the stack becomes empty). We will refer to this forest as the stack-forest. Notice that in the stack-forest two adjacent vertices are owned by different players.
• In any possible sequence of moves, the group taken in the last move intersects at least one root of the stack-forest. Indeed, the cards before the first card of the group can be taken independently from the others (without alternating turns) and therefore, thanks to the Lemma, when the first card of the group is processed the stack is empty (thus it belongs to a root).
We prove that a certain final situation is possible if and only if the stack-partitioning works and there is a root of the stack-forest that is owned by Giada.
First, if a situation is possible then the stack-partitioning works (because of the lemma). Moreover, since Giada performs the last move, thanks to the second property above, there must be a root of the stack-forest owned by Giada.
Let us now describe a greedy algorithm to produce a given final situation provided that the stack-partitioning works and there is a root owned by Giada in the stack-forest.
Notice that if we remove leaves from the stack-forest, alternating between nodes owned by Federico and Giada, we are actually performing a sequence of valid moves. The algorithm is the following:
• When it is Federico's turn, we remove an arbitrary leaf owned by Federico.
• When it is Giada's turn we remove an arbitrary leaf owned by Giada taking care of not removing a root if there is only one root owned by Giada.
Why does the algorithm work?
• When it is Federico's turn, since there is at least one root owned by Giada and the number of nodes owned by Federico and Giada is the same, there must be at least one leaf owned by Federico (recall that adjacent vertices have different owners).
• When it is Giada's turn, there are more nodes owned by Giada then by Federico, hence there is at least one leaf owned by Giada. Could it be that such a leaf is also a root and it is the only root owned by Giada? It can be the case only if that is in fact the only remaining vertex.