CHEFRP - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Cakewalk

PREREQUISITES:

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

Time Complexity:

O (N)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

2

where is the mistake in my code


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

3

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

4

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):
n = int(sys.stdin.readline())
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)
5

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.

6

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

7

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

8

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;
}

9

Why is my code showing wrong ans ?

10

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

11

@xcode

U will be laughing after u get to know the mistake :stuck_out_tongue:
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.

12

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

13

It happens. :slight_smile:

14

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

15

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

16

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

17

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

18

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