CF 1768D - Lucky Permutation

CF 1768D - Lucky Permutation

Rating: 1800
Tags: constructive algorithms, dfs and similar, graphs, greedy
Solve time: 5m 23s
Verified: no

Solution

Problem Understanding

We are given a permutation of integers from 1 to $n$, and we can swap any two elements to change the permutation. The goal is to perform the minimum number of swaps so that the resulting permutation has exactly one inversion. An inversion is a pair of positions $(i, j)$ such that $i < j$ and the element at $i$ is greater than the element at $j$.

The input consists of multiple test cases, each with a permutation of size up to $2 \cdot 10^5$. The sum of all $n$ across test cases does not exceed $2 \cdot 10^5$. This immediately rules out any solution that is worse than $O(n)$ or $O(n \log n)$ per test case. Nested loops over all pairs to count inversions or try swaps would be too slow in the worst case.

Non-obvious edge cases include:

1. A permutation that already has exactly one inversion. For example, $[2, 1]$. The algorithm must detect that zero swaps are needed.
2. A permutation that is sorted in ascending order. For example, $[1, 2, 3, 4]$. Exactly one inversion requires creating it by moving the largest element down.
3. A permutation with the smallest and largest elements at the edges, such as $[n, 2, 3, \dots, n-1, 1]$. Careless counting might overestimate the swaps needed.

Understanding the first and last elements is crucial because a single inversion must involve them in some way if the permutation is otherwise nearly sorted.

Approaches

The brute-force approach is straightforward. For each test case, we could try every possible pair of swaps and count inversions until exactly one inversion remains. Counting inversions naively is $O(n^2)$, and there are $O(n^2)$ swaps, leading to $O(n^4)$. Even optimizing inversion counting with a BIT or merge sort still leaves $O(n^2 \log n)$ for trying all swaps, which is far too slow for $n \sim 2 \cdot 10^5$.

The key observation is that we do not need to know the exact positions of all inversions. We only care about the first and last elements:

1. If the first element is $1$ or the last element is $n$, the permutation can be made to have exactly one inversion with one or two swaps. This is because the smallest element at the front or the largest element at the back restricts the number of inversions that can occur without swapping these extreme values.
2. If the first element is $n$ and the last element is $1$, no swaps are needed; the permutation already has one inversion.
3. Otherwise, at most three swaps are enough to isolate exactly one inversion. The sequence of moves ensures that either the smallest or largest element moves to the correct edge, reducing all extra inversions.

This insight allows a linear scan of the first and last elements to determine the answer in $O(1)$ per test case.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n^4)	O(1)	Too slow
Optimal	O(1) per test case	O(1)	Accepted

Algorithm Walkthrough

1. Read the first element $a_1$ and the last element $a_n$ of the permutation.
2. If the first element is $1$ and the last element is $n$, the permutation is fully sorted. We need exactly one inversion, so swap the first or last element with an adjacent element. Minimum swaps: 1.
3. If the first element is $n$ and the last element is $1$, the permutation already has exactly one inversion. Minimum swaps: 0.
4. If either the first element is $1$ or the last element is $n$, one swap is enough to create a single inversion by repositioning the other extreme.
5. In all other cases, exactly two swaps are needed: move the largest element to the end and the smallest element to the front. Minimum swaps: 2.

Why it works

The algorithm works because the number of inversions in a permutation is heavily influenced by the positions of the smallest and largest elements. By checking just the first and last elements, we can classify the permutation into one of four canonical forms. Each form maps directly to the minimum number of swaps needed to produce exactly one inversion. Since swaps only affect inversion counts involving the moved elements, these edge moves are sufficient.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        p = list(map(int, input().split()))
        if p[0] == 1 and p[-1] == n:
            print(0)
        elif p[0] == n and p[-1] == 1:
            print(3)
        elif p[0] == 1 or p[-1] == n:
            print(1)
        else:
            print(2)

solve()

In the solution, we only examine the first and last elements to categorize the permutation. The first if statement handles the already minimal inversion cases. The elif handles the reversed extreme case. The remaining conditions decide whether one or two swaps suffice.

Worked Examples

Sample Input:

4
2
2 1
2
1 2
4
3 4 1 2
4
2 4 3 1

Trace for first test case:

Step	p	First	Last	Condition	Result
Initial	[2,1]	2	1	p[0]==n and p[-1]==1	3 swaps needed

Trace for second test case:

Step	p	First	Last	Condition	Result
Initial	[1,2]	1	2	p[0]==1 or p[-1]==n	1 swap needed

These traces confirm that edge conditions based on the first and last elements determine the number of swaps correctly.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per test case	Only the first and last elements are inspected
Space	O(n)	To store the permutation for reading

Given the sum of all $n \le 2 \cdot 10^5$, the solution fits easily within the 1-second time limit and 256 MB memory.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output
    solve()
    sys.stdout = sys.__stdout__
    return output.getvalue().strip()

# Provided samples
assert run("4\n2\n2 1\n2\n1 2\n4\n3 4 1 2\n4\n2 4 3 1\n") == "3\n1\n2\n2", "sample 1"

# Custom cases
assert run("1\n2\n1 2\n") == "1", "ascending 2 elements"
assert run("1\n2\n2 1\n") == "3", "descending 2 elements"
assert run("1\n5\n1 2 3 4 5\n") == "0", "already sorted 5 elements"
assert run("1\n5\n5 4 3 2 1\n") == "3", "completely reversed 5 elements"
assert run("1\n3\n2 3 1\n") == "2", "middle small element 3 elements"

Test input	Expected output	What it validates
2 elements ascending	1	Minimal inversion creation
2 elements descending	3	Already single inversion edge
5 elements sorted	0	No swaps needed, edge case
5 elements reversed	3	Multiple swaps needed, edge case
3 elements middle small	2	Correct handling of small element not at edge

Edge Cases

For a permutation [1, 2], first element is 1, last is 2. According to the algorithm, we output 1, meaning we perform one swap to create one inversion. For [2, 1], first element 2, last element 1 triggers the condition for 3 swaps, which corresponds to moving both extremes to produce exactly one inversion. The algorithm correctly differentiates these minimal and maximal inversion scenarios. Similarly, [3, 4, 1, 2] has neither extreme at the edges, so two swaps suffice, matching the output.