 # need help in question FORESTGA one test case in not passing

I have sorted the array in the decreasing number of months required by each tree. FUNCTION (MergeSort())

Then checking Linearly for required wood in “for loop” of main.

Can you explain your approach? It’s hard to figure out what is happening.

1 Like

eg.
3 74 51
2 2
5 7
2 9
i am sorting both the array based on the number of months needed
let for 2 2
(51-2)/2 =24.5 months will need to grow upto 51
similarly (51-5)/7=6.57 moths,(51-2)/9=5.44
hence array after sorting will be
2 2
5 7
2 9
now i will ckeck from last
if a single tree’s wood is greater than required tree i will break else i will add the other trees wood

@jeetu86044 in certain cases your answer is becoming a negative value such as the input here. A simple check can fix the problem, I have marked it as “BUG FIX”, and making the change gives AC.
I also found another bug where the output comes as 1 instead of 0. Using the library function `ceill` instead of your own `ciel` seems to fix this.
There may be other bugs, I didn’t look further, but I hope this satisfies you. By the way, it’s an nice approach for the problem 1 Like

@meooow thanks a lot for fixing the bug

CodeChef is a non-commercial competitive programming community Hello vamsi_223
Logout
PRACTICE
COMPETE
DISCUSS
COMMUNITY
HELP
CodeChef SnackDown 2017Compete & win \$20.5K Qualifier starts on 20 May, SAT 5:00 PM IST Duration: 96 hrs
31
Days
5
Hrs
22
Min
16
Sec Register Now
Home » Forest Gathering » All Submissions » jeetu86044 
Solution: 13370771
CodeChef submission 13370771 (C++ 4.9.2) plaintext list. Status: AC, problem FORESTGA, contest CODECHEF. By jeetu86044 (jeetu86044), 2017-04-22 00:37:37.
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define ll long long int
void MergeSort(ll *p,ll *q,ll low,ll high,ll min);
void Merge(ll p,ll q,ll low,ll mid,ll high,ll min);
ll ciel(long double n);
int main(){
ll n,in,rt,req,min,re=9223372036854775807,count=0,sum1=0,sum=0,count1,diff,sum3=0,flag=0,i;
long double x=1.0000000000000000000;
scanf("%lld%lld%lld",&n,&req,&min);
for(i=0;i<n;i++){
scanf("%lld%lld",&in[i],&rt[i]);
}
MergeSort(in,rt,0,n-1,min);
for(i=n-1;i>=0;i–){
count1=ciel((long double)(min-in[i])/(rt[i]x));
// printf("%lld re\n",re);
diff=count1-count;
if(count1>=re){
printf("%lld\n",re);
flag=1;
break;
}
sum=(count1
rt[i]+in[i])+sum1
diff+sum;
sum1=sum1+rt[i];
sum3=sum3+in[i];
if(sum>=req){
printf("%lld\n",count1);
flag=1;
break;
}
else{
re=ciel((long double)(req-sum3)/(sum1
x));
count=count1;
}

}
if(!flag)
printf("%lld\n",re);

return 0;

}
ll ciel(long double n){
ll n1;
long double x=0.00000000000000000000;
n1=n;
n=n-n1;
if(n==x)
return n1;
else return (n1+1);

}

void MergeSort(ll *p,ll *q,ll low,ll high,ll min){
ll mid;
if(low<high){
mid=(low+high)/2;
MergeSort(p,q,low,mid,min);
MergeSort(p,q,mid+1,high, min);
Merge(p,q,low,mid,high,min);
}

}
void Merge(ll p,ll q,ll low,ll mid,ll high,ll min){
ll k,i,j,b,c;
long double x,y,z=1.000000000000000;
i=low,j=mid+1,k=0;
while(i<=mid&&j<=high){
x=(
(p+i)-min)/( (q+i)z);
y=(
(p+j)-min)/( (q+j)z);
if(x<y){
b[k]=
(p+i);
c[k]=
(q+i);
i++,k++; }
else{
b[k]=
(p+j);
c[k]=
(q+j);
j++,k++;
}
}
while(i<=mid){
b[k]=(p+i);
c[k]=
(q+i);
i++,k++;
}
while(j<=high){
b[k]=(p+j);
c[k]=
(q+j);
j++,k++;
}
for(i=low,j=0;i<=high;i++,j++){
*(p+i)=b[j];
*(q+i)=c[j];

}

}

No problem //