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$ ~G~ be the color with the greatest number of markers, thus, there are $\#R=N-\#G$ ~\#R=N-\#G~ markers remaining.

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

While are still markers that are not of the color $\#G$ ~\#G~, first append the sword with a marker of color $G$ ~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$ ~G~, there will always be a marker of color $G$ ~G~ available, and we are able to use all $\#R$ ~\#R~ markers.

To fit in the remaining markers colored $G$ ~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$ ~\#R~ "padding" markers is $\#R+1$ ~\#R+1~ using a sequence like ABABABA.

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

Comments

There are no comments at the moment.