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

×

It gives me wrong answer although i did it correctly

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

int t,i,n,flag=1,count;
int *q=NULL;
cin>>t;

while(t--)
{
    cin>>n;
    q = new int[n];
    for(i=0;i<n;i++)
    {
        cin>>q[i];
    }
    for(i=0;i<n;i++)
    {
        if(q[i]>=2)
        {
         count=count+2;
        }
       else
        {
            flag=0;
        }
    }

    cout<<count<<endl;
   count=0;

    if(flag==0)
    {
        cout<<"-1";
    }
}


return 0;

}

asked 24 May '15, 11:52

sam_coder13's gravatar image

1★sam_coder13
14
accept rate: 0%

edited 24 May '15, 11:53


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

link

answered 24 May '15, 12:51

ankurverma1994's gravatar image

4★ankurverma1994
415114
accept rate: 8%

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:

×856

question asked: 24 May '15, 11:52

question was seen: 1,186 times

last updated: 24 May '15, 13:22