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

×

LUMPYBUS - Editorial

6
1

PROBLEM LINK:

Practice
Contest

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.

SAMPLE SOLUTIONS:

Author
Editorialist
Tester

This question is marked "community wiki".

asked 30 Jul '16, 22:57

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581
accept rate: 4%

edited 05 Aug '16, 00:32

animesh_f's gravatar image

6★animesh_f ♦
8831422


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

link

answered 30 Jul '16, 23:46

geek_geek's gravatar image

4★geek_geek
43914
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) dpraveen ♦♦4★
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) dpraveen ♦♦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).

link

answered 31 Jul '16, 00:23

lebron's gravatar image

7★lebron
3.3k317
accept rate: 24%

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

link

answered 31 Jul '16, 00:06

xellos0's gravatar image

7★xellos0
5.9k54394
accept rate: 10%

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.

link

answered 31 Jul '16, 00:14

stillhungry's gravatar image

4★stillhungry
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) dpraveen ♦♦4★

Thanks Sir,really appreciate it.

(03 Aug '16, 19:34) stillhungry4★

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

link

answered 31 Jul '16, 01:31

s12a06's gravatar image

1★s12a06
1
accept rate: 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.

link

answered 31 Jul '16, 01:54

gametube8's gravatar image

2★gametube8
1
accept rate: 0%

edited 31 Jul '16, 01:56

@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

link

answered 31 Jul '16, 14:30

gowthamvn's gravatar image

3★gowthamvn
1
accept rate: 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

link

answered 31 Jul '16, 15:26

noname321's gravatar image

2★noname321
1
accept rate: 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));

} } code @ https://www.codechef.com/viewsolution/10980356

link

answered 31 Jul '16, 17:33

vijayiota77's gravatar image

4★vijayiota77
14425
accept rate: 3%

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

link

answered 31 Jul '16, 19:13

prashant_93_y's gravatar image

2★prashant_93_y
3315
accept rate: 0%

Thanks dpraveen for the comment!

link

answered 21 Sep '17, 15:44

bhagirathi08's gravatar image

3★bhagirathi08
01
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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