# PROBLEM LINK:

*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();
}
```