LUMPYBUS - Editorial

#1

Author: Praveen Dhinwa
Testers: Animesh Fatehpuria Pushkar Mishra

Editorialist: Pushkar Mishra

Easy

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.

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.

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.

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 - ext{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.

SAMPLE SOLUTIONS:

#2

I got AC,

1.Sorted the Array

2.For each element try to use 2 coins and 1 coins greedily , use as many as 2 coins and pay rest with one coin , if possible increament the counter else move to the next number

Code in Python : https://www.codechef.com/viewsolution/10961797

#3

“But what if x is only made of value 2 coins?”

I noticed that in this case, there can’t be anyone paid using 2+ 1-coins - otherwise, we could swap those two 1-coins with one of the 2-coins in x.

So we can take the maximum of the obvious greedy and an alternative greedy where we try paying 1 coin to all odd people in increasing order first.

#4

Hi I everyone I noticed in a greedy solution ,An exchange theorem is mentioned.The article associated with the link is very difficult for a newbie like me.Can anyone please explain it or give a link,Please.
It will be a great help.3-4 lines will do the trick.

#5

We can simply use invariant “spend not too much money + used not too many odd coins”, that will lead to a greedy which doesn’t need any odd/even partitioning (


[1]).

[1]: https://www.codechef.com/viewsolution/10960777

#6

will anyone please let me know for what test cases my solution is wrong
https://www.codechef.com/viewsolution/10975156
subtask 15 and subtask 16 is wrong and subtask 17 is right

#7

My short AC cpp code without vectors/searching: https://www.codechef.com/viewsolution/10975470
Easy enough to understand for noobs.
Ironically,i failed to recognize it as greedy.I thought I was doing brute-force.

#8

@s12a06
Try this case

No of 1 rupee coins is 3,
No of 2 rupee coins is 1,
array is [5,5,5]

3 3 1

5 5 5

#9

Can anyone please let me know why I am getting WA for test case 16 and 17. Help would be appreciated.

https://www.codechef.com/viewsolution/10974501

#10

sir please check my code ,its not working for 3rd subtask (highly redable code)

{ int c=0; for(all x in arr) {

if( x is even)
{
if(x can be made with only 2’s)
{
q=q-(x/2);
c++;
}
else if(x can be made with combination of 1 and 2)
{
remain=x-2q;
if(remain <=p)
{
q=0;
p=p-remain;
c++;
}
}
}
if(x is odd)
{
int r=(arr
-1)/2;

if(arr*-1<=2*q && p!=0) // single one used
{
c++;
q=q-r;
p–;
}
else {

   if(arr*-(2*q)<=p)//use all q and remaining with use of required p
{
c++;
q=0;
p=p-(arr*-(2*q));


#11

Can anyone please let me know why I am getting WA for test case 15, 16 and 17. Help would be appreciated.

https://www.codechef.com/viewsolution/10972060

#12

Thanks dpraveen for the comment!

#13

Yes, I used this solution too. See the solveUsingGreedy function in the solution here. This is same greedy as mentioned in the editorial.

#14

Btw, one thing to get careful in this greedy approach is to make sure that you don’t subtract count of 1 or 2 Rs coins in the case when it is not possible to make a number. I got some WA initially in this approach due to this error.

#15

Ideally, it is better to spend some time to get into rigorous details. Basic of exchange argument is that if you swap/exchange something in your optimal solution, your solution is only going to get worse. See this thread, it is really good example to learn about it.

#16

Thanks Sir,really appreciate it.