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();
}
0 Comments