PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Prefix sums
PROBLEM:
Given N, construct any permutation of \{1, 2, \ldots, N\} such that no subarray has a sum that’s a multiple of (N+1).
EXPLANATION:
First, note that no matter what, the entire permutation itself, with sum 1+2+\ldots + N will always be a subarray.
This sum equals \frac{N\cdot (N+1)}{2}. In particular, when N is even, this number is a multiple of N+1.
So, if N is even, no solution can exist.
Let’s now look at odd N.
When dealing with subarray sums, it’s useful to look at them in terms of prefix sums.
Let pr_i = P_1 + P_2 + \ldots + P_i denote the prefix sum array of P, with pr_0 = 0.
The sum of the subarray [L, R] of P is then simply pr_R - pr_{L-1}.
We don’t want any subarray sum to be a multiple of (N+1), meaning none of these differences should be zero modulo (N+1).
That’s equivalent to saying that all the pr_i values must be distinct when taken modulo (N+1).
There are (N+1) values of pr_i, so for them all to be distinct modulo (N+1), they must be some rearrangement of \{0, 1, 2, \ldots, N\}.
Note that pr_0 = 0 is fixed, as is pr_N = \frac{N\cdot (N+1)}{2}, the latter of which is \frac N 2 \pmod {N+1}.
There are now likely a few different constructions, here’s a simple one that works:
- Set the odd prefixes to the values 1, 2, 3, 4, \ldots
- Set the even prefixes to the values N, N-1, N-2, \ldots
That is, the prefix sum array will look like [0, 1, N, 2, N-1, 3, N-2, \ldots, \frac N 2] (when taken modulo (N+1)).
From this, we obtain the permutation P as P_i = pr_i - pr_{i-1}, which can be seen to be
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
if (n % 2 == 0){
cout << -1 << "\n";
return;
}
int p1 = n;
int p2 = 2;
for (int i = 1; i <= n; i++){
if (i & 1){
cout << (p1) << " \n"[i == n];
p1 -= 2;
} else {
cout << (p2) << " \n"[i == n];
p2 += 2;
}
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...)
#endif
#ifndef LOCAL
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
#else
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
string X; cin >> X;
return X;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res; cin >> res;
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res; cin >> res;
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
}
void readEoln() {
}
void readEof() {
}
};
#endif
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
input_checker inp;
int T = inp.readInt(1, (int)2e2), NN = 0; inp.readEoln();
while(T-- > 0) {
int N = inp.readInt(1, (int)1e3); inp.readEoln();
if(N % 2 == 0) {
cout << -1 << '\n'; continue;
}
vector<int> A(N);
for(int i = 0 ; i < N ; i += 2) A[i] = N - i;
for(int i = 1 ; i < N ; i += 2) A[i] = i + 1;
for(int i = 0 ; i < N ; ++i)
cout << A[i] << " \n"[i == N - 1];
}
inp.readEof();
return 0;
}
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
if (n%2 == 0) {
cout << -1 << '\n';
continue;
}
vector<int> pref(n+1);
pref[n] = (n+1)/2;
int L = pref[n] - 1, R = pref[n] + 1;
for (int i = 1; i < n; ++i) {
if (i%2 == 1) {
pref[n - i] = L--;
}
else {
pref[n - i] = R++;
}
}
for (int i = 1; i <= n; ++i) {
int x = (pref[i] - pref[i-1]) % (n+1);
if (x <= 0) x += n+1;
cout << x << ' ';
}
cout << '\n';
}
}