need help in question FORESTGA one test case in not passing

link text

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.

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 :slight_smile:

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
ABOUT
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 [13370771]
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[1000000],rt[1000000],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[1000000],c[1000000];
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];

}

}

https://www.codechef.com/viewsolution/13370771 refer this link

plz somebody answer

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

1 Like

No problem :slight_smile: