For best results when reading this editorial, please make sure you have spent some time on the original problem and have a good grasp of C++ :)

This editorial might seem very long, but please stick with me, the solution’s just a bit tricky and it’s actually quite short once you understand it. Plus, most of this editorial is just a bunch of proofs.

I’ll be covering the solution for this problem (AIO 2020 Q1, Baubles).

Recall that Ro and Bo are the # of red and blue baubles Olaf has respectively. Rp and Bp are the # of red and blue baubles that have been ordered. S is the # of spare baubles he has.

# TL;DR

#include<bits/stdc++.h>
using namespace std;
int main() {
	ifstream in ("baublesin.txt");
	ofstream out ("baublesout.txt");
 
	int ro, bo, s, rp, bp;
	in >> ro >> bo >> s >> rp >> bp; 
 
	if(rp == 0) {
		out << max(0, (s+bo)-(bp-1));
	} else if(bp == 0) {
		out << max(0, (s+ro)-(rp-1));
	} else if(ro >= rp and bo >= bp) {
		int x = min(ro-(rp-1), bo-(bp-1));
		out << x + s << endl;
	} else if(ro < rp or bo < bp) {
		int c = max(0, rp-ro) + max(0, bp-bo);
		out << max(0, s-(c-1)) << endl;
	} 
}

# Case 1

Notice that if Olaf has enough red and blue baubles to complete the order (Ro >= Rp AND Bo >= Bp), then we have to break some coloured baubles. Let’s break the minimum amount of these coloured baubles so that Olaf cannot fill his order (call this quantity X).

Let’s analyze how many reds we have to delete. We want to delete reds JUST until he doesn’t have enough (this will fail Olaf on the red baubles with the minimum amount of reds broken). Which is basically deleting until he has Rp-1 reds. Which costs Ro-(Rp-1) broken baubles. You can apply a similar logic for blue baubles. The answer is the minimum of both of these as mentioned above (min(Ro-(Rp-1), Bo-(Bp-1))).

Notice how if Rp = 0 then this analysis is wrong (because we can’t “delete until we have -1 baubles”). We’ll get back to that later.

Remember that Ro >= Rp and Bo >= Bp (enough of both to complete order). In this configuration, we have one pile that is missing a single bauble. Thus, if Olaf has a spare bauble, he can use it to fill the order, so we also have to break all spare baubles.

So our answer for Case 1 is X + S.

Why is this configuration correct? Firstly, we can’t break any less coloured baubles, otherwise Olaf will fill his order. Now, by Subtask 3’s solution, and without loss of generality we assume the pile with one missing bauble is red (you can apply the same logic if that pile was blue).

If we take away a red bauble => there will be one more missing red bauble so Olaf needs to use one more spare bauble. Then we can break one less spare bauble.

If we take away a blue bauble => if Olaf has strictly more than the requirement, he will be unaffected. If he has less than or equal to the requirement, he will be missing one more blue bauble.

Either way, we can “save” a spare bauble. Notice that you break +1 coloured baubles, only to be offset by -1 spare baubles broken. The overall answer is unaffected. Actually, if you repeat this process S times or more you will be breaking 0 spare baubles, at which point you cannot break any less spares, but you are still breaking coloured baubles, which actually makes the answer worse.

# Case 2

If Olaf doesn’t have enough baubles to fill the order (Ro < Rp OR Bo < Bp), he’ll have to use spares. So let’s attack his supply of spares. We want to break just enough spares so that he doesn’t have enough to fill the order.

But how do we know how many spares Olaf needs? Let’s first calculate how many spares he needs to fill his order of reds. Notice that if he has less red baubles than the requirement (Ro < Rp) then he needs Rp-Ro red baubles (which will be greater than 0). Otherwise (Rp <= Ro), he needs 0 more reds. Also notice that if Rp <= Ro, then Rp-Ro is negative or zero but the answer is “shifted up” to zero.

So we can simplify the # of red baubles Olaf needs to max(0, Rp-Ro). You can apply a similar logic for blue. Therefore, the number of spare baubles he needs to fill both red and blue (to complete his order) is max(0, Rp-Ro) + max(0, Bp-Bo). Let’s call this quantity C. And now let’s calculate how many spares we need to break.

If C > S (he doesn’t even have enough spare baubles to complete his order by default), well we can break 0 spares (0 is >= this quantity).

Otherwise, if C <= S then Olaf should have C-1 spares (recall that C is the number of spares he needs to complete his order). So we break S-(C-1) spares, which is positive and thus >= 0.

So we can simplify # of spares we need to break to max(0, S-(C-1)). Which is our answer because by default Olaf can’t fill his order, and now he can’t use spares to do it either.

Now, why is this correct? Well I’m too lazy to write out the proof all over again, but it’s very similar to Case 1. You can’t break any less spare baubles. You suppose you break one more spare bauble and you see that you will never be able to get a better answer.

# Edge Case

If you implement only case #1 and #2 you realize that you’ll get a WA (Wrong Answer) verdict. Well, we forgot something. What if Rp = 0 or Bp = 0? As shown in Case #1 our algorithm messes up. WLOG we assume that 0 blue baubles are ordered, in other words, Bp = 0 (you can use the same logic if Rp = 0). Since the palace does not need any blue baubles, Olaf might as well paint all his spare baubles red. So he will have S + Ro red baubles. We want him to only be able to have Rp-1 red baubles. Which costs (S+Ro) - (Rp-1) broken baubles (some spare, some red, but we do not care, the answer is still valid).

Another edge case: Make sure you check if Rp = 0 or Bp = 0 BEFORE running Cases #1 and #2. Otherwise your program will be wrong!