HackerEarth Minimum changes problem solution YASH PAL, 31 July 2024 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();} coding problems