My code is working on base test cases only

#1

when i submit my code on spoj it is showing me wrong answer.

#include iostream
#include climits

using namespace std;

#define ll long long

int minimum=INT_MAX;

bool isPossible(ll ranks[],ll cooks,ll mid,ll paratas) {
ll ans=0;
for(ll i=0;i<cooks;i++) {
ll temp=ranks[i];

    ll sum=0;
    ll j=1,counter=0;
    while(1) {
        sum=sum+temp*j;
        if(sum>mid) {
            break;
        }
        j++;
        counter++;
    }
    ans=ans+counter;

}

if(ans>=paratas) {
return true;
}

return false;
}

int main() {
int t;
cin >> t;

while(t--) {
    ll paratas;
    cin >> paratas;

    ll cooks;
    cin >> cooks;

    ll ranks[cooks]={0};

    for(ll i=0;i<cooks;i++) {
        cin >> ranks[i];
    }

    ll start=0,endd=100;

    while(start<=endd) {
        ll mid=(start+endd)/2;
        bool checker=isPossible(ranks,cooks,mid,paratas);
        if(checker) {
            endd=mid-1;
            minimum=min(mid,minimum);
        }
        else {
            start=mid+1;
        }
    }
    cout << minimum << endl;
    minimum=INT_MAX;
}

return 0;

}

#2

@premang the problem is with the endd point you have taken as ‘100’. It can be anything more than that.
One End point you can take here if we assign all the work to minimum rank chef and get it done, because we are sure that our answer will atleast this much or less than it.

so just do endd = (parathas * (parathas+1))/2 * minimum_rank_possible.
Here one point to note is minimum_rank_possible is not always 1, it actually depends upon the input, so find it also.

#3

how did u derived this endd = (parathas * (parathas+1))/2 * minimum_rank_possible ?

#4

for eg rank r = 2 and parathas = 5.
So total time using this rank is :- 21 + 22 + 23 + 24 + 25 = 2(1+2+3+4+5) which is sum of natural numbers from 1 till parathas(that is 5)

#5

i still dont understand anything !!

#6

what is minimum rank ? how did you got that ?
what is meaning of -> (parathas * (parathas+1))/2 ?

how you combine both ?

can you clearly explain with full example ?

#7

got ittttttttttttttttttttttttttttttt :wink:

1 Like
#8

@premang you can have a look at this
ok lets suppose input is something like:-
10
4 3 4 5 6

here we have 10 parathas to be made
and we have 4 cooks with rank 3,4,5,6.
here minimum rank is 3.

I am supposing you know the sum of first n natural numbers = (n*(n+1))/2
So, one of possible solution is to assign the total work of making parathas to the
cook with rank=3, because he is fastest among them.

(This thing is written in question “For example if a cook is ranked 2…
he will cook one prata in 2 minutes one more prata in the next 4 mins an one more in the next 6 minutes
hence in total 12 minutes he cooks 3 pratas” )

So, time taken by him to make all the parathas himself is
= 3x1 + 3x2 + 3x3 + 3x4 + 3x5 + … + 3x10

so this thing is nothing but 3 x (10 x 11)/2 where 3 is rank and second term is sum of first 10 natural
numbers.

So that can also be written as :- minimum_rank x (parathas x (parathas+1))/2.

#9

@premang also please doubt as resolved if you have understood it.

#10

my code still does not pass for the test case:
1
8
1 1

#include iostream>
#include climits>

using namespace std;

#define ll long long

int minimum=INT_MAX;

bool isPossible(ll ranks[],ll cooks,ll mid,ll paratas) {
ll ans=0;
for(ll i=0;i<cooks;i++) {
ll temp=ranks[i];

    ll sum=0;
    ll j=1,counter=0;
    while(1) {
        sum=sum+temp*j;
        if(sum>mid) {
            break;
        }
        j++;
        counter++;
    }
    ans=ans+counter;

}

if(ans>=paratas) {
return true;
}

return false;
}

int main() {
int t;
cin >> t;

while(t--) {
    ll paratas;
    cin >> paratas;

    ll cooks;
    cin >> cooks;

    ll ranks[cooks]={0};

    for(ll i=0;i<cooks;i++) {
        cin >> ranks[i];
    }
    ll endd_calculation=(paratas)*((paratas+1)/2);
    endd_calculation=ranks[cooks-1]*endd_calculation;
    ll start=0,endd=endd_calculation;

    cout << "endd_calculation = " << endd_calculation << endl;

    while(start<=endd) {
        ll mid=(start+endd)/2;
        bool checker=isPossible(ranks,cooks,mid,paratas);
        if(checker) {
            endd=mid-1;
            if(minimum>mid) {
            	minimum=mid;
            }
        }
        else {
            start=mid+1;
        }
    }
    cout << minimum << endl;
    minimum=INT_MAX;
}

return 0;

}

#11

@premang why are you multiplying end with ranks(cooks-1) , I just told you that it should be the minimum one

#12

to find max we need to multiply last element ?

#13

The ranks are given in random order

#14

then how to find max ?

#15

now i again do not understand, what the meaning for endd we found, if ranks are not in order

#16

@premang please go through all the explanations i have given above, also take some example by yourself and understand it by dry run on it.
In mean time if you also want to have a look at the code, i have the required changes in your code you can also have a look at it https://ide.codingblocks.com/s/230521

#17

thank you …