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.

HackerEarth Minimum changes problem solution.

`#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;}`

Second solution

`#include <bits/stdc++.h>using namespace std;typedef long long ll;namespace F{  const int maxn = 2e2 + 17, maxm = 4e4 + 17, so = maxn - 1, sink = maxn - 2;  int head[maxn], to[maxm], prv[maxm], cap[maxm], cost[maxm], q[maxm * maxn], ecnt;  void init(){    memset(head, -1, sizeof head);    ecnt = 0;  }  void add(int v, int u, int cst = 0, int vu = 1, int uv = 0){    prv[ecnt] = head[v], to[ecnt] = u, cap[ecnt] = vu, cost[ecnt] = cst, head[v] = ecnt++;    prv[ecnt] = head[u], to[ecnt] = v, cap[ecnt] = uv, cost[ecnt] = -cst, head[u] = ecnt++;  }  int d[maxn], par[maxn];  bool mark[maxn];  bool spfa(){    memset(d, 63, sizeof d);    d[so] = 0;    int h = 0, t = 0;    q[t++] = so, par[so] = -1;    while(h < t){      int v = q[h++];      mark[v] = 0;      for(int e = head[v]; ~e; e = prv[e])        if(cap[e] && d[to[e]] > d[v] + cost[e]){          d[to[e]] = d[v] + cost[e];          if(!mark[to[e]]){            mark[to[e]] = 1;            q[t++] = to[e];          }          par[to[e]] = e;        }    }    return d[sink] < 1e9;  }  int mincost(){    int ans = 0;    while(spfa())      for(int e = par[sink]; ~e; e = par[to[e ^ 1]])        cap[e]--, cap[e ^ 1]++, ans += cost[e];    return ans;  }}const int maxn = 1e5 + 17, maxk = 112;int n, k, cost[maxk][maxk];void solve(){  F::init();  memset(cost, 0, sizeof cost);  cin >> n >> k;  for(int i = 0; i < n; i++){    int x;    cin >> x;    x--;    for(int j = 0; j < k; j++)      if(j != x)        cost[j][i % k]++;  }  for(int i = 0; i < k; i++){    F::add(F::so, i);    for(int j = 0; j < k; j++)      F::add(i, k + j, cost[i][j]);    F::add(i + k, F::sink);  }  cout << F::mincost() << '\n';}int main(){  ios::sync_with_stdio(0), cin.tie(0);  int t;  cin >> t;  while(t--)    solve();}`