Editorial for Google Code Jam '22 Qualification Round Problem B - 3D Printing
Submitting an official solution before solving the problem yourself is a bannable offence.
The first thing we can notice is that if a printer has units of ink left of a given color, we cannot use more than units of that color. Moreover, this is the only restriction imposed by that value. So, we can summarize the input by saying we cannot use more than units of cyan ink, units of magenta ink, units of yellow ink, or units of black ink.
If then the case is impossible and we are done. Otherwise, we may need to use lower amounts of each color. We can simply go one color at a time, lowering the amounts of ink until we make the sum exactly . Doing it one unit at a time works, but it is very slow. We can do better: in the same way as before, we can consider all the colors one at a time. Let be the sum of the current amount of ink for the colors not currently under consideration. If , we can simply set the amount of the current color to and continue with the next one. If we can lower the current color to and finish immediately. This works because at all times we maintain the invariant that the total amount of ink we are considering is at least units.
Comments