PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: airths
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
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];
vector <int> adj[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 readString(int l,int r,char endd){
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){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int sumN = 0;
void solve()
{
int n = readIntLn(1, 100000);
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);
int T=readIntLn(1,1000);
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)
