Editorial for Google Code Jam '22 Qualification Round Problem B - 3D Printing


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.

The first thing we can notice is that if a printer has u units of ink left of a given color, we cannot use more than u 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 C = \min(C_1, C_2, C_3) units of cyan ink, M = \min(M_1, M_2, M_3) units of magenta ink, Y = \min(Y_1, Y_2, Y_3) units of yellow ink, or K = \min(K_1, K_2, K_3) units of black ink.

If C+M+Y+K < 10^6 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 10^6. 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 S be the sum of the current amount of ink for the 3 colors not currently under consideration. If S \ge 10^6, we can simply set the amount of the current color to 0 and continue with the next one. If S < 10^6 we can lower the current color to 10^6-S 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 10^6 units.


Comments

There are no comments at the moment.