HackerEarth Minimum changes problem solution

In this HackerEarth Minimum changes problem solution You are provided K different tasks and you have to perform a single activity on a single day. The activities are numbered by using the integers 1, 2, … K.

A time table has been provided to you that must be followed for the next N days. The time table states that on the ith day, you should do the job with index A[i]. 1 <= A[i] <= K 

A rule states that if you do some particular job with index X on a day with index Y, then you should not do the same job any time before day Y + K. You cannot perform the job with index X on any day in the range [Y + 1,Y + K – 1] in such a case.

You are required to change the time table in such a way that it also satisfies the mentioned rule. You also have to make the minimum number of changes in the time table. A change involves modifying a job that has to be done on some day i(1<=i<=N) to any other job in the range of 1…K. Your task is to determine this minimum number.

#include<bits/stdc++.h>

using namespace std;

typedef complex<double> base;
typedef long double ld;
typedef long long ll;
typedef vector<int> VD;
typedef vector<VD> VVD;

#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >

const int maxn=(int)(2e5+5);
const ll mod=(ll)(1e9+7);
int a[maxn];
int cnt[105][105],cost2[105][105];
int n,k;

VD MinCostMatching(int n)
{
    VVD cost;

    for(int i=0;i<n;i++)
    {
        vector<int> now;

        for(int j=0;j<n;j++)
        {
            now.pb(cost2[i][j]);
        }

        cost.pb(now);
    }

    VD Lmate, Rmate;

    // construct dual feasible solution
    VD u(n);
    VD v(n);
    for (int i = 0; i < n; i++) {
        u[i] = cost[i][0];
        for (int j = 1; j < n; j++) u[i] = min(u[i], cost[i][j]);
    }
    for (int j = 0; j < n; j++) {
        v[j] = cost[0][j] - u[0];
        for (int i = 1; i < n; i++) v[j] = min(v[j], cost[i][j] - u[i]);
    }

    // construct primal solution satisfying complementary slackness
    Lmate = VD(n, -1);
    Rmate = VD(n, -1);
    int mated = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (Rmate[j] != -1) continue;
            if (fabs(cost[i][j] - u[i] - v[j]) < 1e-10) {
                Lmate[i] = j;
                Rmate[j] = i;
                mated++;
                break;
            }
        }
    }

    VD dist(n);
    VD dad(n);
    VD seen(n);

    // repeat until primal solution is feasible
    while (mated < n) {

        // find an unmatched left node
        int s = 0;
        while (Lmate[s] != -1) s++;

        // initialize Dijkstra
        fill(dad.begin(), dad.end(), -1);
        fill(seen.begin(), seen.end(), 0);
        for (int k = 0; k < n; k++)
            dist[k] = cost[s][k] - u[s] - v[k];

        int j = 0;
        while (true) {

            // find closest
            j = -1;
            for (int k = 0; k < n; k++) {
                if (seen[k]) continue;
                if (j == -1 || dist[k] < dist[j]) j = k;
            }
            seen[j] = 1;

            // termination condition
            if (Rmate[j] == -1) break;

            // relax neighbors
            const int i = Rmate[j];
            for (int k = 0; k < n; k++) {
                if (seen[k]) continue;
                const double new_dist = dist[j] + cost[i][k] - u[i] - v[k];
                if (dist[k] > new_dist) {
                    dist[k] = new_dist;
                    dad[k] = j;
                }
            }
        }

        // update dual variables
        for (int k = 0; k < n; k++) {
            if (k == j || !seen[k]) continue;
            const int i = Rmate[k];
            v[k] += dist[k] - dist[j];
            u[i] -= dist[k] - dist[j];
        }
        u[s] += dist[j];

        // augment along path
        while (dad[j] >= 0) {
            const int d = dad[j];
            Rmate[j] = Rmate[d];
            Lmate[Rmate[j]] = j;
            j = d;
        }
        Rmate[j] = s;
        Lmate[s] = j;

        mated++;
    }

    int value = 0;
    for (int i = 0; i < n; i++)
        value += cost[i][Lmate[i]];

    return Lmate;
}

void reset(int k)
{
    for(int i=0;i<k;i++)
    {
        for(int j=0;j<k;j++)
        {
            cnt[i][j]=0;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    int t;cin>>t;

    while(t>0)
    {
        cin>>n>>k;

        for(int i=0;i<n;i++)
        {
            cin>>a[i];

            a[i]--;

            cnt[i%k][a[i]]++;
        }

        for(int i=0;i<k;i++)
        {
            for(int j=0;j<k;j++)
            {
                cost2[i][j]=(n/k)+((i<(n%k))?1:0)-cnt[i][j];
            }
        }

       // cout<<"hello"<<endl;

        vector<int> res=MinCostMatching(k);

        int tot=0;

        for(int i=0;i<k;i++)
        {
            tot+=cost2[i][res[i]];
        }

        cout<<tot<<endl;

        reset(k);

        t--;
    }

    return 0;
}