MINPERM - Editorial

PROBLEM LINK:

Practice

Contest

Author: Hanlin Ren

Tester: Jingbo Shang

Editorialist: Hanlin Ren

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

A permutation p is said to be good if p_i\ne i for any i\in[1,N]. Find the lexicographically smallest good permutation of length N.

QUICK EXPLANATION:

The answer is

\begin{cases}2,1,4,3,\dots,N,N-1&N\text{ is even}\\2,1,4,3,\dots,N-3,N-4,N-1,N,N-2&N\text{ is odd}\end{cases}.

EXPLANATION:

Guessing the answer

Let’s print the answer for small n's. (Actually, when the input consists of only one integer, we often print answers for small n's and maybe we can find the pattern.)

$n$ the answer
2 2,1
3 2,3,1
4 2,1,4,3
5 2,1,4,5,3
6 2,1,4,3,6,5
7 2,1,4,3,6,7,5

Can you find it?

For n even, we split the identity permutation (1,2,\dots,n) into blocks of length 2, and swap every block:

1 2 3 4 5 6
1 2|3 4|5 6
2 1|4 3|6 5
2 1 4 3 6 5

For n odd, things are slightly more complicated: the last block has length 3, and when “swapping” this block, we change N-2,N-1,N into N-1,N,N-2.

1 2 3 4 5 6 7
1 2|3 4|5 6 7
2 1|4 3|6 7 5
2 1 4 3 6 7 5

Why?

First notice that when N\ge 2, there is always a solution.

Also, to make things simpler, we assume that N\ge 4. When N < 4, we can use brute force to compute the answer.

When lexicographical order comes into a problem, it’s usually useful to think “position by position”. Let p be the permutation we want.

First, can p[1]=1? Obviously the answer is no.

Then, can p[1]=2? Yes! It’s easy to see that, there exists a good permutation that starts with 2(e.g. (2,3,4,\dots,N,1)), so the lexicographically smallest one must start with 2.

Next we need to determine p[2]. Can p[2]=1? The answer is yes. Since N-2\ge 2, you know that you have a good permutation of 1\sim (N-2), say, q. Let’s add 2 to every element of q so it becomes a permutation of 3\sim N, and append it after (2,1). That gives a permutation (2,1,q[1]+2,q[2]+2,\dots,q[N-2]+2) and it’s obviously good. So p[2]=1. To make your permutation the lexicographically smallest, you only need to make q the smallest. That becomes a subproblem of size N-2. This is why the answer always begin with something like “2\ 1\ 4\ 3\dots”.

ALTERNATIVE SOLUTION:

There is a simple brute force solution that actually runs in O(N^2) time:

p = [array of length n, uninitialized]
u = [array of 0's] #u[x] means if x appears in p[1..(i-1)]
dfs(i)
    for j = 1 to n
        if (not u[j]) and (j != i)
            p[i] = j
            u[j] = 1
            dfs(i+1)
            u[j] = 0

This brute force simply searches all positions one by one, and prune the search tree immediately while something isn’t right. Why is it O(N^2)? This algorithm actually does the following thing:

  1. Try p[1]=1. It’s not valid. Then try p[1]=2.
  2. Try p[2]=1. It’s OK.
  3. Try p[3]=1,2,3, all invalid. Then p[3]=4.
  4. Try p[4]=1,2, invalid. Then p[4]=3.

In step i, we enumerate O(i) invalid numbers. When n is even, no backtracking happens; when n is odd, the only backtrack happens when i=n-1. Therefore the complexity is O(1+2+\dots+n)=O(n^2).

How could we improve this to O(n)? We simply maintain the smallest number j that u[j]=0, and the i-th step costs O(i) enumerations, rather than O(i).

p = [array of length n, uninitialized]
u = [array of 0's] #u[x] means if x appears in p[1..(i-1)]
J = 1//smallest J that u[J] = 0
dfs(i)
    for j = J to n
        if (not u[j]) and (j != i)
            p[i] = j
            u[j] = 1
            //maintain new J
            old_j = J
            while u[J] == 1 and J <= n do
            	J = J + 1
            dfs(i+1)
            u[j] = 0
            J = old_j//restore J

However, I think this solution is more complex than the pattern-finding one. What do you think?

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.
Author’s solution for “Alternative Solution” can be found here.

2 Likes

Actually, after looking at the lenient sample input output, no second thoughts were needed to be given :stuck_out_tongue: . And actually thats good, because cakewalk problem is majorly aimed at people who are new to world of programming, so it actually impresses on them to read problem statement and sample I/O with an eye of detail, catching the patters (if any).

Also, I loved the explanation as well. Its good to see a genuine explanation even for easier problems. :slight_smile:

2 Likes

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
int t;
cin>>t;
while(t–)
{
int N;
int a[100000]={0};
cin>>N;
int i;
if(N%2==0)
{
for(i=1;i<N+1;i++)
{
if(i%2==0)
a[i-1]=i-1;
else
a[i-1]=i+1;
}
}
else
{
for(i=1;i<N-1;i++)
{
if(i%2==0)
a[i-1]=i-1;
else
a[i-1]=i+1;
}
a[N-1-1]=N;
a[N-1]=N-2;
}
for(i=0;a[i]!=0;i++)
{
cout<<a[i];
}
}
cout<<endl;
return 0;
}

Author’s solution and alternative solution looks to be same.