PROBLEM LINK:Author: Dmytro Berezin DIFFICULTY:Simple PREREQUISITES:Greedy, Inbuilt data structures PROBLEM:EXPLANATION:Subtask 1 Subtask 2
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. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 01 Jan '16, 16:27

NO requirement of any data structures like multiset or balanced binary trees. Just an algorithm, also called "2pointer algorithm" which reduces the complexity from O(n^2) to O(n). Here is a link to a tutorial on 2pointer algorithm (link). First just sort the initial difference array in descending order and find the most suitable candidate for it in the buttons array using binary search or just linear search as well. Then using 2 pointer concept, iterate over the buttons and difference array. Here is a link to my AC solution. Another problem on 2 pointer concept is Codeforces problem answered 11 Jan '16, 18:29

short editorial on 4 easy problems: https://shadekcse.wordpress.com/2016/01/11/codechefjan16challenge/ answered 12 Jan '16, 11:03

An easy solution can be: 1) Store difference if a[i]b[i] in one array (named diff) , sorted in descending order. 2) Store all buttons in one array sorted in descending order of their value x. 3) Iterate over the array diff, get the biggest button that is smaller than or equal to diff[i]. 4) Use this button to lessen diff[i] to 0 or a smaller integer. 5) Store this value in incomplete tasks variable. 6) Repeat steps 35 for other elements in diff. answered 14 Jul, 15:34

Seriously? Optimal complexity is suggested to be O(NlgN) ? It can be solved in O(N) without any complex datastructure but just arrays.
Yes array does it. But you do need to sort it. Can you do this in O(n)?