Editorial for Back From Summer '17 P2: Crayola Lightsaber
Submitting an official solution before solving the problem yourself is a bannable offence.
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
Therefore, we can place at most ~\min(\#G, \#R+1) + \#R~, giving us the solution.