Help on a problem from contest CodeIngen

Kindly help me with the solution of this problem from IIT BHILAI coding contest

Contest Page | CodeChef.
Thanks in advance…
@ssrivastava990 @shubham_avasth @taran_1407 @shashwat07…kindly help me if you find time…

1 Like

Anyone else interested kindly help me

sorry bro , not able to do … can u please help @tamo11 @carre

Thanks for your response Sir. Hope someone else sees this…

Well, you can make 2D dp[i][j] which denotes the minimum number of changes you need to make in array [1..i] such that you have atmost j indices satisfying that condition(A_k != A_{k+1}). Then you have the recursion: dp[i][j] = \min\limits_{x=0}^{i-1} dp[i-x-1][j-1] + x+1-f, where f denotes the frequency of element which occurs maximum number of times. What I am doing here is that I am considering the interval [i-x, i] with same element, finding changes in this interval and then using pre-computed answer for [1..i-x-1].
You can construct this dp in O(K*N^2*log(N)).

AC Code
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n, k;
        cin >> n >> k;
        int arr[n+1];
        int i;
        for(i=1;i<=n;i++)   
            cin >> arr[i];
        int dp[n+1][k+1], freq[1001] = {0};
        int j;
        for(i=0;i<=n;i++)
            for(j=0;j<=k;j++)
                dp[i][j] = 1e9;
        set<pair<int, int>> s;
        for(j=0;j<=k;j++)
            dp[0][j] = 0;
        for(i=1;i<=n;i++)
        {
            int cnt = freq[arr[i]];
            if(s.find({cnt, arr[i]}) != s.end())
                s.erase({cnt, arr[i]});
            freq[arr[i]]++;
            cnt = freq[arr[i]];
            s.insert({cnt, arr[i]});
            pair<int, int> p = *s.rbegin();
            dp[i][0] = (i - p.first);
        }
        for(i=1;i<=n;i++)
            for(j=1;j<=k;j++)
            {
                map<int, int> mp;
                s.clear();
                for(int x = 0; x < i; x++)
                {
                    if(mp.find(arr[i-x]) != mp.end())
                        s.erase({mp[arr[i-x]], arr[i-x]});
                    mp[arr[i-x]]++;
                    s.insert({mp[arr[i-x]], arr[i-x]});
                    pair<int, int> p = *s.rbegin();
                    dp[i][j] = min(dp[i][j], dp[i-x-1][j-1] + x+1-p.first);
                }
            }
        cout << dp[n][k] << '\n';
    }
}
4 Likes

Aaareww Sir,many many thanx