PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Anshu Garg
Tester: Danny Mittal
Editorialist: Nishank Suresh
DIFFICULTY:
Medium
PREREQUISITES:
Cycle decomposition of a permutation, Greedy algorithms
PROBLEM:
Alice and Bob have copies of the same permutation P. Further, Alice has a potential array V. They take turns doing the following, with Alice starting:
- On Alice’s turn, she can swap P_i and P_j for any two indices i and j such that V_i > 0 and V_j > 0, after which V_i and V_j decrease by 1.
- On Bob’s turn, he can swap P_i and P_j for any two indices i and j.
Determine who manages to sort their permutation first, and a sequence of their moves achieving this minimum.
QUICK EXPLANATION:
If the cycle decomposition of the permutation consists of C disjoint cycles, Bob can sort it in N - C moves (using s-1 moves for a cycle of size s).
Alice wins if and only if she can also sort the permutation in N - C moves, which requires her to also be able to sort a cycle of size s in s-1 moves. It can be shown that this is possible if and only if the sum of potentials of all vertices in a cycle of size s is at least 2s-2, and the moves can be constructed greedily.
EXPLANATION:
A common idea when dealing with permutations is to look at the cycle decomposition of the permutation, which is a graph constructed on N vertices with edges i \to p_i.
Since p is a permutation, every vertex has exactly one out edge and exactly one in edge, which is only possible if the graph looks like a bunch of disjoint cycles.
Let’s ignore the potentials for now, and concentrate on finding the minimum number of swaps needed to sort the permutation (which also happens to be the number of moves Bob needs).
How many moves to sort a permutation?
Each cycle of size s can trivially be sorted using s-1 moves - for example, if the cycle is a_1 \to a_2 \to \dots \to a_s \to a_1 it can be sorted by swapping the following pairs in order:
Adding this up over all cycles, we can see that for a permutation with C cycles, it can be sorted in N - C moves.
It turns out that this is also necessary, i.e, we can’t do any better. The crux of the idea here is that performing any swap either decreases or increases the number of swaps by exactly 1. We start out with C cycles and the sorted array has N cycles; clearly if we can only increase by 1 each time, the minimum number of moves required is N-C.
For those interested, a formal proof of this can be found at this stackexchange answer.
Now let’s look at Alice’s case. The only way Alice can win is if she also takes exactly N-C moves to sort the permutation - of course, the earlier analysis tells us that this is only possible when she can sort each cycle of size s in s-1 moves.
First, note that each swap consumes 2 potential - hence, sorting a cycle needs its vertices to have at least 2(s-1) potential in total, otherwise that cycle cannot be sorted at all.
However, once a cycle has at least 2(s-1) potential in total, it turns out that it can always be sorted in s-1 moves. Here’s how:
For convenience, let the cycle be 1\to 2\to 3\to \dots s\to 1, with potentials V_1, V_2, \dots, V_s respectively.
If s = 1, the cycle is already sorted and nothing needs to be done.
Otherwise, pick a vertex i such that V_i is minimum. If there are multiple such i, pick one with the largest value of V_{i-1}. If there are still ties, pick any of them arbitrarily.
Now swap vertices i and i-1, which updates the cycle to become 1\to 2\to 3\to \dots \to i-1\to i+1\to i+2\to \dots s\to 1 (i.e, a cycle of size s-1) and continue the process till we are left with a single vertex.
This process clearly takes exactly s-1 moves, because at each step we set p_i = i for some index i. All that remains to be shown is that we never pick a vertex whose potential is 0.
Proof
We prove this by induction on the size of the cycle.
Note that the input guarantees that V_i \geq 1 for all i initially.
If s = 1 the result is trivial.
If s = 2, the cycle consists of two vertices, each with positive potential, so we can safely swap them.
Suppose that any cycle of size s such that every vertex in it has positive potential, and the total potential is at least 2s-2, can be sorted in s-1 moves.
Consider any cycle of size s+1 whose vertices have positive potential, and the total potential is P, where P\geq 2s.
Let i be the vertex picked by our greedy process, and consider what happens when we swap i with i-1.
-
Case 1: V_i = 1
Note that by the pigeonhole principle, there is at least one vertex j with V_j\geq 2 (otherwise the total potential would be s+1 < 2s, which contradicts our assumption).
So, if the minimum potential is 1, there definitely exists some vertex x with potential 1 such that V_{x-1} \geq 2 (just follow the cycle backwards). By our rule of breaking ties, only such a vertex will be chosen as V_i.
The total potential of the cycle formed by swapping i and i-1 is hence exactly P - 2 \geq 2s-2.
Further, we have V_{i-1} \mapsto V_{i-1} - 1 \geq 2-1 = 1, so the smaller cycle we created satisfies the inductive hypothesis and hence can be sorted. -
Case 2: V_i > 1.
In this case, every vertex has at least potential 2. So, even after swapping i and i-1, the other s-1 untouched vertices give a total potential of at least 2\cdot (s-1) to the remaining cycle.
Further, V_{i-1}\geq 2 so upon subtracting 1 from it, it remains positive.
By the inductive hypothesis, once again the smaller cycle can be sorted optimally and we are done.
IMPLEMENTATION DETAILS
Given a cycle, we would like to find the vertex with least potential, and among these the one whose inverse has the largest potential. Further, swapping two adjacent elements of the cycle affects the potential of exactly one remaining element, and updates the previous/next element in the cycle of exactly two remaining elements.
One way to maintain this information is to keep tuples of (V_x, V_{p^{-1}_x}, x), sorted in ascending order by first coordinate and descending order by second, in a structure which allows us to quickly add/remove elements and get the smallest element - for example, std::set in C++ or TreeSet in Java.
At each step, remove the first element of this set and add the operation to swap (x, p^{-1}_x), then remove the tuples corresponding to x, p_x, and p^{-1}_x from the set.
Update the potential of p^{-1}_x, update the next/previous links of p^{-1}_x and p_x respectively, and then insert them back into the set.
If you still find this confusing, please refer to the code linked below.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per test.
CODE:
Setter (C++)
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define INF 2000000000000000000
#define popcount(x) __builtin_popcountll(x)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define ld long double
const int M = 1000000007;
const int MM = 998244353;
template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
#ifdef LOCAL
#define debug(...) debug_out(#_VA_ARGS, __VA_ARGS_)
#else
#define debug(...) 2351
#endif
int runtimeTerror()
{
int n;
cin >> n;
vector<int> p(n+1),V(n+1),par(n+1);
for(int i=1;i<=n;++i)
{
cin >> p[i];
par[p[i]] = i;
}
for(int i=1;i<=n;++i)
{
cin >> V[i];
}
vector<pair<int,int>> alice,bob;
auto make = [&](vector<int> &cy,long long P)
{
int n = cy.size();
if(n <= 1)
return 1;
// bob moves
for(int i=1;i<cy.size();++i)
{
bob.push_back({cy[0],cy[i]});
}
if(P < 2 * n - 2)
return 0;
// alice moves
set<pair<pair<int,int>,int>> s;
for(auto j:cy)
{
s.insert({{V[j],-V[par[j]]},j});
}
while(!s.empty())
{
auto [x,u] = *s.begin();
s.erase(s.begin());
alice.push_back({u,par[u]});
s.erase({{V[p[u]],-V[u]},p[u]});
if(p[u] == par[u])
continue;
s.erase({{V[par[u]],-V[par[par[u]]]},par[u]});
p[par[u]] = p[u];
par[p[u]] = par[u];
--V[par[u]];
s.insert({{V[p[u]],-V[par[u]]},p[u]});
s.insert({{V[par[u]],-V[par[par[u]]]},par[u]});
}
return 1;
};
vector<bool> vis(n+1,0);
int ans = 1;
for(int i=1;i<=n;++i)
{
if(vis[i])
continue;
long long P = 0;
int cur = i;
vector<int> cy;
while(!vis[cur])
{
P += V[cur];
vis[cur] = true;
cy.push_back(cur);
cur = p[cur];
}
ans &= make(cy,P);
}
if(ans)
{
cout<<"Alice\n";
cout << alice.size() << "\n";
for(auto [j,k]:alice)
cout << j << " " << k << "\n";
}
else
{
cout<<"Bob\n";
cout << bob.size() << "\n";
for(auto [j,k]:bob)
cout << j << " " << k << "\n";
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T;
cin >> T;
while(T--)
runtimeTerror();
return 0;
}
Tester (Kotlin)
import java.io.BufferedInputStream
import java.util.*
const val BILLION = 1000000000
fun main(omkar: Array<String>) {
val jin = FastScanner()
var nSum = 0
val out = StringBuilder()
repeat(jin.nextInt(1000)) {
val n = jin.nextInt(100000)
nSum += n
if (nSum > 100000) {
throw IllegalArgumentException("constraint on sum n violated")
}
val p = IntArray(n + 1)
for (j in 1..n) {
p[j] = jin.nextInt(n, j == n)
}
if (p.toSet().size != n + 1) {
throw IllegalArgumentException("p is not a permutation")
}
val v = IntArray(n + 1)
for (j in 1..n) {
v[j] = jin.nextInt(BILLION, j == n)
}
var moves = solve(n, p.clone(), v)
if (moves != null) {
out.appendln("Alice")
} else {
moves = solve(n, p.clone(), IntArray(n + 1) { 2 })!!
out.appendln("Bob")
}
out.appendln(moves.size)
for ((j, k) in moves) {
out.appendln("$j $k")
}
}
print(out)
jin.assureInputDone()
}
fun solve(n: Int, p: IntArray, v: IntArray): List<Pair<Int, Int>>? {
val q = IntArray(n + 1)
for (j in 1..n) {
q[p[j]] = j
}
val treeSet = TreeSet<Int>(compareBy({ v[it] }, { it }))
fun addIf(j: Int) {
if (p[j] != j && (p[p[j]] == j || v[q[j]] >= 2)) {
treeSet.add(j)
}
}
for (j in 1..n) {
addIf(j)
}
val moves = mutableListOf<Pair<Int, Int>>()
while (treeSet.isNotEmpty()) {
val k = treeSet.first()
val j = q[k]
val l = p[k]
treeSet.remove(j)
treeSet.remove(k)
treeSet.remove(l)
p[k] = k
p[j] = l
q[k] = k
q[l] = j
v[k] = 0
v[j]--
moves.add(Pair(j, k))
addIf(j)
addIf(l)
}
if ((1..n).all { p[it] == it }) {
return moves
} else {
return null
}
}
class FastScanner {
private val BS = 1 shl 16
private val NC = 0.toChar()
private val buf = ByteArray(BS)
private var bId = 0
private var size = 0
private var c = NC
private var `in`: BufferedInputStream? = null
constructor() {
`in` = BufferedInputStream(System.`in`, BS)
}
private val char: Char
private get() {
while (bId == size) {
size = try {
`in`!!.read(buf)
} catch (e: Exception) {
return NC
}
if (size == -1) return NC
bId = 0
}
return buf[bId++].toChar()
}
fun assureInputDone() {
if (char != NC) {
throw IllegalArgumentException("excessive input")
}
}
fun nextInt(endsLine: Boolean): Int {
var neg = false
c = char
if (c !in '0'..'9' && c != '-' && c != ' ' && c != '\n') {
throw IllegalArgumentException("found character other than digit, negative sign, space, and newline")
}
if (c == '-') {
neg = true
c = char
}
var res = 0
while (c in '0'..'9') {
res = (res shl 3) + (res shl 1) + (c - '0')
c = char
}
if (endsLine) {
if (c != '\n') {
throw IllegalArgumentException("found character other than newline, character code = ${c.toInt()}")
}
} else {
if (c != ' ') {
throw IllegalArgumentException("found character other than space, character code = ${c.toInt()}")
}
}
return if (neg) -res else res
}
fun nextInt(from: Int, to: Int, endsLine: Boolean = true): Int {
val res = nextInt(endsLine)
if (res !in from..to) {
throw IllegalArgumentException("$res not in range $from..$to")
}
return res
}
fun nextInt(to: Int, endsLine: Boolean = true) = nextInt(1, to, endsLine)
}
Editorialist (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> p(n+1), inv(n+1), v(n+1), mark(n+1);
for (int i = 1; i <= n; ++i) {
cin >> p[i];
inv[p[i]] = i;
}
for (int i = 1; i <= n; ++i)
cin >> v[i];
auto pcopy = p, invcopy = inv;
if (n == 1) {
cout << "Alice\n0\n";
continue;
}
vector<array<int, 2>> ans;
auto solve = [&] (auto cycle) -> bool {
int N = size(cycle);
if (N == 1) return true;
ll sum = 0;
for (int x : cycle)
sum += v[x];
if (sum < 2*(N-1)) return false;
auto cmp = [] (auto a, auto b) {
if (a[0] != b[0])
return a[0] < b[0];
if (a[1] != b[1])
return a[1] > b[1];
return a[2] < b[2];
};
set<array<int, 3>, decltype(cmp)> active(cmp);
for (int x : cycle) {
active.insert({v[x], v[inv[x]], x});
}
while (active.size()) {
auto [v1, v2, x] = *begin(active);
active.erase(begin(active));
ans.push_back({x, inv[x]});
// Now inv[x] points to p[x] and v[inv[x]] decrements by 1
active.erase({v[p[x]], v[x], p[x]});
if (p[x] == inv[x]) continue;
active.erase({v[inv[x]], v[inv[inv[x]]], inv[x]});
p[inv[x]] = p[x];
inv[p[x]] = inv[x];
--v[inv[x]];
active.insert({v[p[x]], v[inv[x]], p[x]});
active.insert({v[inv[x]], v[inv[inv[x]]], inv[x]});
}
return true;
};
vector<vector<int>> cycles;
for (int i = 1; i <= n; ++i) {
if (mark[i]) continue;
vector<int> cycle;
int cur = i;
while (!mark[cur]) {
cycle.push_back(cur);
mark[cur] = 1;
cur = p[cur];
}
cycles.push_back(cycle);
}
bool alice = true;
for (auto cycle : cycles) {
alice &= solve(cycle);
}
if (alice) {
cout << "Alice\n" << size(ans) << '\n';
for (auto move : ans)
cout << move[0] << ' ' << move[1] << '\n';
}
else {
for (int i = 1; i <= n; ++i)
v[i] = n;
swap(p, pcopy);
swap(inv, invcopy);
ans.clear();
for (auto cycle : cycles) {
solve(cycle);
}
cout << "Bob\n" << size(ans) << '\n';
for (auto move : ans)
cout << move[0] << ' ' << move[1] << '\n';
}
}
}