Codeforces 1215 E

Posted on | | 阅读数 次
Words count in article: 1.4k | Reading time ≈ 7

E. Marbles

开启传送门

题目描述

Monocarp has arranged $n$ colored marbles in a row. The color of the $i$-th marble is $a_i$. Monocarp likes ordered things, so he wants to rearrange marbles in such a way that all marbles of the same color form a contiguos segment (and there is only one such segment for each color).

In other words, Monocarp wants to rearrange marbles so that, for every color $j$, if the leftmost marble of color $j$ is $l$-th in the row, and the rightmost marble of this color has position $r$ in the row, then every marble from $l$ to $r$ has color $j$.

To achieve his goal, Monocarp can do the following operation any number of times: choose two neighbouring marbles, and swap them.

You have to calculate the minimum number of operations Monocarp has to perform to rearrange the marbles. Note that the order of segments of marbles having equal color does not matter, it is only required that, for every color, all the marbles of this color form exactly one contiguous segment.

Input

The first line contains one integer $n$ ($2≤n≤4\cdot10^5$) — the number of marbles.

The second line contains an integer sequence $a_1, a_2, \dots, a_n$($1≤a_i≤20$), where $a_i$ is the color of the $i$-th marble.

Output

Print the minimum number of operations Monocarp has to perform to achieve his goal.

Examples

input1

7

3 4 2 3 4 2 2

output1

3

input2

5

20 1 14 10 2

output2

0

input3

13

5 5 4 4 3 5 7 6 5 4 4 6

5

output3

21

Note

In the first example three operations are enough. Firstly, Monocarp should swap the third and the fourth marbles, so the sequence of colors is $[3,4,3,2,4,2,2]$. Then Monocarp should swap the second and the third marbles, so the sequence is $[3,3,4,2,4,2,2]$. And finally, Monocarp should swap the fourth and the fifth marbles, so the sequence is $[3,3,4,4,2,2,2]$.

In the second example there’s no need to perform any operations.

题意

zuhiul认识很多妹子，显然不同的妹子有不同的颜值（颜值最高为20，最小为1），有一天他把他认识的所有妹子召集在一起（不超过$4\cdot 10^5$个），她们站成一排。现在zuhiul想把颜值相同的妹子放在一起，但是妹子们都在玩手机，所以他只能每次叫两个相邻的妹子配合一下交换。现在问你最小交换次数，使得所有颜值相同的妹子坐在一起。

分析

当时没做出来，看的题解（orz）， 所以先给官方题解，强烈建议先看官方题解。

The main fact is that the number of colors is less than $20$, which allows us to use exponential solutions.

For each pair of colors $(i,j)$, we can calculate $cnt[i][j]$ — the number of swaps required to place all marbles of color $i$ before all marbles of color $j$ (if we consider only marbles of these two colors). 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 colors. Let $d[mask]$ be the minimum number of operations to correctly order all marbles from the $mask$ of colors. 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 marbles of this color after all marbles 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 𝑠𝑢𝑚 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 colors, and that is $d[2^{20}-1]$.

因为看的题解，所以没想出第二种解法，用我的话复述一下。

因为不同的颜值数量很少（$<=20$)，所以我们可以在这个方向上下文章。

如果考虑只有两种颜色，我们可以很轻易的知道答案是多少（通过枚举每个不同的位置算贡献）。

于是考虑可以用状压DP来搞，$dp[i]$表示状态为 $i$ 的时候的代价。那么答案显然是$d[2^{20}-1]$.

考虑转移，枚举每个已知答案的子集。我们怎么推算下一个状态的答案呢？

显然是往里面加了一个之前没有的值。我们不妨设当前状态为$mask$，当前新加的是 $i$ ， $i$ 加进来的代价是 $sum$ 。那么新状态显然就是$nmask=mask|(1<<i)$。并且我们有$ans[nmask] = min(ans[nmask], ans[mask]+sum)$。

剩下的就是考虑怎么算 $sum$。 记得我们刚刚说的吗？对于两种颜值我们怎么计算的？利用两种颜值的计算方法，我们可以预处理处一个代价矩阵$cnt[i][j]$,表示只考虑 $i$ 和 $j$ 两种颜值，我们把这两堆人排好序（ $i$ 在前，$j$ 在后）的代价。

然后可以得到 $ sum = \sum_{j\in mask}^{} cnt[i][j]$

over.

代码

给大佬递上我奇丑无比的代码　(/ω＼)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int n;
const int maxm = 1e6;
const long long inf = 1e18;
vector<long long> mat[22];
long long value[22][22];
long long ans[1<<21];
int main(){
    scanf("%d",&n);
    for(int i = 0, a;i<n;i++) {
        scanf("%d",&a);
        mat[a].push_back(i);
    }
    for(int i = 0;i<=20;i++) mat[i].push_back(maxm<<1);
    for(int i = 1;i<=20;i++) {
        if(mat[i].size()==0) continue;
        for(int j = 1;j<=20;j++) {
            if(mat[j].size()==0||i==j) continue;
            long long ind1 = 0;
            for(auto ind : mat[j]) {
                if(ind > maxm) continue;
                while(ind > mat[i][ind1]) ind1++;
                value[i-1][j-1] += ind1;
            }
        }
    }
    for(int i = 0;i<(1<<20);i++) ans[i] = inf;
    ans[0] = 0;
    for(int mask = 0;mask<(1<<20);mask++) {
        vector<int> has_bit;
        for(int i = 0;i<20;i++) if(mask&(1<<i)) has_bit.push_back(i);
        for(int i = 0;i<20;i++){
            if(mask&(1<<i)) continue;
            long long sum = 0;
            for(int j = 0;j<has_bit.size();j++) sum+=value[i][has_bit[j]];
            int nmask = mask|(1<<i);
            ans[nmask] = min(ans[nmask], ans[mask]+sum);
        }
    }
    printf("%lld\n", ans[(1<<20)-1]);
    return 0;
}