PROBLEM LINK: FEBCON03
Author, Tester, Editorialist: John Zakkam
DIFFICULTY: EASY-MEDIUM
PREREQUISITES:
PROBLEM:
Tracy has N dolls and arranged has arranged them in a row. Every doll has a hair stye and some dolls can have same hair styles also. The hairstyle of ith doll is represented by ai. Now, Tracy wants to rearrange the dolls such that the dolls with same hairstyle come together.
To achieve his goal, Tracy can do the following operation any number of times: choose two neighboring dolls, and swap them. We have to calculate the minimum number of operations Tracy has to perform to rearrange the dolls. Note that the order of segments of dolls having same hairstyle does not matter, it is only required that, for every hairstyle, all the dolls of this hairstyle form exactly one contiguous segment.
You have to print the minimum number of operations Tracy has to perform to achieve his goal.
EXPLANATION:
The main fact is that the number of haircuts is less than 20, which allows us to use exponential solutions.
For each pair of haircuts (i,j), we can calculate cnt[i][j] — the number of swaps required to place all dolls of color i before all dolls of color j
(if we consider only dolls of these two haircuts). We can store a sorted vector for each color, and calculate this information for a fixed pair with two pointers.
Then let’s use subset DP to fix the order of haircuts. Let d[mask]
be the minimum number of operations to correctly order all dolls from the mask of haircuts. Let’s iterate on the next color we consider — it should be a position in binary representation of mask with 0 in it. We will place all dolls of this color after all dolls we already placed. If we fix a new color i, let’s calculate the sum (the additional number of swaps we have to make) by iterating on the bit j equal to 1 in the mask, and increasing sum by cnt[j][i] for every such bit. The new state of DP can be calculated as nmask=mask|(1«i). So the transition can be implemented as d[nmask]=min(d[nmask],d[mask]+sum).
The answer is the minimum number of swaps required to place all the haircuts, and that is d[220−1].
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define ll long long
#define uint unsigned
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
using namespace std;
int n,x,S[25];
ll pr[25][25],f[(1<<20)];
int main()
{
scanf("%d",&n);
For(i,1,n){
scanf("%d",&x); --x;
For(j,0,19) if (x!=j) pr[j][x]+=S[j];
++S[x];
}
memset(f,60,sizeof(f));
f[0]=0;
For(i,0,(1<<20)-1)
For(j,0,19) if (!(i&(1<<j))){
ll s=f[i];
For(k,0,19) if (i&(1<<k))
s+=pr[j][k];
f[i|(1<<j)]=min(f[i|(1<<j)],s);
}
printf("%lld\n",f[(1<<20)-1]);
}