Minimum and maximum differences

★★★★★

2.8

32 votes

Basic Programming, , Basics of Implementation, Greedy Algorithms

Details

Submissions

Discussion

Editorial

Problem

You are given a number $n$ . Your task is to determine two arrays of permutation of size $n$ so that $a_i \neq i$ for each $1 \le i \le n$ and the sum of $| a_i - i |$ for each $1 \le i \le n$ is minimum and maximum possible.

Example

If $n=2$ , then for the minimum difference is $2$ and the corresponding array permutation is $\{2,1\}$ , $|2-1|+|1-2|=2$ and the maximum difference is also $2$ and the corresponding array permutation is $\{2,1\}$ , $|2-1|+|1-2|=2$ .

Input format

The first line contains an integer $n \text{ }(1 \le n\le 4\times10^4)$ .

Output format

In the first line, print one integer for the minimum difference.
In the second line, print permutation $\{ a_1,a_2, \dots ,a_n\}$ corresponding to the minimum difference.
In the third line, print one integer for the maximum difference.
In the fourth line, print permutation $\{ b_1,b_2, \dots ,b_n\}$ corresponding to the maximum difference

If there is no permutation for minimum, then print $-1$ instead of the first and second lines.
If there is no permutation for maximum, then print $-1$ instead of the third and fourth lines.

Sample Input

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

given $n=3$ so if we take $\{3,1,2\}$ as our permuatation for minimum we will get $|3-1| + |1-2| + |2-3|= 2+1+1 =4$ as sum of absolute diffrence with index. you can't get absolute difference less than this without violatiiong condintion $a_i \neq i$

for maximum differance we can use $\{2,3,1\}$ as permutation for maximum. we will get $|2-1| + |3-2| +|1-3| = 1+1+2=4$ as sum of absolute diffrence with index. you can't get absolute difference more than this without violatiiong condintion $a_i \neq i$

In this case ( $n=3$ ) minimum and maximum differance is same

Contributers:

Harshad Vaghasiya

Arpa PoorAkhavan