MAXDISTPERM - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh07
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given N, find two permutations A and B of length N such that \min_{i=1}^N |A_i - B_i| is maximized.

EXPLANATION:

The only thing that matters is the difference between A_i and B_i for each index i; that is, which elements are paired together.
So, for convenience, let’s set A = [1, 2, \ldots, N], and then decide B since that fixes the pairing.

Now, note that the minimum difference cannot be more than about \frac{N}{2}. Specifically,

  • If N is even, the element \frac{N}{2} can attain a difference of at most \frac{N}{2} (which happens only when it’s paired with N).
  • If N is odd, the element \frac{N+1}{2} can attain a difference of at most \frac{N-1}{2} (which happens when it’s paired with either 1 or N).

More succinctly, it can be seen that the minimum possible difference is at most \left\lfloor \frac{N}{2} \right\rfloor.
With this in mind, it’s not too hard to find a B such that |B_i - i| \geq \left\lfloor \frac{N}{2} \right\rfloor - simply rotate A.
That is, we obtain

B = \left[\left\lfloor \frac{N}{2} \right\rfloor + 1, \left\lfloor \frac{N}{2} \right\rfloor + 2, \ldots, N, 1, 2, 3, \ldots, \left\lfloor \frac{N}{2} \right\rfloor\right]

For example, if N = 6 we obtain B = [4, 5, 6, 1, 2, 3], and if N = 9 we obtain
B = [5, 6, 7, 8, 9, 1, 2, 3, 4].

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    print(*list(range(1, n+1)))
    print(*list(range(n//2 + 1, n+1)), *list(range(1, n//2+1)))
2

I think multiple answers are not being checked.
It is only accepting the answer in form - { (n/2)+1, (n/2)+2, …, n, 1, 2, …, n/2}

Because when I check it against my solution with above solution, the maximum distance is same but still giving wrong answer in codechef.

Here’s my testing code :
“arr - comparing array
brr - editorial’s solution array
crr - my solution during contest”

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

#define all(x) x.begin(), x.end()
#define el cout << "\n";
#define vi vector <int>

int main()
{
    for (int n = 1; n <= 100; n++)
    {
        vi arr, brr, crr;
        for (int i = 0; i < n; i++)
        {
            arr.push_back(i + 1);
            crr.push_back(i + 1);
        }
        for (int i = n / 2; i < n; i++)
        {
            brr.push_back(i + 1);
        }
        for (int i = 1; i <= n / 2; i++)
        {
            brr.push_back(i);
        }
        reverse(all(crr));

        int tmp1 = 0, tmp2 = 0;
        for (int i = 0; i < n; i++)
        {
            tmp1 += abs(arr[i] - brr[i]);
            tmp2 += abs(arr[i] - crr[i]);
        }

        if (tmp1 != tmp2)
        {
            cout << tmp1 << " " << tmp2 << endl;
        }
    }
}
3

Note that distance is defined as min(|A[i] - B[i]|) and not sum(|A[i] - B[i]|)

You have used sum to calculate the values

1 Like
4

Thanks for clarification !
I misunderstood the problem.