I am trying to solve this easy problem http://www.codechef.com/problems/CHEFRP . Whenever i run on IDE it gives me correct output however when i try submitting the answer it shows wrong answer could someone please tell me whats wrong? here is my code include <iostream>using namespace std; int main(void) {
} asked 24 May '15, 11:52

Warning: Long Answer We have to calculate for worst case. And you are working on best case. Your code is if(q[i]>=2) { count=count+2; // it should be count = count + q[i]; }Why I am doing so? Lets take an example.. The input numbers are 6,8,4,3,10 The output should be 10+8+6+4+2= 30. Why 2 is added here and not 3? We have to calculate for worst case. Suppose For the first time from bag I get ingredient of last type (with quantity 10). And for second time I again get last type of ingredient. So for worst case we would first take all the ingredient with largest quantity and then ingredient with second largest quantity and so on... And from the last ingredient that is having smallest quantity we would take 2 from it(as we are required to take 2 units from each). We have taken all the ingredients and from the last ingredient we would take 2 which will complete the task If any of the ingredients is having less than 2 units then it would not be possible to complete the task One optimal solution would be: First sort all the numbers in ascending order. Check the first element(as this would be smallest number) is smaller than 2 then it would be impossible to complete the task Then concurrently add all the numbers from the last to first element in sorted array(except the first element) and add '2' for the first element. Lets see how this would work in above example Input numbers 6 8 4 3 10 Sorted Array 3 4 6 8 10 Required Answer = 10+8+6+4+2 Hope you would have got your answer and this is very easy question and will help your Interest in Competitive Programming Here is my solution: http://www.codechef.com/viewsolution/6954021 answered 24 May '15, 12:51
