PERDIS - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: mexomerf
Tester: jay_1048576
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given a permutation P of \{1, \ldots, N\}.
Find the minimum number of adjacent swaps needed to ensure that P_i \neq i for all i.

EXPLANATION:

Call an index i bad if P_i = i. We want to end up with a permutation where no index is bad.

Notice that each swap operation can ‘fix’ at most two bad indices.
Specifically, if two bad indices are next to each other then swapping them will fix them both; otherwise only one bad index can be fixed with a swap.
Since our aim is to minimize the number of operations, we should try to fix two bad indices at a time, if possible.

Further, notice that whenever a swap is performed that includes a bad index, both indices will not be bad afterwards. In other words, we won’t ever ‘create’ new bad indices.

Why?

Suppose P_i = i, and we swap the values at indices (i, i+1).
Let P_{i+1} = x initially. We don’t know what x is, but it definitely isn’t i (since i is at index i).
Then, after the swap,

  • P_i = x, and x\neq i so index i is not bad.
  • P_{i+1} = i, so i+1 is also not bad.

This allows the problem to be solved with a simple greedy algorithm.
For each i = 1 ,2, 3, \ldots, N in order,

  • If i is not a bad index, do nothing.
  • Otherwise, swap the values at indices i and i+1.

At the end of this, the only index that can possibly be bad is index N; so if it is bad, use one more move to swap (N, N-1) and we’re done.
The idea of this is that we simply repeatedly take the first bad index, then fix it by swapping it with its neighbor.
It’s better to swap to the right because we know for sure that 1, 2, \ldots, i-1 aren’t bad; but (i+1) might be so swapping to the right gives us a chance to fix two indices at once.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Tester's code (C++) 
/*...................................................................*
 *............___..................___.....____...______......___....*
 *.../|....../...\........./|...../...\...|.............|..../...\...*
 *../.|...../.....\......./.|....|.....|..|.............|.../........*
 *....|....|.......|...../..|....|.....|..|............/...|.........*
 *....|....|.......|..../...|.....\___/...|___......../....|..___....*
 *....|....|.......|.../....|...../...\.......\....../.....|./...\...*
 *....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
 *....|.....\...../.........|....|.....|.......|.../........\...../..*
 *..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
 *...................................................................*
 */
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007

void solve(int tc)
{
    int n;
    cin >> n;
    int p[n];
    for(int i=0;i<n;i++)
        cin >> p[i];
    int c=0,ans=0;
    for(int i=0;i<n;i++)
    {
        if(p[i]==i+1)
            c++;
        else
        {
            ans += (c+1)/2;
            c=0;
        }
    }
    ans += (c+1)/2;
    cout << ans << '\n';
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc=1;
    cin >> tc;
    for(int ttc=1;ttc<=tc;ttc++)
        solve(ttc);
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    p = list(map(int, input().split()))
    ans, cur = 0, 0
    for i in range(n):
        if p[i] == i+1:
            cur += 1
            if cur == 2:
                ans += 1
                cur = 0
        else:
            if cur == 1:
                ans += 1
                cur = 0
    print(ans + cur)