PROBLEM LINK:Author: Praveen Dhinwa 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 Subtask 2 Subtask 3 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:
Sorting takes $\mathcal{O}(N\log N)$ time. Thus, overall complexity is dominated by it. Rest of the procedure is linear. Binary search based solution COMPLEXITY:$\mathcal{O}(N\log N)$ per test case. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 30 Jul '16, 22:57

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
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)

"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+ 1coins  otherwise, we could swap those two 1coins with one of the 2coins 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

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.34 lines will do the trick. answered 31 Jul '16, 00:14
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)

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

My short AC cpp code without vectors/searching: https://www.codechef.com/viewsolution/10975470 answered 31 Jul '16, 01:54

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

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=x2*q; if(remain <=p) { q=0; p=premain; c++; } } } if(x is odd) { int r=(arr[i]1)/2; if(arr[i]1<=2*q && p!=0) // single one used { c++; q=qr; p; } else {
answered 31 Jul '16, 17:33

Can anyone please let me know why I am getting WA for test case 15, 16 and 17. Help would be appreciated. answered 31 Jul '16, 19:13
