Google Kickstart Round D Editorial

general
, ,
1

Hello Codechef Community, Here are the video editorials for today’s held Google Kickstart Round D 2022. Each and every problem along with their solutions are explained in detail.

Below are the links to the solution:-

  1. Image Labeler
  2. Maximum Gain
  3. Touchbar Typing

Rest problems will be updated soon.

Please do watch videos, like, comment, and subscribe to this channel. Likewise, Videos will be uploaded for most of the contest’s editorial. Any suggestions are welcome, do comment in this blog post.

Thank You!!

Google Kickstart Round C Editorial
Algebra in Competitive Programming

3 Likes
2

I am unable to solve maximum gain. Can someone help to figuring out what is the mistake in below code:)

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

vector<ll> createDPArray(int n,vector<ll>& arr){
    vector<ll> dp(n+1);
    vector<ll> suf(n+2);
    vector<ll> pre(n+2);
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+arr[i-1];
    }
    for(int i=n;i>=1;i--){
        suf[i]=suf[i+1]+arr[i-1];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            dp[i]=max(dp[i],pre[j]+suf[n+1-i+j]);
        }
    }
    return dp;
}


ll solve(int n,vector<ll>& a,int m,vector<ll>& b,int k){
    vector<ll> dp1=createDPArray(n,a);
    vector<ll> dp2=createDPArray(m,b);
    int ndp1=dp1.size();
    int ndp2=dp2.size();
    ll ans=INT_MIN;
    for(int i=1;i<=k;i++){
        if(i<=n && (k-i)<=m){
            ans=max(ans,dp1[i]+dp2[k-i]);
        }
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    for(int h=1;h<=t;h++){
        int n;
        cin>>n;
        vector<ll> a(n);
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        int m;
        cin>>m;
        vector<ll> b(m);
        for(int i=0;i<m;i++){
            cin>>b[i];
        }
        int k;
        cin>>k;
        cout<<"Case #"<<h<<": "<<solve(n,a,m,b,k)<<"\n";
    }
    return 0;
}