0 like 0 dislike
3,529 views

Image of Question ::

| 3,529 views

0 like 0 dislike

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 ;
}```
by Expert (111,350 points)
0 0
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;
}