PROBLEM LINK:
Author: Dmytro Berezin
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Pushkar Mishra
DIFFICULTY:
Simple
PREREQUISITES:
Greedy, In-built data structures
PROBLEM:
Chef spent N days working really hard! He planned loads of tasks: as many as Ai tasks to do on the ith day! Chef's work was brutal, so he only managed to finish Bi tasks on the ith day.
The good news is that Chef has a Time Machine!
The Time Machine has K white buttons and M black buttons. Each button has a positive integer printed on it. Now Chef goes through all N days consequently and presses buttons. Each day Chef can only press one button (either white or black). After using a button once, it becomes inactive.
Pressing a white button with integer x printed on it reduces the number of planned tasks on the day it was pressed by exactly x. Note that this white button can only be pressed if number of planned tasks on the day are greater than or equal to x.
Pressing a black button with integer x printed on it increases the number of completed tasks on the day it was pressed by exactly x. Note that this black button can only be pressed if after pressing it, number of completed tasks don't exceed the number of tasks.
Chef is interested in finding the minimum possible amount of total uncompleted tasks he will still be left with after N days using the Machine in the best way?
Be careful! Time is sensitive! Chef cannot make a day when he completed more tasks then planned, as this may result in a more-work-than-planned paradox, killing all lazy people on the planet!
EXPLANATION:
Subtask 1
Given constraints are very small. Thus, a brute force solution can easily work. Trying all possible buttons in all possible ways and noting the minimum over all such arrangements gives the answer. The total complexity of this approach is \mathcal{O}(2^N*2^M*2^K). This will pass under the given constraints.
Subtask 2
There are many observations to make here which reduce this problem substantially:
-
For the given A[i] and B[i] values, we are only interested in the value A[i]-B[i]. Basically, we can modify each A[i] to A[i]-B[i]. From this point onwards in this editorial, array A is assumed to be containing the modified values, i.e., A[i]-B[i].
-
The black and white buttons fundamentally do the same things when dealing with the modified values of the array A. Thus, we put all the values from the two arrays, C and D, in a common multiset called buttons. A multiset is a set which allows duplicates to exist.
Now, before we go on to the formal algorithm, let’s think of a smaller problem. Let’s take two values from the array A (just reminding, the values aren’t the ones which were taken as input) A[i] and A[j]. Let’s assume that A[j] > A[i]. Now, let us take two values x and y from the buttons multiset. Let’s say that x < y < A[j]. Which button should be use for A[j] then. Intuition tells us that it is beneficial to use y. This is for two reasons. First one is that using y allows us to complete more number of tasks on the j^{th} day than x using why would. Second reason is that assume y > A[i] and x < A[i]. If we use x on A[j], we won’t be able to use y on A[i]. A better strategy is to use x on A[i] and y on A[j]. What if both x and y were less than A[i]. Then we could use either of buttons on A[i] and the other on A[j]. This is because we will anyway be reducing the same number of tasks from the sum of total incomplete tasks.
This gives us our greedy algorithm: for a particular value A[i], use the button x such that x hasn’t been used up till now and x is the largest value less than or equal to A[i] in the buttons multiset. Now, the incomplete tasks left will be A[i] - x. Add this to the accumulator variable which is to be finally returned as the answer. x is removed from the multiset since one button can’t be used twice. The proof of this greedy algorithm has been given above and can be more formally stated as “Exchange Argument”. You can find more about proofs of greedy algorithms here.
The multiset data structure can be found in almost all the major programming langauges. Writing one on your own requires knowledge of balanced binary search trees. All operations in a multiset are in order \mathcal{O}(\log N).
The editorialist’s program follows the editorial. Please see for implementation details.
OPTIMAL COMPLEXITY:
\mathcal{O}(N\log N) per test case.