Playing Around the Table
Contest: Codeforces Round 774 (Div. 2)
Difficulty rating: 2900
Tags: constructive algorithms, greedy, implementation

There are $$$n$$$ players, numbered from $$$1$$$ to $$$n$$$ sitting around a round table. The $$$(i+1)$$$-th player sits to the right of the $$$i$$$-th player for $$$1 \le i < n$$$, and the $$$1$$$-st player sits to the right of the $$$n$$$-th player.

There are $$$n^2$$$ cards, each of which has an integer between $$$1$$$ and $$$n$$$ written on it. For each integer from $$$1$$$ to $$$n$$$, there are exactly $$$n$$$ cards having this number.

Initially, all these cards are distributed among all the players, in such a way that each of them has exactly $$$n$$$ cards. In one operation, each player chooses one of his cards and passes it to the player to his right. All these actions are performed simultaneously.

Player $$$i$$$ is called solid if all his cards have the integer $$$i$$$ written on them. Their objective is to reach a configuration in which everyone is solid. Find a way to do it using at most $$$(n^2-n)$$$ operations. You do not need to minimize the number of operations.

Input format:
The first line contains a single integer $$$n$$$ ($$$2\le n\le 100$$$).

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1\le c_j\le n$$$) — the initial cards of the $$$i$$$-th player.

It is guaranteed that for each integer $$$i$$$ from $$$1$$$ to $$$n$$$, there are exactly $$$n$$$ cards having the number $$$i$$$.

Output format:
In the first line print an integer $$$k$$$ ($$$0\le k\le (n^2-n)$$$) — the numbers of operations you want to make.

Then $$$k$$$ lines should follow. In the $$$i$$$-th of them print $$$n$$$ integers $$$d_1, d_2, \ldots, d_n$$$ ($$$1\le d_j\le n$$$) where $$$d_j$$$ is the number written on the card which $$$j$$$-th player passes to the player to his right in the $$$i$$$-th operation.

We can show that an answer always exists under the given constraints. If there are multiple answers, print any.

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

Note:
In the first test case, if the first player passes a card with number $$$2$$$ and the second player passes a card with number $$$1$$$, then the first player has two cards with number $$$1$$$ and the second player has two cards with number $$$2$$$. Then, after making this operation, both players are solid.

In the second test case, $$$0$$$ operations would be enough too. Note that you do not need to minimize the number of operations.

Example input:
2
2 1
1 2

Example output:
1
2 1

Example input:
3
1 1 1
2 2 2
3 3 3

Example output:
6
1 2 3
3 1 2
2 3 1
1 2 3
3 1 2
2 3 1

Editorial:
For each player, we say it is diverse if all his cards have different numbers. For each player, we will call a card repeated if this player has two or more cards with that number. Observe that a player is diverse if and only if he has no repeated cards.
To construct the answer we are going to divide the process into two parts, each of them using at most $$$\displaystyle \frac{n\times(n-1)}{2}$$$ operations. In the first part, we are going to reach a configuration where everyone is diverse. In the second one, we will reach the desired configuration.
To do the first part, in each operation we will choose for each player a repeated card to pass. We will repeat this until all players are diverse. If some player is already diverse, he will pass a card with the same number as the card he will receive in that operation. This way, if a player was diverse before the operation, he will still be diverse after the operation.
We will prove that the above algorithm ends. If it does not end, at some point some non-diverse player will pass a card he already passed (not a card with the same number, the exact same card). At this point, all other players have at least one card with this number and this player has at least two (because it is non-diverse), but this implies that there are at least $$$n+1$$$ cards with this number, which cannot happen.
Now, we will prove that this algorithm ends in at most $$$\displaystyle\frac{n\times(n-1)}{2}$$$ operations. Consider all cards having the number $$$c$$$, and for each of them consider the distance it moved, but when a player is diverse, we will consider his cards as static and that the card he received (or a previous one, if there are multiple diverse players before him) moved more than once in a single operation. For each $$$x$$$, such that $$$1\leq x\leq n-1$$$, consider all cards having the number $$$c$$$ that moved a distance of $$$x$$$ or more, and look at the one that reaches its final destination first. The first $$$x$$$ players that passed this card already had a card with the number $$$c$$$ on it, and for each of them, one of these cards will not move anymore (remember that once the player is diverse, his cards are static) and it moved less than $$$x$$$, as we are considering the first card. So, there are at most $$$n-x$$$ cards that moved a distance of $$$x$$$ or more. Thus, the maximum sum of distances of all cards containing the number $$$c$$$ is $$$\displaystyle 1+2+\ldots+(n-1)=\frac{n\times(n-1)}{2}$$$ and the maximum sum of distances of all cards is $$$\displaystyle \frac{n^2\times(n-1)}{2}$$$. In each operation, the sum of all distances is increased by $$$n$$$ so there will be at most $$$\displaystyle \frac{n\times(n-1)}{2}$$$ operations in this part.
To do the second part, for each $$$j=1,2,\ldots,n-1$$$ (in this order) the $$$i$$$-th player will pass a card with the number $$$((i-j)\bmod n) + 1$$$ a total of $$$j$$$ times. It is easy to see that after $$$\displaystyle 1+2+\ldots+(n-1)=\frac{n\times(n-1)}{2}$$$ operations, all players are solid.
Implementing the first part naively will result in an $$$\mathcal{O}(n^4)$$$ algorithm, which is enough to solve the problem. However, it is possible to divide the complexity by $$$n$$$ maintaining a stack of repeated cards for each player.
Intended complexity: $$$\mathcal{O}(n^3)$$$