PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Danish
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
1318
PREREQUISITES:
None
PROBLEM:
For a sequence of N elements A_1, A_2, A_3, \ldots, A_N, Chef defines a function F(i) (\forall 1 \leq i \leq N) as the median of the first i elements of the sequence.
Chef wants to get a Permutation P of length N such that P_i = F(i) \forall 1 \leq i \leq N. Can you help Chef in achieving this?
The \textbf{Median} of an array is the middle element in its sorted order. If N is even, choose the element at \frac{N}{2} position in the sorted order. If N is odd, choose the middle element.
A \textbf{Permutation} of length N is an array of N integers P = [P_1, P_2, \ldots, P_N] such that every integer from 1 to N (inclusive) appears in it exactly once. For example, [2,5,4,1,3] is a permutation of length 5.
EXPLANATION:
Let’s rephrase the problem slightly: find a permutation such that any element is the median of the prefix leading up to that element.
Let’s construct the elements from back to front:
- The last element P_N must be \lceil \frac{N}{2} \rceil (since it is the median of values from 1 to N).
- Now we know the values that the first N - 1 elements should have (1 to P_N - 1 and P_N + 1 to N), the second-to-last element P_{N - 1} must be the median of these values
- We then know the values that the first N - 2 should have, we then know the value of P_{N - 2}
and so on. After constructing from back to front, we look at the element from front to back and we see that its structure is P = [N, 1, N - 1, 2, N - 2, 3, \dots, \lceil \frac{N}{2} \rceil], and we can easily prove that this construction satisfy what we want.
TIME COMPLEXITY:
Time complexity is O(N) for each test case.
SOLUTION:
Setter's Solution
// #include <format>
#include <climits>
#include <iostream>
#include <fstream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
using namespace std;
FILE *fp;
ofstream outfile;
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;
}
assert(l<=x && x<=r);
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,' ');
}
const int maxn = 1e5, sumn = 2e5, maxt = 700;
int main()
{
int t = readIntLn(1, maxt);
int tot = 0;
while(t--){
int n = readIntLn(1, maxn); tot += n;
int a = n, b = 1;
for(int i = 0; i < n; i++)
{
if(i % 2 == 0)cout << a-- << " \n"[i == n - 1];
else cout << b++ << " \n"[i == n - 1];
}
}
assert(tot <= sumn);
assert(getchar()==-1);
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n;
void solve(){
cin >> n;
int l=1,r=n;
for(int i=1; i<=n ;i++){
if(i%2==1) cout << (r--) << ' ';
else cout << (l++) <<' ';
}
cout << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;while(t--) solve();
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
for (int r = n, l = 1; r >= l; r--, l++) {
cout << r << " ";
if (l != r) {
cout << l << " ";
}
}
cout << '\n';
}
}