PROBLEM LINK:
Author: Praveen Dhinwa
Testers: Animesh Fatehpuria Pushkar Mishra
Editorialist: Pushkar Mishra
DIFFICULTY:
Easy
PREREQUISITES:
Greedy
PROBLEM:
Given is an array A of integers. We have two types of coins: P coins of value 1 and Q coins of value 2. We want to make as many values from the array A as we can using these P+Q coins. We have to report the maximum that we can make.
EXPLANATION:
Before we talk about subtasks, the simplest thing that comes to our mind is, we will always try to make the smaller values first. This is quite intuitive, but let’s us give a formal argument to it: let us say we try to make values in random order. If using 1s and 2s, we can make a value x, then we can make all other values y such that y \leq x. Why is this so? For some y \leq x, if x and y are of the same parity, then we can simply remove some of the value 2 coins that we used in x. If they are of different parity, we can can first remove a value 1 coin and then remove some value 2 coins. So, the general argument is that if we can make x with coins of values 1s and 2s, we can make numbers smaller than x too. And we should. We can always make more smaller numbers than making a single x. This is the exchange argument we need for our greedy structure.
But what if x is only made of value 2 coins? In that case, we can’t make smaller values of different parity. We will look at this case later. But it gives us a hint. We need to deal with even and odd numbers separately.
Subtask 1
There are no 1 coins. That means we can only make even numbers. We sort all the numbers and try to make the even ones in increasing order till we run out of all the Q coins of value 2.
Subtask 2
There are no 2 coins. But we can make everything with coins of value 1. Just that we follow the same thing we did before, we start by making the smallest coin first.
Subtask 3
In this subtask we have both the 1s and the 2s. As we saw earlier, we segregate the numbers of the array A into two arrays, even[] and odd[]. Once we have segregated the numbers, we need to sort both the even and the odd arrays; this is because of the same reasoning as before.
Now we start by looking at the smallest coins from the two arrays, even and odd. Let these coins be of values V_e and V_o respectively. We know that odd values require us to use the 1 value coins. So we should try to use our 1 value coins in odd numbers since odd numbers can’t be made with 2 value coins but even numbers can be made with either of the 1s or the 2s. This leads us to a crucial observation. If we can use a 2 value coin, we should do that because we don’t get any benefit by saving them. So, we compare the two values, V_o and V_e, and first make the smaller of the 2. If the V_o was smaller, we move on to the next odd coin, else we move on to the next even coin. This goes on until we run out of all the coins or we are left with just value 2 coins and off numbers. The pseudocode is given below:
Make_Coins(A[], N):
odd[oddCount] = getOddNums(A);
even[evenCount] = getEvenNums(A);
sort even[] and odd[];
CountAns = 0; // Answer Counter.
while (Coins left and Numbers left) {
Vo = smallest remaining value in odd[];
Ve = smallest remaining value in even[]; // in case no value remaining,
// set to arbitrary high value.
if (Vo < Ve and Value 1 coins left) {
// if no value one coins left, we can't make odd numbers.
Coin2req = Vo / 2;
if (Coin2req > Q) {
// we can only use as many coins as are left.
Coin2req = Q;
}
// Subtract value from Vo and also reduce number of 2 coins.
Vo -= Coin2req * 2;
Q -= Coin2req;
// Further calculate how many 1 coins are required.
Coin1req = Vo;
if (Coin1req > P) {
// we can only use as many coins as are left.
Coin1req = P;
}
// Subtract value from Vo and also reduce number of 2 coins.
Vo -= Coin1req;
P -= Coin2req;
// If we managed to make Vo = 0, we can increment our answer counter
if (Vo == 0) {
CountAns = CountAns + 1;
remove Vo from odd[];
}
} else if (Ve < Vo and value 1 or value 2 left) {
//Do same as the case for Vo.
// If we managed to make Ve = 0, we can increment our answer counter
if (Ve == 0) {
CountAns = CountAns + 1;
remove Ve from even[];
}
}
}
return CountAns;
Sorting takes \mathcal{O}(N\log N) time. Thus, overall complexity is dominated by it. Rest of the procedure is linear.
Please see tester’s/setter’s program for implementation details.
Binary search based solution
As we learned above, number of odd coins are more important to consider first. Let us say we decide to make first k smallest odd numbers, we need at least k ones for it. After that, we will find how many even numbers still we make. For that, you can note that the total money remaining to spend on even numbers is $P + 2 * Q - \text{sum of first k smallest odd numbers}. We have to find number of even numbers we can make using this amount of money. This can be done by a binary search over the number of even coins you can make. Overall time complexity will be \mathcal{O}(n log n)$. Please see author’s solution for it.
COMPLEXITY:
\mathcal{O}(N\log N) per test case.