thienlongtpct's blog

(Need help) How fill the table with at most 3 different colors in a same column.
By thienlongtpct, history, 6 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
  • +18
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 12   Vote: I like it -35 Vote: I do not like it

Erased as it overlooked particular conditions.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are so fucking stupid and annoying. With all your 'dear %username%', and 'best wishes' and explaining how ifs and loops work probably because you think that it is the hardest part.

    Or maybe you are some elaborate joke which doesn't work.

    Of course, there is counterexample to your 'solution'. n = 4, m = 8, f = [1, 1, 5, 5, 5, 5, 5, 5]

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it -17 Vote: I do not like it

      MikeMirzayanov is kindly requested to erase the offensive comment made by one of the Codeforces members in this blog.

      No one has the right to make personal insults when mentioning a counter example to a suggested solution that overlooked particular conditions.

      Thanks in advance, and best wishes.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Dear Sir/Madam

        suck my dick

        Best wishes

        → Reply
»
6 years ago, # |
  Vote: I like it +39 Vote: I do not like it

I will assume that colors are sorted by frequency.

The algorithm will have two phases. In the first phase we take next number and the least full column. If we can put all our numbers in that column then we do it. It is easy to see that this column will become the most full. If we can't do it then we proceed to the second phase (note that we didn't do anything with current color yet).

Actually in the first phase we are going through our columns in some circular order, and we will use at least n colors during the first phase. So in the beginning of the second phase we have some columns with one color and some columns with two colors, and every column with two colors has more numbers than any column with one color.

All the numbers of current color cannot fit in the least full column. That means that all the numbers of current color cannot fit in any of the columns. But our current color has the least frequency over all remaining colors, so if we take any remaining color and any column, that column doesn't have enough place to accommodate all the numbers of that color.

In the second phase we are going to do the following for each color (still in sorted by frequency order): If there are any column with two colors already used which can be fully filled with remaining numbers of our color then do it. Repeat until there are no such columns. Then take the most full column with only one color used and place all the remaining numbers of our color in it (if there are no numbers of our color left we will still consider this column as having two colors).

Now I state that this algorithm always can be done and by construction in each column there will be no more than 3 different colors.

I want to show two statements by induction:
1. Every column with two different colors has more numbers than any column with one color
2. If we have k colors left then we have exactly k columns with one color.

Both this statements are easily proven by how algorithm works.

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

→ Reply