PROBLEM LINK:
Author: Dmytro Berezin
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Pushkar Mishra
DIFFICULTY:
Simple
PREREQUISITES:
Greedy, In-built data structures
PROBLEM:
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.