Hello Codeforces community!I would like to share an intuitive approach to solve the problem where we need to construct a permutation of length \[3n\] such that the sum of medians of \[n\] contiguous blocks (each of size 3) is maximized.↵
↵
Method ExplanationTo maximize the sum of the medians, we want the median of each triplet to be as large as possible.Let's think greedily. A median of 3 elements only requires one element smaller than it and one element larger than it. Therefore, to save the largest possible numbers to become medians, we should sacrifice the smallest \[n\] numbers (from \[1\] to \[n\]) to be the "left elements" (the smallest element in each triplet).↵
↵
For the remaining \[2n\] larger numbers (from \(n+1\) to \[3n\]), we can pair them up sequentially. For each block \[i\] (from \[1\] to \[n\]):Left element: \[i\]Median element: \(n + 2i — 1\)Right element: \(n + 2i\)When sorted, the triplet \((i, n + 2i — 1, n + 2i)\) will always have \(n + 2i — 1\) as its median. This perfect construction utilizes the largest numbers effectively.↵
↵
And here is the typical code for this problem↵
↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
void solve(){↵
↵
ll n;↵
↵
cin >> n;↵
↵
vector<ll>permutation;↵
↵
permutation.reserve(3 * n);↵
↵
for(int i = 1; i <= n; i++){↵
↵
ll left = i;↵
↵
ll median = n + 2 * i - 1;↵
↵
ll right = n + 2 * i;↵
↵
permutation.push_back(left);↵
permutation.push_back(median);↵
permutation.push_back(right);↵
}↵
for(int i = 0; i < 3 * n; i++){↵
cout << permutation[i] << (i == 3 * n - 1 ? "" : " ");↵
}↵
cout << "\n";↵
}↵
↵
signed main() {↵
↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
ll t;↵
cin >> t;↵
↵
while(t--) solve();↵
return 0;↵
}↵
↵
Method ExplanationTo maximize the sum of the medians, we want the median of each triplet to be as large as possible.Let's think greedily. A median of 3 elements only requires one element smaller than it and one element larger than it. Therefore, to save the largest possible numbers to become medians, we should sacrifice the smallest \[n\] numbers (from \[1\] to \[n\]) to be the "left elements" (the smallest element in each triplet).↵
↵
For the remaining \[2n\] larger numbers (from \(n+1\) to \[3n\]), we can pair them up sequentially. For each block \[i\] (from \[1\] to \[n\]):Left element: \[i\]Median element: \(n + 2i — 1\)Right element: \(n + 2i\)When sorted, the triplet \((i, n + 2i — 1, n + 2i)\) will always have \(n + 2i — 1\) as its median. This perfect construction utilizes the largest numbers effectively.↵
↵
And here is the typical code for this problem↵
↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
void solve(){↵
↵
ll n;↵
↵
cin >> n;↵
↵
vector<ll>permutation;↵
↵
permutation.reserve(3 * n);↵
↵
for(int i = 1; i <= n; i++){↵
↵
ll left = i;↵
↵
ll median = n + 2 * i - 1;↵
↵
ll right = n + 2 * i;↵
↵
permutation.push_back(left);↵
permutation.push_back(median);↵
permutation.push_back(right);↵
}↵
for(int i = 0; i < 3 * n; i++){↵
cout << permutation[i] << (i == 3 * n - 1 ? "" : " ");↵
}↵
cout << "\n";↵
}↵
↵
signed main() {↵
↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
ll t;↵
cin >> t;↵
↵
while(t--) solve();↵
return 0;↵
}↵
