## Editorial for Back From Summer '17 P2: Crayola Lightsaber

**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:

Let be the color with the greatest number of markers, thus, there are markers remaining.

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

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

To fit in the remaining markers colored , 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 "padding" markers is using a sequence like `ABABABA`

.

Therefore, we can place at most , giving us the solution.

## Comments

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.

For the first case:

For the second case:

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.

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.

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