Overview
This is just a subproblem that I have learned before. However, I don't have the testcases or the place to submit this.
Describe
Give 2 * n colors with the their frequency (Each of them have to appear at least once). Sum of all their frequency is m * n. Make a table with size m * n (m rows, n column) that minimize the max numbers of different color in each column (And the frequency of color is same above) ?
Input
The first line of input contains two integers m and n (m, n < = 50). The second line contains 2 * n integers — the frequency of each color. The sum values of them equal exactly m * n.
4 4
1 1 2 2 2 4 1 3
Output
Output the table that satisfied the statement above.
1 7 4 6
2 3 4 6
6 3 5 8
6 8 5 8
Explain
- Color 1 has to appear 1 times;
- Color 2 has to appear 1 times;
- Color 3 has to appear 2 times;
- Color 4 has to appear 2 times;
- Color 5 has to appear 2 times;
- Color 6 has to appear 4 times;
- Color 7 has to appear 1 times;
- Color 7 has to appear 3 times;
Sum of them is: 1 + 1 + 2 + 2 + 2 + 4 + 1 + 3 = 16 = m * n.
- Column 1 has 3 different colors.
- Column 2 has 3 different colors.
- Column 3 has 2 different colors.
- Column 4 has 2 different colors.
So the maximum different colors in each column is 3, which is the best answer in this case.
My approach
My teacher said that the answer is only equal 2 or 3. - In case the answer is 2, we just sort the frequency of colors and merge the most frequency and the least frequency color together in the first column, do the same thing with (n - 1) other column. - However, when the answer is 3, he just said the the greedy approach could do this.
I have tried some greedy approach, like merge this first least and the second least frequency color (we can prove that sum of them always < = m) with the most frequency color. But I already found a conner case for this.
I have ask many people (include my teacher — who always said is just a easy greedy problem -_-) but I couldn't found a correct approach. So now I post this, thank you Codeforces community.
