# CHEFRP - Editorial

Author: Abhra Dasgupta
Tester: Kevin Atienza
Editorialist: Ajay K. Verma
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng

Cakewalk

Basic maths

### PROBLEM:

Given N numbers, find the smallest value M such that any collection of M of the given numbers is guaranteed to have at least two entries of each number.

### EXPLANATION:

If there is at least one number which is present only once in the original set of N numbers, then we can never find a collection where each number occurs at least twice. Hence, the answer in this case would be -1.

Now, we know that each number occurs at least two times in the original set of numbers. Let us say that number x has the least number of occurrences (f). Now, if we take any collection of (N - f + 2) numbers, it will have at least two entries of each number. This is because only (f - 2) are missing in this collection, and since each number has at least f entries, it will have at least two entries in the picked collection.

On the other hand, we can take a collection of (N - f + 1) numbers, consisting of all (N - f) numbers other than x, and a single entry of x, which contains only a single entry of x. Hence, the answer to our problem should be (N - f + 2).

In the problem, we are not given the whole list of numbers; instead we are given the frequency of each number. Hence, we need to compute the total number of all ingredients, and the smallest frequency, as shown in the snippet below.

```
// A[] is the input array, which consists of the frequencies of elements.

int sum = 0;
int minFreq = INF;

for (int i = 0; i < A.size(); ++i) {
sum += A[i];
minFreq = min (minFreq, A[i]);
}

if (minFreq == 1) return -1;
return (sum - minFreq + 2);
```

O (N)

### AUTHOR’S AND TESTER’S SOLUTIONS:

where is the mistake in my code

I’ve also uses same concept but with another logic.

@dev987 your logic will fail if there are more than one ingredient with minimum count.

Hey shouldn’t there be summation of all N’s instead of just N? coz n is just no of ingredients right?

Can anyone tell me what’s wrong in my solution? it passes subtask 1 but fails second

import sys
t = int(raw_input())

for i in range(t):
inp = raw_input().split()
inp = map(int,inp)

``````sum = 0
cnt = 0
min_inp = min(inp)
for i in range(len(inp)):
sum+=inp[i]

for i in range(len(inp)):
if inp[i] == 1:
print -1
break

if inp[i] == 2:
print sum%100000007
break

else:
cnt+=1

if cnt == len(inp):
print (sum - min_inp + 2)%(1000000007)``````

can anyone pls tell me whats wrong with my code
http://www.codechef.com/viewsolution/6983523

@tarungupta1956 array size must be 105 you have taken it to be 104.

Why is my code showing wrong ans ?

http://discuss.codechef.com/questions/70744/chef-and-new-recepie-wrong-ans

I have used the same concept but got WA during contest. Can someone point out my mistake in following submission :
http://www.codechef.com/viewsolution/6862695

@xcode

U will be laughing after u get to know the mistake
No offense.

Just check, where you used your break statement.
Suppose u have given N=20.
And your first Ingredient is 1.
the n u will break from there…without Scanning(input) 20 ingredient.
You should input all the things first, then only you can do other things.
Otherwise…there will be a problem in matching your input and output file against tester’s input and output file.

@shivam9753 This was silly mistake… thanks man for pointing it out. ROFL
I will remember it for a long time

Can somebody help me …
I used same concept but it shows WA
http://www.codechef.com/viewsolution/7311969

@ganesh_chef you are doing a very small mistake and that is you are breaking the loop when you encounter a[i]<2 which is wrong because for that test case your program will not finish taking the whole input. Though approach is correct but processing input completely is also a part of successful execution of code. You may use a flag variable.

check out this solution:
https://www.codechef.com/submit/complete/9967532

may this helps:
https://www.codechef.com/viewsolution/9967532

I can’t understand the question properly, can someone help me to understand it better? Thank you.

thanks, fixed.

In your code, you should remove the part

``````if inp[i] == 2:
print sum%100000007
break
``````

and it should work. First this case is already handled outside the loop, second this prevents you from seeing the future entries which could be “1”, e.g., for input {3, 2, 1}, your code will print 6, while answer is -1.

Also, you don’t need to use modulo here.

y my code fails??
bool flag = 0;
vector a;
REP(i,n)
{
int g;
cin>>g;
if(g<2)
{
cout<<"-1"<<endl;
flag = 1;
}
a.PUB(g);
}
if(flag != 1)
{
sort(a.begin(),a.end());
sum = 2;
for(int i=1;i<n;i++)
{
sum+=a[i];
}
cout<<sum<<endl;
}

It happens.