PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Arthur Nascimento
Tester: Danya Smelskiy
Editorialist: Arthur Nascimento
DIFFICULTY:
MEDIUM
PREREQUISITES:
Bitmasks, DP, Permutations
PROBLEM:
You are given a permutation and a list of free pairs of indices. Find the minimum number of swaps you need in order to sort it, given that the pairs in the list can be swaped intantly (ie. these swaps don’t account in the answer)
Notice:
This problems requires some familiarity with the concept of permutation cycles.
This video gives a good intuition on the subject, and also
explains the solution for the first subtask
QUICK EXPLANATION
- The robot operations induces a graph, where each vertex is a position, and each edge is a possible swap
- For every connected component of the graph, we can freely permute its elements
- The answer is the minimum number of swaps so that each vase ends up on its component
- This induces a new directed graph, where each vertex is a connected component, and each directed edge is a vase
- A directed cycle of size S can be fixed in S-1 operations, so we must find a partition of edges that maximizes the number of cycles
- This can be done with bitmask dp
EXPLANATION
It is a nice idea to think of the robot operations as a graph, where each vertex is a position, and each edge is a possible swap,
because it will make us understand what cases can be solved in 0 minutes. On one hand, it is clear that if some vase must end up on
a different connected component of this graph, the answer must be greater than 0. But it turns out that, if all vases are already in
their component, the answer will be 0.
This can be proved constructively by the following algorithm:
- Find any spanning tree of the component
- Pick any leaf, and by a sequence a swaps, make this position correct (ie. find the vase that should end up in this position, and put it there)
- Delete this leaf from the tree, and continue recursively
Of course, since the problem does not require you to output a valid answer, one didn’t have to formally prove this, but just have enough
intuition to get convinced this is true.
Because of this, we conclude that all operations that Chef does will swap vases that are on different components, and therefore we must minimize the
number of swaps so that each vase ends up on its component
We know from subtask 1 that, if M = 0, a cycle of size S can be fixed in S-1 operations. This logic also applies here of course, but the problem here is that our graph may have
a strange format, and cycles might intersect, so it is not clear what we should do. If we select a disjoint set of cycles that cover all edges in the graph, we could fix all these
cycles, one by a time, and we would manage to solve the problem in N - C minutes, where C is the number of cycles. Since this solution somewhat resembles the algorithm for
solving the case where M = 0, one might conjecture the following statement:
- The answer is N - MAXC, where MAXC os the maximum number of cycles that we can partition our edges into.
(Again, notice contestants were not supposed to come up with a formal mathematical proof of this during the contest.)
This is in fact true, and the proof that we can’t do better than this (ie. the answer is not smaller than N - MAXC) can be done by the following claim:
- Let K be a variable representing, for a current state of our graph, the maximum possible number of cycles in a partition. Then:
-
If each vase is already on its component, K = N
-
Every time Chef makes an operation, K will increase at most by 1 (it may decrease, but it will never increase by more than 1)
Proof:
-
is true because all cycles have length 1
-
can be proved constructively: Let K_0 be the value of K before an operation, and K_1 be the value after it. We can use the optimal partition after the swap, modifying only the edges
that changed in the graph, to find a partition in the old graph with at least K_1-1 cycles. This implies that K_0 \geq K_1-1
This claim directly proves that the answer is N - MAXC
Now, finally, we have reduced our problem to finding the value of MAXC. The constraints are small, which suggests an approach that considers all possible partitions. Although backtracking
may be too slow, we can indirectly try all possibilities using dynamic programming with bitmasks. The state of the dp is the following:
- DP[ini][cur][unused], where ‘ini’ and ‘cur’ are vertices and ‘unused’ is a mask representing a subset of edges,
and this will return us the maximum number of cycles, given that we we want to partition the edges in unused into several cycles and a path from ini to cur.
This dp can be done in O(N^2*2^N) complexity
SOLUTIONS:
Setter
#include <bits/stdc++.h>
#define maxn 18
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define debug(args...)
using namespace std;
int p[maxn];
vector<int> L[maxn];
int vis[maxn];
int comp[maxn];
void dfs(int vx,int c){
vis[vx] = 1;
comp[vx] = c;
for(int i : L[vx])
if(!vis[i])
dfs(i,c);
}
vector<pii> G[maxn];
char dp[maxn][maxn][1<<maxn];
char get(int ini,int cur,int mask){
char &ans = dp[ini][cur][mask];
if(ans+1) return ans;
if(ini == cur && mask == 0)
return 1;
if(ini == cur){
for(int i=0;i<maxn;i++)
if(mask & (1<<i))
ans = max(ans, char (1 + get(comp[i],comp[p[i]],mask-(1<<i))));
}
else
for(pii i : G[cur]){
if(mask & (1<<i.second))
ans = max(ans, get(ini,i.first,mask-(1<<i.second)));
debug("at %d %d %d to %d %d\n",ini,cur,mask,i.first,i.second);
}
if(ans == -1) ans = 0;
debug("ini %d cur %d mask %d ans %d\n",ini,cur,mask,ans);
return ans;
}
int main() {
int nt;
scanf("%d",&nt);
while(nt--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%d",p+i), p[i]--;
vis[i] = comp[i] = 0;
G[i].clear();
L[i].clear();
}
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b), a--, b--;
L[a].pb(b);
L[b].pb(a);
}
int c = 0;
for(int i=0;i<n;i++)
if(!vis[i]){
dfs(i,c);
c++;
}
for(int i=0;i<n;i++){
G[comp[i]].pb({comp[p[i]],i});
debug("%d -> %d (%d)\n",comp[i],comp[p[i]],i);
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<(1<<n);k++)
dp[i][j][k] = -1;
int ans = 0;
for(int i=0;i<n;i++)
ans = max(ans, int (get(comp[i],comp[p[i]], (1<<n) - 1 - (1<<i))));
printf("%d\n",n-ans);
}
}
Tester
#include <iostream>
#include <string>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, k;
int p[20];
int dsu[20];
vector<pair<int, int> > e;
int dp[(1 << 18) + 5];
int nxt[20];
int cnt[20];
bool used[20];
int get_anc(int x) {
if (x == dsu[x]) return x;
return dsu[x] = get_anc(dsu[x]);
}
void dfs(int x) {
if (used[x]) return;
used[x] = true;
if (nxt[x])
dfs(nxt[x]);
}
bool is_simple_cycle(int mask) {
for (int i = 0; i < n; ++i) {
cnt[i] = 0;
used[i] = false;
nxt[i] = 0;
}
for (int i = 0; i < k; ++i)
if (mask & (1 << i)) {
int x = e[i].first;
int y = e[i].second;
++cnt[x];
++cnt[y];
nxt[x] = y;
}
for (int i = 0; i < n; ++i)
if (cnt[i] != 0 && cnt[i] != 2) return false;
for (int i = 0; i < n; ++i) if (cnt[i]) {
dfs(i);
break;
}
for (int i = 0; i < n; ++i)
if (cnt[i] && !used[i]) return false;
return true;
}
void solve(int test_id) {
scanf("%d %d\n", &n, &m);
for (int i = 0; i < n; ++i) {
if (i) scanf(" ");
scanf("%d", &p[i]);
--p[i];
}
for (int i = 0; i < n; ++i) {
dsu[i] = i;
}
for (int i = 0; i < m; ++i) {
int x, y;
scanf("%d %d\n", &x, &y);
--x; --y;
x = get_anc(x);
y = get_anc(y);
if (x != y) dsu[x] = y;
}
e.clear();
for (int i = 0; i < n; ++i) {
int x = i;
int y = p[i];
x = get_anc(x);
y = get_anc(y);
if (x != y) e.push_back({x, y});
}
k = (int)e.size();
for (int i = 1; i < (1 << k); ++i) {
if (is_simple_cycle(i)) {
dp[i] = 1;
} else dp[i] = 0;
}
for (int i = 1; i < (1 << k); ++i) {
for (int j = i; j > 0; j = (j - 1) & i) {
if (dp[j] && dp[i ^ j])
dp[i] = max(dp[i], dp[j] + dp[i ^ j]);
}
}
int result = (int)e.size() - dp[(1 << k) - 1];
printf("%d\n", result);
}
int main(int argc, const char * argv[]) {
#ifdef __APPLE__
freopen("/Users/danya.smelskiy/Documents/Danya/Resources/input.txt","r",stdin);
#endif
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int tests;
scanf("%d\n", &tests);
for (int i = 0; i < tests; ++i) {
solve(i);
}
return 0;
}
