Editorial for Back From Summer '17 P2: Crayola Lightsaber


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: kobortor

Let G be the color with the greatest number of markers, thus, there are \#R=N-\#G markers remaining.

First, let us prove that it is always possible to fit in the \#R markers that are not of the color \#G.

While are still markers that are not of the color \#G, first append the sword with a marker of color G. Next, take one of each color of the remaining colors and append them to the stick. Since all the colors are different, there will never 2 markers with the same color adjacent to each.

Since no color has more markers than G, there will always be a marker of color G available, and we are able to use all \#R markers.

To fit in the remaining markers colored G, we must take previously placed markers to "pad" them.

It is easy to convince yourself that the maximum number of markers you can put down with \#R "padding" markers is \#R+1 using a sequence like ABABABA.

Therefore, we can place at most \min(\#G, \#R+1) + \#R, giving us the solution.


Comments


  • -1
    doydlellama  commented on Oct. 3, 2017, 12:52 a.m.

    This clearly fails in the first and second test cases given in the problem. It is not always possible to fit in the #R markers which are not of the color #G.


    • -1
      kobortor  commented on Oct. 3, 2017, 8:43 a.m.

      For the first case:

      red blue black green

      For the second case:

      yellow orange yellow

      • -1
        m4m3sh1b4  commented on Oct. 5, 2017, 9:59 p.m.

        Could you elaborate beyond just giving the correct algorithm output? In the first case, you have #G = 1, #R = 3. Then max(#G, #R + 1) + #R = 7, but the correct output is 4.


        • 0
          aeternalis1  commented on Oct. 6, 2017, 9:01 a.m.

          I believe it ought to be min(#G, #R + 1) + #R rather than max(). The editorial is correct except in that last statement, which was probably a typo.


          • -2
            kobortor  commented on Oct. 6, 2017, 1:50 p.m.

            Ah I see, that is a mistake, it is now fixed.