Aesthetic Permutation | Triology | CodeNation | Coding | OA | SDE | Set-36 | 2023 | Hard | Greedy + Dynamic-Programming | Jan 8

Question

Answer 1

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
ll dp[5005][5005] ;
ll diff[500000+5];

ll kk(ll y,ll g){
    
    ll vv = 0 ; 
    vv = abs(diff[g] - diff[y]);
    return vv ; 
    
    
}

int main() {
    
    ll n ; 
    cin>>n ; 
    ll k;
    cin>>k ; 
    ll b[n+1] = {0};
    ll i = 1 ; 
    while(i<=n){
        cin>>b[i] ; 
        i++;
    }
    
    ll p1 = n/k ;//....g 
    ll p2 = n/k + 1 ; //...g+1...
    ll k2 = 0 ;//count of g..basically x.. 
    ll k5 = 0 ; //count of g+1...basically y..
    i = 1 ; 
    while(i<=k) {
        ll vv = (n-i)/k ; 
        vv++;
        if(vv==p1){
            k2++;
        }
        if(vv==p2){
            k5++;
        }
        i++;
    }
    cout<<k2<<" "<<k5 ;
    cout<<"\n"; 
    
   
    sort(b+1,b+n+1);
    
    i = 2 ; 
    while(i<=n){
        ll gg = abs(b[i]-b[i-1]);
        diff[i] = diff[i-1] + gg ;//diff is p-s[]
        i++;
    }
    
    
    
    
    i = 1 ; 
    while(i<=k2){
        
         ll sum = i*p1 + 0*p2;
        ll g = sum ; 
        ll y = (sum - p1 + 1 );
        
        dp[i][0] = dp[i-1][0] + kk(y,g); //base_case...
        
        i++;
    }
    
    
    i = 1 ; 
    while(i<=k5){
        
         ll sum = 0*p1 + i*p2;
        ll g = sum ; 
        ll y = (sum - p2 + 1);
        
        dp[0][i] = dp[0][i-1] + kk(y,g); //base_case...
        
        i++;
    }
    
    
    
    
    
    
    
    
  
    i = 0 ; 
    while(i<=k2){
     ll j = 0 ; 
     while(j<=k5){
         
         
         ll sum = i*p1 + j*p2 ; 
         
         if(sum!=0){
             ll v5 = 1e18 ; 
             if(j>=1){
             //focus on j part....
             
             ll g = sum ; 
             ll y = (sum - p2 + 1 );
             v5 = dp[i][j-1] + kk(y,g);
             }
             ll v8 = 1e18 ; 
             
             if(i>=1){
                 
                  ll g = sum ; 
             ll y = (sum - p1 + 1 );
             v8 = dp[i-1][j] + kk(y,g);
                 
                 
             }
             
             
             dp[i][j] = min(v5,v8);
             
             
         }
         
         
         
         j++;
     }
     i++;   
    }
        
        
        
        
        
        
        
    
    cout<<dp[k2][k5];
    
    
    /*
    
    15 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

5
-5 -5 3 3 3 

    
    
    */
    
    
    

    
    return 0 ; 
}

Answer 2

Problem Q go through this  :