PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: practice_track
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
simple
PREREQUISITES:
Permutation cycles
PROBLEM:
You are given a permutation P.
For each i, define val_i via the following process:
- Set val_i = 1 and k = P_i.
- While k \neq i, increment val_i by one and set k to P_k.
You can swap P_i and P_j for a cost of val_i + val_j, after which all the elements of val are recomputed.
Find the minimum cost necessary to maximize the sum \sum_{i=1}^n val_i.
EXPLANATION:
Consider a graph on N vertices with the edges being i\to P_i for every i.
It’s well-known that such a graph looks like a disjoint collection of cycles (if you’re unfamiliar with why, this blog is a good read).
In particular, note that val_i is simply the size of the cycle containing i.
Our aim is to maximize \sum_{i=1}^n val_i, which is clearly at its largest when val_i = N for all i. This occurs only when we have a single cycle of length N.
Now that we know our goal, let’s understand how to get there.
To do this, we must understand how the cycle decomposition changes when P_i and P_j are swapped.
It can be observed that:
- If i and j lie on different cycles, swapping P_i and P_j will essentially merge their cycles together into a single larger cycle of size val_i + val_j.
The new cycle formed is exactly i \to P_j \to \ldots \to j \to P_i \to\ldots \to i, where the \ldots parts are from the previously existing cycles. - If i and j lie on the same cycle, swapping P_i and P_j splits up the cycles into two smaller ones.
Our goal being to have only a single cycle in the end and minimize the cost, it’s never optimal to split up cycles.
So, we only merge cycles.
Note that the cost of merging two cycles is simply the sum of their sizes.
Let’s first find all cycles in P and their lengths - say c_1, c_2, \ldots, c_k.
Now, we want to merge these two at a time till only one is left, but merging creates a new cycle with their sum as its size.
To do so while minimizing the cost, it’s optimal to always choose the two cycles with smallest size.
That is, do the following:
- Let S be a (multi)set of current cycle lengths.
- While S has size \gt 1, extract the two smallest elements of S, add their sum to the answer, and insert their sum back into S.
This is, in fact, nothing but the Huffman encoding algorithm - which is how we know it’s optimal.
Each move can be simulated in \mathcal{O}(\log N) time using a multiset or priority queue, leading to a solution that’s \mathcal{O}(N\log N) overall.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
while(t--)
{
int n; cin >> n;
vector<int> p(n);
for(int i = 0; i < n; i++)
{
cin >> p[i];
p[i]--;
}
vector<int> v(n, 0);
priority_queue<int, vector<int>, greater<int>> cyc;
for(int i = 0; i < n; i++)
{
if(v[i] == 0)
{
int j = i;
int c = 1;
v[i] = 1;
while(v[p[j]] == 0)
{
j = p[j];
v[j] = 1;
c++;
}
cyc.push(c);
}
}
long long ans = 0;
while(cyc.size() > 1)
{
int a = cyc.top();
cyc.pop();
int b = cyc.top();
cyc.pop();
ans += (a+b);
cyc.push(a+b);
}
cout << ans << endl;
}
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
mark = [0]*n
cycles = []
for i in range(n):
if mark[i]: continue
j = i
k = 0
while not mark[j]:
k += 1
mark[j] = 1
j = p[j] - 1
cycles.append(k)
import heapq
heapq.heapify(cycles)
ans = 0
while len(cycles) > 1:
x = heapq.heappop(cycles)
y = heapq.heappop(cycles)
ans += x + y
heapq.heappush(cycles, x + y)
print(ans)