PERRY -Editorial

PROBLEM LINK:

Practice
Agents on missions

Author: sherlock8696
Tester: hellb0y_suru

DIFFICULTY:

EASY

PROBLEM:

Given two arrays A and B and a cost array ,of length N We have to find the minimum cost required to make a non decreasing array C of same length such that C[i] = A[i] with cost 0 or B[i] with cost cost[i]

Prerequisites:

  • Very basics of Dynamic Programming.

QUICK EXPLANATION:

Its a beginner friendly Problem on Dynamic programming. with very simple recursion relation as the cost of sub-problem β€œ1 to i” , where selecting ith elements from array A would be given by

  • min( cost of selecting i-1 from A , cost of selecting i-1 from B )

and selecting ith element from B would give cost

  • min(cost of selecting i-1 from A, cost of selecting i-1 from B) + cost[i]

–the answer to sub-problem 1 to i is min of above two cases cost if possible else -1.

EXPLANATION:

Firstly For the current index i , we can either choose A[i] or B[i] and the ith element of output array is only possible if at-least one of A[i-1] or B[i-1] is less then or equal to the current selected element .So in worst case we have 2 options to choose for every index and there will be 2^n total cases possibles. iterate over all cases and return min of them is feasible only if N is less then 20 or so .
As the problem involve choosing between options , and solving problem for 1 to i , requires solving for 1 to i-1 , these clearly gives hint of Dynamic Programming . That is simply storing the results of sub-problems , and use them when needed.

Lets start with making two dp array dpA and dpB where , dpA[i] stores the min cost for first i elements , if the ith element is choose from array A and dpB[i] stores min cost for first i elements , if the ith element is choose from array B .
Initialization of dp arrays with infinte (large number) will help to count minimum cost . Also cost for first 0 elements is obviously 0 thus
dpA[0] = dpB[0] = 0
Now Lets assume we are in ith index ,

  • if A[i] is >= A[i-1] we may select A[i] with cost
    dpA[i] = min( dpA[i] , dpA[i-1] ) + 0
  • similarly if A[i] is >= B[i-1] we may select A[i] with cost
    dpA[i] = min( dpA[i] , dpB[i-1] ) + 0

and Also we can choose from array B

  • if B[i] is >= A[i-1] we may select B[i] with cost
    dpB[i] = min( dpB[i] , dpA[i-1] ) + cost[i]
  • similarly if A[i] is >= B[i-1] we may select A[i] with cost
    dpB[i] = min( dpB[i] , dpB[i-1] ) + cost[i]

So the minimum cost for the first i elements will be the min of - cost if ith element is A[i] and cost if ith element is B[i]. i.e.
ans = min(dpA[i] , dpB[i]).
if ans is infinte , that means none above of condition is true , then solution is not possible hence return -1;

when i becomes n , the ans will be solution complete problem.

the above implementation is calculated by iterating i 1 to n using loop and dp arrays (formally called dp-table) to store the previous results : this method is formally called as Bottom-up approach.

Another Implementation of above method is done using recursion and memoization. called Top-down approach i.e Start with bigger sub-problem break down into smaller sub-problem , if they are already solved use them or else solve them(again recursion) and store the results.

SOLUTIONS:

Highly recommend to write code on your own , see below codes only if not getting satisfactory results after 2 -3 tries

Setter's Solution - Top down
const ll N = 4e5;

vector<vector<ll>> dp(N,vector<ll> (2,-1));

vector<ll> A(N) ,B(N) ,cost(N);

// st is the state , i.e. 0 for choosing from A , 1 for B .
ll find(ll n,ll st){  
  // base condition
   if(n==1){

       dp[n][0] = 0;

       dp[n][1] = cost[0]; 

   }

   else{
     // if already solved !!
       if(dp[n][st] !=-1){

           return dp[n][st];

       }
//not solved yet for (n,st) !
       dp[n][st] = INT_MAX;

       if(st){             // slecting ith from array B

           if(spec[n-1]>=spec[n-2]){

               dp[n][st] = min(dp[n][st] , find(n-1,1)) + cost[n-1];

           }

           if(spec[n-1] >= def[n-2]){

               dp[n][st] = min(dp[n][st] , find(n-1, 0)) + cost[n-1];

           }

       }

       else{ // selectnig ith from array A

           if(def[n-1]>=spec[n-2]){

               dp[n][st] = min(dp[n][st] , find(n-1,1));

           }

           if(def[n-1] >= def[n-2]){

               dp[n][st] = min(dp[n][st] , find(n-1, 0));

           }

       }

   }

   return dp[n][st];

}

Tester's Solution - Bottom up
// Suryansh
#include <bits/stdc++.h>
#define ll long long int
#define oo 1000000000000000
using namespace std;

ll a[100000],b[100000],c[100000];
ll dp[100000][2];

void pre(int n){
   dp[0][0]=0 , dp[0][1]=0;
   for(int i=1;i<=n;i++) dp[i][0]=oo , dp[i][1]=oo;
   for(int i=1;i<=n;i++){
       if( a[i] >= a[i-1] ) dp[i][0] = min(dp[i][0] , dp[i-1][0]);
       if( a[i] >= b[i-1] ) dp[i][0] = min(dp[i][0] , dp[i-1][1]);
       if( b[i] >= a[i-1] ) dp[i][1] = min(dp[i][1] , c[i] + dp[i-1][0]);
       if( b[i] >= b[i-1] ) dp[i][1] = min(dp[i][1] , c[i] + dp[i-1][1]);
   }
}

void sol(){
   int n; cin >> n;
   for(int i=1;i<=n;i++) cin >> a[i];
   for(int i=1;i<=n;i++) cin >> b[i];
   for(int i=1;i<=n;i++) cin >> c[i];
   pre(n);
   ll ans = min(dp[n][0] , dp[n][1]);
   if(ans==oo) cout << -1 <<"\n";
   else cout << ans << "\n";
   return;
}

int main() {
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   int t; cin >> t;
   while(t--) sol();
}

4 Likes