FASTFOOD APRIL LUNCHTIME 2019

1

I have implemented a O(n) solution of the given problem code FASTFOOD which is giving the correct output but gets a TLE im subtask 2.I am curious to know the reason for the TLE in my code : CodeChef: Practical coding for everyone

2 
for(i=0;i<N;i++)
	    {
	          cin>>B[i];
	          C[i]=A[i]-B[i];
	          D[i]=accumulate(C.begin(),C.begin()+1+i,0);
	    }

You sure its O(N)??

Complexity of Accumulate:

Linear in the distance between first and last.

2 Likes
3

You have used accumulate which is O(n), so your code complexity becomes O(n^2). Try to construct a partial sums from back of the array.

2 Likes
4

You are using std::accumulate…

            for(i=0;i<N;i++){     
                  ...
                  ...
	          D[i]=accumulate(C.begin(),C.begin()+1+i,0);
	    }

this is equivalent to

for(int i = 0; i < n ; i++){
    for(j = 0; j <= i ; j++){
        ....
    }
}
1 Like
5 
#include<bits/stdc++.h>
#include<vector>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--> 0)
	{
		long long n,l=0,c=0,i;
		cin>>n;
		long long a[n],b[n],j=0,z=0;
		for(i=0;i<n;i++)
		{
			cin>>a[i];
			l=l+a[i];
		}
			for(i=0;i<n;i++)
		{
			cin>>b[i];
			c=c+b[i];
		}
	//	if(l>c)
	//	cout<<l<<"\n";
	//	else
	//	{
			
			for(i=0;i<n;i++)
			{
				if(a[i]>b[i])
				{
					z=z+a[i];
					l-=a[i];
					c-=b[i];
					//cout<<l<<"if -\n";
					if(i==n-1)
					cout<<z<<"\n";
				}
				else
				{
					if(l>c)
					{
						z=z+a[i];
						l-=a[i];
					c-=b[i];
					//	j=i+1;
					}
					else
					{
					
					//for(j=i;j<n;j++)
					
						z=z+c;
						j=i+1;
					//	cout<<z<<" else -\n";
					
				}
					//cout<<"else out \n";
				}
			//	cout<<"value of i ="<<i<<endl;
				if(j>i)
				{
				  cout<<z<<"\n";
				  break;
				}
			}
	//	}
		
	}
	return 0;
}

What is the error in my code ?
can some one guide me

6

1
5
18 7 9 9 3
20 4 13 4 10

Try to run your code on this test case . Your Output is 51 instead it should be 53
18+7+9+9+10 = 53 . First 4 days in Chefland and last day in Chefabad . Hope this helps :smiley: