# SPLITPERM - Editorial

Author: notsoloud
Tester: airths
Editorialist: iceknight1093

TBD

None

# PROBLEM:

The goodness of a permutation P is the largest integer k such that P can be partitioned into k subarrays, each of which has the same sum.
Given N, find any permutation of length N with maximum goodness.

# EXPLANATION:

Consider some permutation P, that’s partitioned into k subarrays all with the same sum S.
The sum of all these subarrays will then equal the sum of all the elements of P, which is
1 + 2 + 3 + \ldots + N = \frac{N\cdot (N+1)}{2}
This means we’ll have k\cdot S = \frac{N\cdot (N+1)}{2}.

Our objective is to maximize k, which in turn means S should be as small as possible.

Clearly, having S \lt N is impossible: the element N will appear in some subarray, and that subarray will have a sum that’s \geq N.

The next best option is to try S = N.
Note that this fixes k = \frac{N+1}{2}.
In particular, if N is even, k won’t be an integer - and so choosing S = N is impossible.
When N is odd however, it’s always possible.
We want to create \frac{N+1}{2} subarrays each of which sum to N.
To do that,

• Pair up 1 and N-1.
• Pair up 2 and N-2.
\vdots
• Pair up \frac{N-1}{2} and \frac{N+1}{2}.
• Keep N alone.

Join all these pairs to obtain a permutation of length N with goodness \frac{N+1}{2}, which is the maximum possible.

For example, for N = 7, the permutation we obtain is [1, 6, 2, 5, 3, 4, 7].

That leaves the case when N is even.
We know S \leq N is impossible, so our next option is to look at S = N+1.
This gives us k = \frac{N}{2}, and now it’s easy to see that a similar construction to the odd case works: just that we pair numbers to form a sum of N+1 rather than N.
That is,

• Pair up 1 and N.
• Pair up 2 and N-1.
\vdots
• Pair up \frac{N}{2} and \frac{N}{2} + 1

For example, for N = 8, we obtain [1, 8, 2, 7, 3, 6, 4, 5].

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

Author's code (C++)
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <math.h>
#include <ctime>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
#define int long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;

const int N=500023;
bool vis[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}
int sumN = 0;
void solve()
{
sumN += n;
if(n % 2 == 0){
for(int i = 1; i <=n/2; i++){
cout << i << " " << n-i+1 << " ";
}
}else{
for(int i = 1; i <=n/2; i++){
cout << i << " " << n-i << " ";
}
cout << n;
}
cout << endl;
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
while(T--){
solve();
}
assert(getchar()==-1);
cerr << sumN << endl;
assert(sumN <= 2000000);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}


Tester's code (C++)
/*
*
* 	^v^
*
*/
#include <iostream>
#include <numeric>
#include <set>
#include <cctype>
#include <iomanip>
#include <chrono>
#include <queue>
#include <string>
#include <vector>
#include <functional>
#include <tuple>
#include <map>
#include <bitset>
#include <algorithm>
#include <array>
#include <random>

using namespace std;

using ll = long long int;
using ld = long double;

#define iamtefu ios_base::sync_with_stdio(false); cin.tie(0);

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

void scn(){
// not necessarily distinct
// right down ytdm

int n; cin>>n;
vector <int> a(n);
array<int,2> o={n, 1};
for (int i=0; i<n; i++){
a[i] = o[i%2];
if (i&1){
o[i&1]++;
} else {
o[i&1]--;
}
}
for (int i=0; i<n; i++){
cout<<a[i]<<" \n"[i==n-1];
}
}

int main(){
iamtefu;
#if defined(airths)
auto t1=chrono::high_resolution_clock::now();
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int _; for(cin>>_; _--;)
{
scn();
}
#if defined(airths)
auto t2=chrono::high_resolution_clock::now();
ld ti=chrono::duration_cast<chrono::nanoseconds>(t2-t1).count();
ti*=1e-6;
cerr<<"Time: "<<setprecision(12)<<ti;
cerr<<"ms\n";
#endif
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
for i in range(1, n//2+1): print(i, n+1-i-n%2, end = ' ')
if n%2 == 1: print(n)


for a beginner , how he has to get an initiative to solve this kind of problems .

Any kind of suggestions are welcomed .

Solve more constructive or ad-hoc based problems!

1 Like

Hi! I just tried to run the python code in practice mode for this question ‘SPLITPERM’ and it has a small printing issue.
It prints the correct output but if the input is even it does not go to the next line because of the --end=’ '-- part. But solution still gets accepted.

for _ in range(int(input())):
n = int(input())
for i in range(1, n//2+1): print(i, n+1-i-n%2, end = ' ')
if n%2 == 1: print(n)


Most modern online judges treat all whitespace the same - it doesn’t matter whether you print a space or a newline (or 10 spaces and a newline).

I misunderstood the question and started solving a different version:

The goodness of a permutation P is defined as the number of ways P can be partitioned into one or more sub-arrays, such that all sub-arrays have the same sum.
Given N, find any permutation of length N with maximum goodness.

I checked every permutation and tried identifying the pattern for all N \isin [1, 10]. After around 20 minutes, I noticed a significant rise in the number of accepted submissions and decided to read the question again.

Maybe I shouldn’t assume the third question is difficult.