SORTVS - Editorial

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:
  1. If each vase is already on its component, K = N

  2. 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:

  1. is true because all cycles have length 1

  2. 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;
}
 
12 Likes

Why Greddily Solving 1 length cycles then 2 length cycles then 3 length cycles and so on does not work with the help of DSU ? Please give me some motivation to go for dp not for greedy in this problem?

4 Likes

I have tried using shortest path algo to travel no. from current index to desired index.
i.e selection sort but swapping through a series of indices(shortest route). It passed only 1st subtask.
Can anyone explain why this approach is not enough.
Thank you…!

@arthurfn @smelskiy I have same query. Why will greedy won’t work ?
I have found all the connected components and then I find cycles of elements b/w different connected components. Size=2 cycle ,size=3 cycle and so on. I will swap elements when I find a cycle.

3 Likes

yes i have also find the connected components and done it but WA for last task

instead of using Bitmasks DP, I Formed two graphs, one for the ones connected by the robot and the other one for where the elements should be, like if an element is in family 1 and it needs to go to an element in family 2 (family refers to all the points connected by the first graph), so family one is connected to family 2 with a weight equal to how many elements need to go there.
afterward, I just removed all possible cycles in the graph.
Here’s my solution :
https://www.codechef.com/viewsolution/32972265
It was a great question really, awesome work, problem setters :smile:

1 Like

WHAT IF U HAVE A NODE THAT MAKE 3 LENGTH CYCLE WITH MANY NODES NODES ,YOU SHOULD TAKE ONLY ONE OF THEM WHICH DEPENDS ON OTHER NODES ,SO WHEN WE WILL HAVE MULTIPLE EQUAL LENGTH CYCLES THEN IT WILL CREATE AN ISSUE

I see, thanks.

An amazing thing is that I used the Simulated Annealing algorithm and passed this problemlink

1 Like

I also used the connected component approach using graph for robot moves.
but instead of splitting the cycles, first I enlarged the cycle by free swaps between two cycles and then split it using any free swaps and checking which one gives minimum count.
solution

What does

#define debug(args...)

mean? @arthurfn

Loved solving this problem (and all the others as well).

The freakishly amazing moment was when I drew the highlighted graph and realized that I don’t just have to count the number of cycles but the maximum number of cycles.

Here’s a more clear graph.


There are two ways to select cycles in this graph, either you select 2 yellow cycles or you can select 3 green cycles. Our code must prefer the 3 green cycles over 2 yellow cycles.

10 Likes

Can anyone please review my code. I tried a lot but still wasn’t able to clear the subtask 3. TLE was the main problem for me.
Please review it: My Solution

It was an interesting problem though.
Thank you

I think the following input gives you a counterexample:

1
12 3
5 8 1 10 3 12 4 7 6 9 2 11
1 2
3 4
5 6

In the final directed graph, you’ll have a cyclical triangle, where each of the sides also belongs to cyclical square. If you greedily pick the triangle, then you’ll be left with a single cycle of size 9 (made of the 3 remaining sides of each square). However, the optimal solution is to pick the 3 squares instead.

1 Like

Looking for video tutorial for this problem. Anyone please?

3 Likes

This is one of the test case in TEST#9 Subtask 3:
1
17 6
3 9 16 5 14 2 13 8 1 11 7 6 15 10 4 12 17
8 9
8 17
3 13
5 7
6 17
11 16

This is a counter example of Greedy approach ( taking ascending order of cycle size like 2 , 3 , 4 , 5… , …18).

1 Like

Hi All,
Can you please let me know what should be the answer for the following test case?
1
16 8
3 1 5 7 12 15 4 2 8 11 14 16 13 6 10 9
2 13
3 14
3 6
12 16
11 16
2 7
10 13
5 14

according to my logic it is 9 but some successful submission shows 8.
Any help is appreciated

Tried Exactly same. https://www.codechef.com/viewsolution/32797189
Didn’t work

What’s wrong with my aproach ,

  1. Get SCC using graph.( robot swaps that are connected ).

  2. Now we keep what we have and what we want .

  3. Now swap among the SCCs …cost = 0;

  4. Now see if there is any among SCCs which is not at correct place but if placed at a pos’n which would correct it in one move…this is one optimal step. cost = 0;

5 now perform the greedy approach. cost++;

https://www.codechef.com/viewsolution/32797189

This gave me correct ans on the testcases I tested on.

According to my logic also the answer is 9…don’t know why. :wink: :wink: