Sonya puts the blocks in the box:Hackerearth

A good question of knapsack approach.We will first fill the table of dp[n+1][m+1] where dp[i][j]=maximum value of sub-array of size j we can get from the ith block.Then we have to maximize the total value in the box such that we choose only one sub-array from each block and the total sum of lengths of sub-arrays is less than m.

So for this we will change definition of dp[i][j] as maximum value we get for box of length j by choosing subarrays from only first i blocks(knapsack 0/1).

dp[i][j] =max( dp[i-1][j-k]+ dp[i][k] ) for 0<=k<=j

Remember to pad appropriately while using prefix sums and maintaining the dp array also update dp[i][j] in above step in a temporary array and then copy it into dp[i][j].

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <utility>
#include <vector>
// five elements
#include <cstdlib>
#include <iomanip>
#define ll long long
#define ef else if
#define rep(i, s, n) for (ll i = s; i < n; i = i + 1)
#define rev(i, s, n) for (int i = s; i > n; i = i - 1)
using namespace std;
#define fr first
#define se second
#define pb push_back
#define mp make_pair
#define mv vector<ll>
#define vv vector<vector<ll>>
#define vii vector<pair<ll, ll>>
#include <functional>
#include <map>
#include <queue>
#include <set>
// akane_psycho
#define fastio                                                                 \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(NULL);                                                               \
  cout.tie(NULL);
#define c1(a) cout << a << endl;
#define c2(a, b) cout << a << " " << b << endl;
#define c4 (k, x, b, c) printf(" %d %d %d %d ", &k, &x, &b, &c)
#define db double
#define inf 1e18
#define lim 2000000000
#define mo 1000000007
#define MAXN 1000001
#define rp(v)                                                                  \
  cout << endl;                                                                \
  rep(i, 0, v.size()) cout << v[i] << " ";                                     \
  cout << endl;
#define lb(v,val) lower_bound(v.begin(),v.end(),val)-v.begin()
#define ub(v,val) upper_bound(v.begin(),v.end(),val)-v.begin()
#define fill(a,d) memset(a,d,sizeof(a))
ll mod(ll n){
    return n%(ll)mo;
}
int main(){fastio
    ll n,m;cin>>n>>m;
    ll dp[n+1][m+1];
    memset( dp,0,sizeof(dp) );
    vector < mv > v;
    rep(i,0,n){
        mv g;
        ll k;cin>>k; g.pb(0);
        rep(i,0,k){
            ll p;cin>>p;g.pb(p);
        }
        rep(i,1,k+1)g[i]+=g[ i-1 ];
        v.pb(g);
    }
    rep(i,1,n+1){
        rep(j,1, m+1){
            ll mx=0, s=v[i-1].size() ;
            rep(u,j, s)mx=max(mx, v[i-1][u]- v[i-1][u-j] );
            if(s-1 < j)dp[i][j]=dp[i][j-1];
            else dp[i][j]=mx;
        }
    }
    rep(i,1,n+1){ ll dm[m+1];dm[0]=0;
        rep(j,1,m+1){
            ll mx=-inf;
            rep(k,0,j+1){
                mx=max(mx, dp[i-1][j-k] + dp[i][k] );
            }
            dm[j]=mx;
        }
        rep(j,0,m+1)dp[i][j]=dm[j];
    }
    cout<<dp[n][m]<<endl;
}

Longest Common Subsequence Hackerrank:

Question askedto find the longest common subseq. Technique used-dp,time complexity=O(n^2)

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <utility>
#include <vector>
// five elements
#include <cstdlib>
#include <iomanip>
#define ll long long
#define ef else if
#define rep(i, s, n) for (ll i = s; i < n; i = i + 1)
#define rev(i, s, n) for (int i = s; i > n; i = i - 1)
using namespace std;
#define fr first
#define se second
#define pb push_back
#define mp make_pair
#define mv vector<ll>
#define vv vector<vector<ll>>
#define vii vector<pair<ll, ll>>
#include <functional>
#include <map>
#include <queue>
#include <set>
// akane_psycho
#define fastio                                                                 \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(NULL);                                                               \
  cout.tie(NULL);
#define c1(a) cout << a << endl;
#define c2(a, b) cout << a << " " << b << endl;
#define c4 (k, x, b, c) printf(" %d %d %d %d ", &k, &x, &b, &c)
#define db double
#define inf 1e18
#define lim 2000000000
#define mo 1000000007
#define MAXN 1000001
#define rp(v)                                                                  \
  cout << endl;                                                                \
  rep(i, 0, v.size()) cout << v[i] << " ";                                     \
  cout << endl;
#define lb(v,val) lower_bound(v.begin(),v.end(),val)-v.begin()
#define ub(v,val) upper_bound(v.begin(),v.end(),val)-v.begin()
#define fill(a,d) memset(a,d,sizeof(a))

ll mod(ll n){
    return n%(ll)mo;
}
int main()
{
    ll t;t=1;while(t--){
        ll n,m,p,q;cin>>n>>m;
        ll dp[n+1][m+1];
        memset(dp,0,sizeof(dp));
        ll x[n+1],y[m+1];
        rep(i,1,n+1)cin>>x[i];
        rep(i,1,m+1)cin>>y[i];
        ll mx=0;
        rep(i,1,n+1){
            rep(j,1,m+1){
                if(x[i]==y[j])
                {dp[i][j]+=(dp[i-1][j-1]+1);
                if(dp[i][j]>mx){
                    mx=dp[i][j];
                    p=i;
                    q=j;
                }
                //mx=max( mx, dp[i][j] );
                }
                else {
                    dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        
        mv ans;
        //c2(p,q)
        for(ll i=p;i>=0;i--){//c1(q)
            rep(j,0,q+1){
                if(dp[i][j]>dp[i-1][j] && dp[i][j]==mx ){ans.pb(x[i]);q=j;mx--;break;}
            }
        }
        for(ll i=ans.size()-1;i>=0;i--)cout<<ans[i]<<" ";
        //for(int i=p;i>p-mx;i--)cout<<x[i]<<" ";
        //rep(i, p-mx+1 , p+1)cout<<x[i]<<" ";        
    }
}

Featured

shivam, shantam and absolute difference-hackerearth

A dp question in which we first compute the no of subsets of two arrays having a sum s. s ranges from 0 to 200*2000 from the constraints.we will will make two arrays x and y for storing the no of different subsets possible whose sum=i.We will do this using dp approach.Then we will take x[i] one by one and find summation of y[j] where

max( 0,x[i]-q ) <= j <= min(k-1,x[i]+q)

(this can be done in O(n) using prefix sums) and add summ*x[i] to ans.

Remember to take mod at every time you add (add 10^9+7 when you subtract and then take mod) as total subsets could go upto 2^200.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <utility>
#include <vector>
// five elements
#include <cstdlib>
#include <iomanip>
#define ll long long
#define ef else if
#define rep(i, s, n) for (ll i = s; i < n; i = i + 1)
#define rev(i, s, n) for (int i = s; i > n; i = i - 1)
using namespace std;
#define fr first
#define se second
#define pb push_back
#define mp make_pair
#define mv vector<ll>
#define vv vector<vector<ll>>
#define vii vector<pair<ll, ll>>
#include <functional>
#include <map>
#include <queue>
#include <set>
// akane_psycho
#define fastio                                                                 \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(NULL);                                                               \
  cout.tie(NULL);
#define c1(a) cout << a << endl;
#define c2(a, b) cout << a << " " << b << endl;
#define c4 (k, x, b, c) printf(" %d %d %d %d ", &k, &x, &b, &c)
#define db double
#define inf 1e18
#define lim 2000000000
#define mo 1000000007
#define MAXN 1000001
#define rp(v)                                                                  \
  cout << endl;                                                                \
  rep(i, 0, v.size()) cout << v[i] << " ";                                     \
  cout << endl;
#define lb(v,val) lower_bound(v.begin(),v.end(),val)-v.begin()
#define ub(v,val) upper_bound(v.begin(),v.end(),val)-v.begin()
#define fill(a,d) memset(a,d,sizeof(a))
#define k 400002

ll x[k],y[k];
ll mod(ll n){
    return n%(ll)mo;
}
ll gi(ll n){
    if(n-1>=0)return y[n-1];
    else return 0;
}
int main()
{
    fastio
    ll n;cin>>n;
    ll a[n],b[n];
    rep(i,0,n)cin>>a[i];
    rep(i,0,n)cin>>b[i];
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    x[0]=1;y[0]=1;
    rep(i,0,n){
        ll d[k]; fill(d,0);  d[0]=1;
        rep(j,0,k){
            if( x[j]>0)d[j+a[i]]=mod( d[j+a[i]] + x[j]);
            
        }
        rep(j,1,k)x[j]=mod(x[j]+d[j]);
    }
    rep(i,0,n){
        ll d[k]; fill(d,0);  d[0]=1;
        rep(j,0,k){
            if( y[j]>0)d[j+b[i]]=mod( d[j+b[i]] + y[j]);
            
        }
        rep(j,1,k)y[j]=mod(y[j]+d[j]);
    }
    ll q;cin>>q;
    rep(i,1,k)y[i]=mod(y[i]+y[i-1]);  
    ll ans=0;
    rep(i,0,k){
        if(x[i]>0){
            ans=mod(ans +mod( x[i]*(  mo +  y[ (ll)min((ll)k-1,i+q ) ]- gi(i-q) ) ) );
        }
    }
    cout<<ans;
}

The Journey Begins

Thanks for joining me!

Good company in a journey makes the way seem shorter. — Izaak Walton

post