You are not logged in. Please login at www.codechef.com to post your questions!

×

# LUMPYBUS - Editorial

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 - \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.

# SAMPLE SOLUTIONS:

This question is marked "community wiki".

asked 30 Jul '16, 22:57

1.3k156581
accept rate: 4%

8831422

 6 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 answered 30 Jul '16, 23:46 439●14 accept rate: 16% 2 Yes, I used this solution too. See the solveUsingGreedy function in the solution here. This is same greedy as mentioned in the editorial. (30 Jul '16, 23:49) 2 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. (31 Jul '16, 00:03)
 4 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 (code). answered 31 Jul '16, 00:23 7★lebron 3.3k●3●17 accept rate: 24%
 2 "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. answered 31 Jul '16, 00:06 7★xellos0 5.9k●5●43●94 accept rate: 10%
 0 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. answered 31 Jul '16, 00:14 0 accept rate: 0% 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. (31 Jul '16, 00:56) Thanks Sir,really appreciate it. (03 Aug '16, 19:34)
 0 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 answered 31 Jul '16, 01:31 1★s12a06 1 accept rate: 0%
 0 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. answered 31 Jul '16, 01:54 1 accept rate: 0%
 0 @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 answered 31 Jul '16, 14:30 1 accept rate: 0%
 0 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 answered 31 Jul '16, 15:26 1 accept rate: 0%
 0 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-2*q; if(remain <=p) { q=0; p=p-remain; c++; } } } if(x is odd) { int r=(arr[i]-1)/2; if(arr[i]-1<=2*q && p!=0) // single one used { c++; q=q-r; p--; } else {  if(arr[i]-(2*q)<=p)//use all q and remaining with use of required p { c++; q=0; p=p-(arr[i]-(2*q));  answered 31 Jul '16, 17:33 144●2●5 accept rate: 3%
 0 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 answered 31 Jul '16, 19:13 33●1●5 accept rate: 0%
 0 Thanks dpraveen for the comment! answered 21 Sep '17, 15:44 0●1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×1,024
×46
×6

question asked: 30 Jul '16, 22:57

question was seen: 4,262 times

last updated: 21 Sep '17, 15:44