FASTFOOD - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Hasan Jaddouh
Tester: Joud Zouzou
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

Partial sums and being greedy. :stuck_out_tongue:

PROBLEM:

Given the list of profits at N moments of time Chef can earn in Chefland (given in array A) and in Chefabad (given in array B). The chef is currently in Chefland and can move from Chefland to Chefabad only once at any moment. Find the maximum profit chef can earn if he chooses the time to move optimally.

QUICK EXPLANATION

  • If chef moves from Chefland to Chefabad at time T, he shall earn profit A[1 \ldots T-1]+B[T\ldots N] where X[L \ldots R] denote X[L]+ X[L+1] +\ldots +X[R].
  • In order to find a maximum profit, we can take the maximum of A[1 \ldots T-1]+B[T\ldots N] for all values of T, by computing prefix sum on A and suffix sum on B.

EXPLANATION

The naive solution would be to try each moment of time as the time the chef moves from chefland to chefabad and check which moment gives the maximum profit.

Suppose Chef moves at time T. In that way, Chef earns profit A[1] + A[2] + \ldots +A[T-1] + B[T] + B[T+1] +\ldots +B[N] since for time moments before T, chef is in Chefland while for moments after T, Chef is in Chefabad. So, this way, we can calculate for each moment of time, the profit we can earn.

The above solution is sufficient for the first subtask, but we can notice that there are N moments of time and for each moment, we are taking N iterations which become O(N^2) and thus will time out.

To optimize it, let us write profit earned for time T as subarrays of A and B. We see that profit earned at time T is nothing but A[1 \ldots T-1] + B[T \ldots N]. For Different values of T, we can see, we only need a prefix of A and a suffix of B. If we can calculate the sum of prefixes and suffices efficiently, we can solve the problem.

Since A[1 \ldots T] = A[1 \ldots T-1]+A[T], this allows us to precompute prefix sums of A for all the time moments. Similarly, B[T \ldots N] = B[T] + B[T+1 \ldots N] we can also compute suffix sums of B for all the time moments. After that, it’s just being greedy and choosing the maximum profit achievable.

The edge case is where Chef either moves in the very first moment or moves after N moment.

Read more on prefix sums here.

Bonus:
Same problem, but now you are allowed to move from chefabad to chefland and chefland to chefabad any number of times, but you cannot move again, if you moved withing previous K moments. Find maximum profit.

TIME COMPLEXITY

Time complexity is O(N) per test case.

SOLUTIONS:

Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
 
 
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
		
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}


int T;
int A[100100];
int B[100100];

int n;
int sm_n=0;
int main(){
	//freopen("00.txt","r",stdin);
	//freopen("00o.txt","w",stdout);
	T=readIntLn(1,1000);
	while(T--){
		n=readIntLn(1,100000);
		sm_n+=n;
		assert(sm_n<=1000000);
		int cur =0;
		int sol=0;
		for(int i=0;i<n;i++){
			if(i==n-1){
				A[i]=readIntLn(1,10000);
			} else {
				A[i]=readIntSp(1,10000);
			}
		}


		for(int i=0;i<n;i++){
			if(i==n-1){
				B[i]=readIntLn(1,10000);
			} else {
				B[i]=readIntSp(1,10000);
			}
			cur += B[i];
		}
		sol = cur;

		for(int i=0;i<n;i++){
			cur += A[i] - B[i];
			sol = max(sol,cur);
		}
		cout<<sol<<endl;
	}
	assert(getchar()==-1);
}
Tester's Solution
// Full Solution
#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
	    char g=getchar();
	    if(g=='-'){
	        assert(fi==-1);
	        is_neg=true;
	        continue;
	    }
	    if('0'<=g && g<='9'){
	        x*=10;
	        x+=g-'0';
	        if(cnt==0){
	            fi=g-'0';
	        }
	        cnt++;
	        assert(fi!=0 || cnt==1);
	        assert(fi!=0 || is_neg==false);

	        assert(!(cnt>19 || ( cnt==19 && fi>1) ));
	    } else if(g==endd){
	        assert(cnt>0);
	        if(is_neg){
	            x= -x;
	        }
	        assert(l<=x && x<=r);
	        return x;
	    } else {
	        assert(false);
	    }
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
	    char g=getchar();
	    assert(g!=-1);
	    if(g==endd){
	        break;
	    }
	    cnt++;
	    ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
long long a[1000005];
long long b[1000005];
int main()
{
	int t = readIntLn(1,1000);
	while(t--)
	{
	    int n = readIntLn(1,100000);
	    for (int i=1;i<=n;i++)
	    {
	        if (i<n)
	            a[i]=readIntSp(1,10000);
	        else
	            a[i]=readIntLn(1,10000);
	    }
	    for (int i=1;i<=n;i++)
	    {
	        if (i<n)
	            b[i]=readIntSp(1,10000);
	        else
	            b[i]=readIntLn(1,10000);
	    }
	    a[0]=0;
	    b[n+1]=0;
	    for (int i=1;i<=n;i++)
	        a[i]+=a[i-1];
	    for (int i=n;i>=1;i--)
	        b[i]+=b[i+1];
	    long long ret=0;
	    for (int i=0;i<=n;i++)
	        ret=max(ret,a[i]+b[i+1]);
	    cout<<ret<<endl;
	}
	assert(getchar()==-1);
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
	//SOLUTION BEGIN
	//This code is not meant for understanding, proceed with caution
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni();
	    long[] a = new long[2+n], b = new long[2+n];
	    for(int i = 1; i<= n; i++)a[i] = nl();
	    for(int i = 1; i<= n; i++)b[i] = nl();
	    for(int i = 1; i<= n+1; i++)a[i] += a[i-1];
	    for(int i = n; i>= 0; i--)b[i] += b[i+1];
	    long ans = 0;
	    for(int i = 0; i<= n; i++)ans = Math.max(ans, a[i]+b[i+1]);
	    pn(ans);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	long mod = (long)1e9+7, IINF = (long)1e18;
	final int INF = (int)1e9, MX = (int)1e6+1;
	DecimalFormat df = new DecimalFormat("0.0000000");
	double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
	static boolean multipleTC = true, memory = false;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    int T = (multipleTC)?ni():1;
//        Solution Credits: Taranpreet Singh
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
	    else new Main().run();
	}
	long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
	int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}   

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

#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

Why am i getting error with this code

t = int(input())
for i in range(t):
n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
s = 0
flag=0
for i in range(n):
if(a[i]>=b[i]):
s+=a[i]
else:
flag = 1
break
if(flag == 1) :
s1 = sum(a[i:])
s2 = sum(b[i:])
s= s+max(s1,s2)
print(s)

https://www.codechef.com/viewsolution/24120664

try input
1 8 10 2
8 2 1 1

Your Output:
12
Correct output:
21

as in your code you are comparing the if array ‘a’ element is larger than element for array ‘b’ and switching if in this input the condition becomes true and gives wrong answer as you are not calculating the overall profit .

 for _ in range(int(input())):
   n=int(input())
   l1=list(map(int,input().split()))
   l2=list(map(int,input().split()))
   res,sum1,sum2=0,0,sum(l2)
   sum3=sum2
   for i in range(n):
     sum1+=l1[i]
     sum2-=l2[i]
   res=max(res,sum1+sum2)
   print(max(res,sum3))

A Simple python Approach : )

3 Likes

Where am i going wrong ? help me debug this problem anyone

# cook your dish here
t=int(input())
for x in range(t):
    n=int(input())    
    old=[int(x) for x in input().split()]
    new=[int(x) for x in input().split()]
    s_old=[]
    s_new=[]
    s=0
    for x in old:
        s=s+x
        s_old.append(s)
    s=0
    for x in new:
        s=s+x
        s_new.append(s)
    f=0
    total_profit=0
    for i in range(n):
        if(i==0):
            if(s_old[i]>s_new[i]):
                total_profit=s_old[i]
            else:
                total_profit=s_new[i]
                f=1
        else:
            o1=(s_old[i]-s_old[i-1])
            o2=(s_new[i]-s_new[i-1])
            if(o2>o1):
                f=1 
                total_profit=total_profit+o2 
            else:
                if(f==1):
                    f=0
                    if(s_old[i]>s_new[i]):
                        total_profit = s_old[i]
                    else:
                        f=1 
                        total_profit =s_new[i]
                else:
                    total_profit=total_profit+o1
    print(total_profit)

//can you please tell me that where I am wrong in it.

#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(false);cin.tie(0)
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define vec std::vector
#define mp map<ll,ll>
#define fo(i,j,n) for(ll i=j;i<n;i++)
#define co cout<<
#define en <<"\n"
#define all(x) x.begin(),x.end()
#define mod 1000000007
#define so(x) sort(x.begin(),x.end())
#define re(x) reverse(x.begin(),x.end())
using namespace std;
int main (){
boost;
ll t,n,x,y,z,k,ans,g;
cin>>t;
while(t–)
{
ans=0;
cin>>n;
vec v1,v2;
x=0;
y=0;
fo(i,0,n)
{
cin>>g;
x+=g;
v1.pb(g);
}

    fo(i,0,n)
    {
        cin>>g;
        y+=g;
        v2.pb(g);
    }

    fo(i,0,n)
    {
        x=x-v1[i];
        y=y-v2[i];

        if(v1[i]>v2[i])
        {
            ans+=v1[i];
        }
        else if(v1[i]==v2[i])
        {
            ans+=v1[i];
        }
        else
        {
            if(y>=x)
            {
                ans+=v2[i]+y;
                break;
            }
            else
            {
                if(x+v1[i]<=y+v2[i])
                {
                    ans+=y+v2[i];
                    break;
                }
                else
                {
                    ans+=v1[i];
                }
            }
        }
    }
    co ans en;
}
return 0;

}

Here is a dp-like approach used to solve this problem.
https://www.codechef.com/viewsolution/54798128

(“Problem of the Day”)

Can anyone help me with my code, I tried to do it using suffixsum, the day we change the shop from location A to B is the day when for Day B we would have greater profit moving forward. The given testcases and the some I tried works fine but I get a WA during submission.

for t in range(int(input())):
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    
    #easiset idea ye hai ki figure out krlo ki kis din ke bad B location m wo jyada pese kamaega uss din shop shift krdo, iske lie suffix sum use kro 
    suma = sum(A)
    sumb = sum(B)
    suffixsumA = [suma]
    suffixsumB = [sumb]

    
    for i in range(1,len(A)):
        
        suffixsumA.append(suffixsumA[i-1] - A[i-1])
        suma -= A[i]
        
    for i in range(1,len(B)):
        
        suffixsumB.append(suffixsumB[i-1] - B[i-1])
        sumb -= B[i]
        
        
    #simply the day after which he earns more 
    daytochange = -1 
    
    for i in range(len(A)):
        if suffixsumB[i] > suffixsumA[i]:
            daytochange = i 
            break 
    # print(daytochange)
    
    totalsum = 0 
    if daytochange == -1:
        print(sum(A))
        continue
    
    else:
        totalsum = sum(A[:daytochange]) + sum(B[daytochange:])
        
        print(totalsum)