Google | OA Coding Questions and Solutions | Set - 19 | 2022

Question

Image of Question :: 

 

Answer 1

Time Complexity : O(n*8) ~ O(n)

Multi-dimensional dynamic programming with eigth transition states.. 

C++ 

Code 

:

:

#include<bits/stdc++.h>
using namespace std ;
typedef long long int ll ; 
ll dp[200000][10];
ll a[200000];
int main() {

    ll n,k;
    cin>>n>>k ; 
    ll i = 1 ; 
    while(i<=n){
        cin>>a[i];
        i++;
    }
    
    if(a[1]<k || a[2]<k || a[3]<k){
         dp[3][1] = 1e18 ; 
    } else {
       
    }
    
    if(a[3]<=k){
        dp[3][2] = abs(a[3]-k) ;
    } else {
        
    }
    
    
    if(a[2]<=k){
        dp[3][3] = abs(a[2]-k) ;
    } else {
        
    }
    
    if(a[1]<=k){
        dp[3][4] = abs(a[1]-k) ;
    } else {
        
    }
    
    
    ll gg = 0 ; 
    if(a[1]<=k){
        gg = gg + abs(a[1]-k); 
    }
    if(a[2]<=k){
        gg = gg + abs(a[2]-k); 
    }
    dp[3][5] = gg ; 
    
    
     gg = 0 ; 
    if(a[1]<=k){
        gg = gg + abs(a[1]-k); 
    }
    if(a[3]<=k){
        gg = gg + abs(a[3]-k); 
    }
    dp[3][6] = gg ; 
    
    gg = 0 ; 
    if(a[2]<=k){
        gg = gg + abs(a[2]-k); 
    }
    if(a[3]<=k){
        gg = gg + abs(a[3]-k); 
    }
    dp[3][7] = gg ; 
    
    
    
    gg = 0 ; 
    if(a[1]<=k){
        gg = gg + abs(a[1]-k); 
    }
    if(a[2]<=k){
        gg = gg + abs(a[2]-k); 
    }
    if(a[3]<=k){
        gg = gg + abs(a[3]-k); 
    }
    dp[3][8] = gg ; 
    

    i = 4 ; 
    while(i<=n){

    dp[i][1] = min(dp[i-1][1],dp[i-1][4]);
    if(a[i]<k){
        dp[i][1]=1e18 ; 
    }

    dp[i][2] = min(dp[i-1][1],dp[i-1][4]) ; 
    if(a[i]<k){
        dp[i][2]+=abs(a[i]-k);
    }

    dp[i][3] = min(dp[i-1][2],dp[i-1][6]) ;
    
    
    

    dp[i][4] = min(dp[i-1][3],dp[i-1][5]);

    dp[i][5] = min(dp[i-1][7],dp[i-1][8]);
    
    

    dp[i][6] = min(dp[i-1][3],dp[i-1][5]);
    if(a[i]<k){
        dp[i][6]+=abs(a[i]-k);
    }
    
    

    dp[i][7] = min(dp[i-1][2],dp[i-1][6]);
    if(a[i]<k){
        dp[i][7]+=abs(a[i]-k);
    }

    dp[i][8] = min(dp[i-1][7],dp[i-1][8]);
    if(a[i]<k){
        dp[i][8]+=abs(a[i]-k);
    }

    i++;
    }
    ll vv = 1e18 ; 
    i = 1 ; 
    while(i<=8){
        
        //cout<<dp[n][i];
        vv = min(vv,dp[n][i]);
        //cout<<"\n";
        i++;
    }

    cout<<vv ; 

    return 0 ; 
}

Comments

I don't think we nee the information about past three index. We can solve it using dynamic programming in which we store a state which is defined by index and whether last two index values are greater than k or not.
It will take N * 4 space.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5, INF = 1e9;
int dp[N][4], a[N], n, k;
int call(int i, int j) {
    if(i == n)return 0;
    int &ans = dp[i][j];
    if(ans != -1)return ans;
    ans = INF;
    if(j) {
        int p = 0;
        if(j % 2)p = 2;
        ans = min(ans, call(i + 1, p));
        if(a[i] <= k) {
            ans = min(ans, call(i + 1, p + 1) + (k + 1 - a[i]));
        }
        else {
            ans = min(ans, call(i + 1, p + 1));
        }
    }
    else {
        if(a[i] <= k) {
            ans = min(ans, call(i + 1, 1) + (k + 1 - a[i]));
        }
        else {
            ans = min(ans, call(i + 1, 1));
        }
    }
    return ans;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k;
    k--;
    for(int i = 0; i < n; ++i) {
        cin>>a[i];
    }
    memset(dp, -1, sizeof(dp));
    if(n < 3) {
        cout<<0;
        return 0;
    }
    int ans = INF;
    for(int i = 0; i < 4; ++i) {
        int val = 0, f = 0;
        for(int j = 0; j < 2; ++j) {
            if((j == 0) && (i & (1ll << j))) {
                if(a[1] <= k) {
                    val += (k + 1 - a[1]);
                }
                f += 1;
            }
            if((j == 1) && (i & (1ll << j))) {
                if(a[0] <= k) {
                    val += (k + 1 - a[0]);
                }
                f += 2;
            }
        }
        ans = min(ans, val + call(2, f));
    }
    cout<<ans;
    return 0;
}