Editorial for Wesley's Anger Contest 6 Problem 6 (Easy Version) - Santa's Candy Factory


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

We will assume without loss of generality that A \le B \le C. Consider a strategy where we arbitrarily assign one bowl to one colour and the other to a different colour. If we place all candy canes in their assigned bowl (and discard the remaining colour), the worst we can do is A + B. This strategy alone however is not enough to get any points.

We can consider another strategy where we attempt to identify the colour with C candy canes. We begin similar to the first strategy by arbitrarily assigning one bowl to one colour and the other to a different colour. If discarding the current candy cane would result in the total number of candy canes discarded exceeding B, then it must be the colour with C candy canes. We will then empty any of the two bowls, change the colour assigned to that bowl to the current candy cane's colour, and proceed as usual. If this never occurs, then it must be that one of the initial colour assignments was the colour with C candy canes. We can see that in the worst case, we will collect 100 - 2 \cdot B candy canes.

By itself, neither the first nor second strategy is enough to get any points, but if we consider all possible values of A, B, and C, we can see that \max(A + B, 100 - 2 \cdot B) is always at least 34, which is enough to get 30\% of the points.

We will now consider a third strategy where we attempt to identify both the colour with B and C candy canes. We will begin similar to the second strategy, but this time we will wait until the current candy cane being discarded would result in more than A total discarded candy canes. This time, we must be careful not to change the colour of a bowl with at least B candy canes in it. We will select any of the remaining bowls and change the colour assigned to that bowl to be the current candy cane's colour. We will also reset the discard counter to the number of candy canes in the bowl that is emptied. Again, if this never occurs, then it must be that the initial colour assignments were the colours with B and C candy canes. We will then continue placing candy canes based on their bowl assignment until discarding the current candy cane would result in the discard counter exceeding B. We can then assign the colour of the bowl that has not yet been reassigned to be the current candy cane's colour, and proceed as usual. If this never occurs, then after the first reassignment, the colour assignments were the colours with B and C candy canes. In the worst case, this strategy will collect 100 - 2 \cdot A - B candy canes, which is also not enough on its own for any points.

If we combine the first and third strategies, for all values of A, B, and C, we can collect at least 40 candy canes.

If we combine all three strategies, we can always collect at least 43 candy canes.

Bonus: can you find a way to get 46 candy canes?


Comments

There are no comments at the moment.