canhtoannct's blog

By canhtoannct, history, 4 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it