Beautiful Rectangle
Contest: Technocup 2020 - Elimination Round 4
Difficulty rating: 2300
Tags: brute force, combinatorics, constructive algorithms, data structures, greedy, math

You are given $$$n$$$ integers. You need to choose a subset and put the chosen numbers in a beautiful rectangle (rectangular matrix). Each chosen number should occupy one of its rectangle cells, each cell must be filled with exactly one chosen number. Some of the $$$n$$$ numbers may not be chosen.

A rectangle (rectangular matrix) is called beautiful if in each row and in each column all values are different.

What is the largest (by the total number of cells) beautiful rectangle you can construct? Print the rectangle itself.

Input format:
The first line contains $$$n$$$ ($$$1 \le n \le 4\cdot10^5$$$). The second line contains $$$n$$$ integers ($$$1 \le a_i \le 10^9$$$).

Output format:
In the first line print $$$x$$$ ($$$1 \le x \le n$$$) — the total number of cells of the required maximum beautiful rectangle. In the second line print $$$p$$$ and $$$q$$$ ($$$p \cdot q=x$$$): its sizes. In the next $$$p$$$ lines print the required rectangle itself. If there are several answers, print any.

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

Example input:
12
3 1 4 1 5 9 2 6 5 3 5 8

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

Example input:
5
1 1 1 1 1

Example output:
1
1 1
1

Editorial:
First, let's formulate the criteria that from the given set of numbers $$$x_1, x_2, \dots, x_k$$$ we can create a beautiful rectangle $$$a \times b$$$ (where $$$a \cdot b = k, a \le b$$$). Obviously, if some number occurs more than $$$a$$$ times, then among $$$a$$$ rows there will be such row that will contain two or more occurrences of the number (pigeonhole principle).
Let's prove that if all numbers in $$$x[1 \dots k]$$$ occur no more than $$$a$$$ times, we can create a beautiful rectangle $$$a \times b$$$ (where $$$a \cdot b = k, a \le b$$$).
We will numerate cells from the upper left corner in the order from one, moving diagonally each time. Assume rows are numerated from $$$0$$$ to $$$a-1$$$ and columns are numerated from $$$0$$$ to $$$b-1$$$. Let's begin from the cell ($$$0,0$$$) and move right-down each time. If we face to a border, we will move cyclically. Thus, from the cell ($$$i,j$$$) we will move to the cell $$$((i+1) \bmod a, (j+1) \bmod b)$$$ each time (where $$$p \bmod q$$$ is the remainder when divided $$$p$$$ by $$$q$$$). If we are going to move to a visited cell, before moving let's assign $$$i := (i + 1) \bmod a$$$.
We can also prove that while such numeration each row and each column contain numbers that differ by no less than $$$a-1$$$ (if we are on a row/column, we will make a turn before we will be on the row/column again). Moreover, the difference reaches $$$a-1$$$ (not $$$a$$$) when we move to the previously visited cell and assign $$$i := (i + 1) \bmod a$$$. So, we can prove that the lengths of such orbits are equal $$$lcm(a,b)$$$ ($$$lcm$$$ is a least common multiple). Consequently, they are divided by $$$a$$$. It means that if we will arrange the numbers from $$$x$$$ in the order from the most common (at worst case those that meet $$$a$$$ times) to the least common, each row and each column will always contain different numbers.
Thus, we have a plan of the solution: find optimal $$$a$$$ and $$$b$$$ so that the answer is the largest rectangle $$$a \times b$$$ ($$$a \le b$$$). For this we will iterate over all possible candidates in $$$a$$$ and for each candidate each number $$$v$$$ from $$$x$$$ we will use it no more than $$$\min(c_v, a)$$$ times where $$$c_v$$$ is a number of occurrences $$$v$$$ in the given sequence. So, if we choose $$$a$$$, the upper bound of a rectangle area is $$$\sum \min(c_v, a)$$$ for all possible different numbers $$$v$$$ from the given sequence. Consequently, the maximal value of $$$b$$$ is $$$\sum \min(c_v, a) / a$$$. And let's update the answer if for current iteration $$$a \cdot b$$$ is larger than previously found answer (still consider that $$$a \le b$$$).
We can maintain the value $$$\sum \min(c_v, a)$$$ while $$$a$$$ is incremented by one. For doing this we should each time add $$$geq[a]$$$ to this value, where $$$geq[a]$$$ is a number of different numbers in the given sequence, which occurs at least $$$a$$$ times (we can precalculate this array).
Below is a code which reads the input data and precalculates the array $$$geq$$$.
Below is a code which finds the optimal sizes of the rectangle by iterating its the smallest side $$$a$$$.
And below is a code which prints the optimal rectangle sizes, generates the required beautiful rectangle and prints it.
Thus, the total complexity of the algorithm is $$$O(n \log n)$$$, where $$$\log n$$$ appears only thanks for working with std::map (and we can easily get rid of it and make the linear algorithm).