PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N and X, construct a permutation P of \{1, 2, \ldots, N\} such that:
- P_1 = X; and
- The array of differences D is a palindrome, where D_i = P_{i+1} - P_{i}
EXPLANATION:
Many constructions exist, here’s one.
First, we solve for even N. Let K = \frac{N}{2}.
Since N is even, we have two halves of the array; we can construct one and then essentially mirror it.
Without loss of generality, let X \leq K.
The first half of P will equal [1, 2, 3, \ldots, K] but shifted cyclically so that the first element is X — that is, [X, X+1, \ldots, K-1, K, 1, 2, 3, \ldots, X-1].
The second half will equal [K+1, K+2, \ldots, N] , shifted cyclically so that the last element is N-X+1.
tl;dr the permutation we create is
For example, if N = 10 and X = 3 we’d create
[3, 4, 5, 1, 2, 9, 10, 6, 7, 8]
It’s quite easy to see that this construction creates a palindromic difference array D:
- In the left half, all but one index has D_i = P_{i+1} - P_i = 1.
You can see that the same applies to the left half. - For the single index where this fails, their positions mirror each other in both halves, and the differences are (1-K) and (K+1-N), which are equal (recall that K = \frac{N}{2}).
- The difference of the ‘connecting part’, i.e D_K = P_{K+1} - P_K, doesn’t matter at all because D has odd length when N is even; its middle element can be anything at all and it’ll still be a palindrome.
When X \gt K do the exact same thing but with the larger elements in the left half.
For odd N, a rather similar construction works.
Let K = \left\lfloor \frac{N}{2} \right\rfloor.
Then, mirroring the smallest and largest K elements as done in the even case works; where you place \left\lceil \frac{N}{2} \right\rceil at position \left\lceil \frac{N}{2} \right\rceil as well to finish off.
For instance, if N = 11 and X = 3 the permutation constructed this way is
[3, 4, 5, 1, 2, 6, 10, 11, 7, 8, 9]
Of course, this construction does fail for one specific case: when X = \left\lceil \frac{N}{2} \right\rceil, since our construction requires us to place it in the middle, not at the beginning.
In fact, in such a case no solution exists at all!
Proof
As earlier, let K = \left\lfloor \frac{N}{2} \right\rfloor.
We’ll prove something a bit stronger: any permutation P for which D is a palindrome must have P_{K+1} = K+1, i.e, the ‘middle element’ is forced to be in the ‘middle position’.
First, note that the elements of P can be described by the values of D.
That is, for any i \lt j, we have
Now, consider some index i \leq K.
We know that:
- P_{K+1} = P_i + D_i + \ldots + D_K
Let x = D_i + \ldots + D_K, so P_{K+1} = P_i + x. - P_{N+1-i} = P_{K+1} + D_{K+1} + \ldots + D_{N-i}
Let y = D_{K+1} + \ldots + D_{N-i}, so P_{N+1-i} = P_{K+1} + y.
By the fact that D is a palindrome, we in fact have x = y since they’re both summing up the same length of differences from the center, just in different directions.
This means that P_i + P_{N+1-i} = P_i + (P_i + 2x) = 2\cdot (P_i + x) = 2\cdot (P_{K+1})
In other words, 2\cdot P_{K+1} = P_i + P_{N+1-i} for every i.
This is only possible if P_{K+1} = K+1; since P_{K+1} must be in the ‘middle’ of all the other pairs of elements.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n,x;
int p[N];
int main()
{
//freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&x);
int k=x>n/2?x-(n+1)/2:x;
vector<int> v[2];
for(int i=1;i<=n;i++) v[0].push_back(0), v[1].push_back(0);
for(int i=1;i<=n/2;i++) v[0][i]=i,v[1][i]=i+(n+1)/2;
if(n&1)
{
if(x==n/2+1) printf("-1\n");
else
{
p[n/2+1]=n/2+1;
for(int i=1,j=k;i<=n/2;i++,j++)
{
if(j>n/2) j=1;
p[i]=v[x>n/2][j];
}
for(int i=n/2+2,j=1-(k-1);i<=n;i++,j++)
{
if(j<1) j+=n/2;
if(j>n/2) j=1;
p[i]=v[x<=n/2][j];
}
for(int i=1;i<=n;i++) printf("%d%c",p[i],i==n?'\n':' ');
}
}
else
{
for(int i=1,j=k;i<=n/2;i++,j++)
{
if(j>n/2) j=1;
p[i]=v[x>n/2][j];
}
for(int i=n/2+1,j=1-(k-1);i<=n;i++,j++)
{
if(j<1) j+=n/2;
if(j>n/2) j=1;
p[i]=v[x<=n/2][j];
}
for(int i=1;i<=n;i++) printf("%d%c",p[i],i==n?'\n':' ');
}
}
//fclose(stdin);
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int T; cin >> T;
while(T-- > 0) {
int N; cin >> N;
vector<int> A(N);
int X; cin >> X;
if(X == N + 1 - X) {
cout << -1 << '\n'; continue;
}
int L = 1, R = N - 2;
A.front() = X, A.back() = N + 1 - X;
X = min(X, N + 1 - X);
int cnt = 1;
while(L <= R) {
if(cnt == X) ++cnt;
A[L] = cnt;
A[R] = N + 1 - cnt;
++L, --R, ++cnt;
}
for(int i = 0 ; i < N ; ++i)
cout << A[i] << " \n"[i == N - 1];
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, x = map(int, input().split())
if n%2 == 1 and x == (n+1)//2:
print(-1)
continue
ans = [0]*n
for i in range(n//2):
ans[i] = x
ans[-1-i] = n+1-ans[i]
if x == n//2: x = 1
elif x == n: x = (n+1)//2 + 1
else: x += 1
if n%2 == 1: ans[n//2] = (n+1)//2
print(*ans)