PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N and K, construct a permutation P of \{1, 2, \ldots, N\} such that
\sum_{i=1}^N (M_i - m_i) = K
where M_i = \max(P_1, P_2, \ldots, P_i) and m_i = \min(P_1, P_2, \ldots, P_i).
EXPLANATION:
Let D_i = M_i - m_i denote the i-th difference.
Let’s look at some conditions that this array D should satisfy.
- For each 1 \leq i \lt N, D_i \leq D_{i+1} should hold.
- D_1 = 0 should hold, of course, since it’s the difference of a single element.
- D_N = N-1 should also hold, since the overall maximum is N and overall minimum is 1.
- This also tells us that D_i \leq N-1 should hold for every i.
- Finally, it can also be seen that D_i \geq i-1 must hold: since the elements are distinct, among the first i elements there will definitely be some two with a difference that’s \geq i-1.
Now, note that the minimum possible sum of D_i is \frac{N\cdot (N-1)}{2}, given by the array D = [0, 1, 2, \ldots, N-1].
The maximum possible sum of D is just (N-1)^2, given by D = [0, N-1, N-1, \ldots, N-1].
If K is not between these bounds, no solution exists.
On the other hand, as long as K is between these bounds, there always exists an array D satisfying the above conditions with sum K.
Our task is now to construct such an array D, then construct a permutation P that gives this array.
Let’s first try to find an array D whose sum is K.
We start off with D = [0, 1, 2, \ldots, N-1], which has minimum sum.
Now, for each i = N-1, N-2, \ldots, 1, keep increasing D_i as long as D_i \lt N-1 and the current sum is \lt K.
Eventually, we reach a state where the sum of D will equal K; and all five of the conditions stated above remain satisfied.
Now, we need to find a permutation P that attains this array D.
Note that the way we constructed D, it has a somewhat special form: it’ll look like
[0, 1, 2, \ldots, i, x, N-1, N-1, \ldots, N-1]
That is, some prefix of D will have D_i = i-1, some suffix will be N-1, and at most one element between then will be \gt i-1 but \lt N-1.
Here’s a rather simple way to construct a permutation P that attains this array D.
- Let x be the first index such that D_x \gt x-1.
- For i = 1, 2, 3, \ldots, x-1, set P_i = i.
- Set P_x = D_x + 1.
- Set P_{x+1} = N
- For everything after x+1, it doesn’t matter what they are since 1 and N already exist: just distribute all remaining elements to those indices in some order.
It’s fairly easy to verify that this P is what we want.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=998244353;
const ll MAX=500500;
void output(vector<ll> p,ll n){
}
void solve(){
ll n,k; cin>>n>>k;
vector<ll> p(n+5);
set<ll> track;
for(ll i=1;i<=n;i++){
p[i]=i-1;
track.insert(i);
k-=p[i];
}
if(k<=-1){
cout<<"-1\n";
return;
}
for(ll i=n;i>=2;i--){
ll now=min(k,n-i);
k-=now;
p[i]+=now;
}
if(k!=0){
cout<<"-1\n";
return;
}
vector<ll> ans(n+5);
ll nax=0;
auto op=[&](ll pos,ll val){
if(!track.count(val)){
val=*track.begin();
}
ans[pos]=val;
track.erase(val);
nax=max(nax,val);
};
for(ll i=1;i<=n;i++){
op(i,p[i]+1);
cout<<ans[i]<<" \n"[i==n];
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
#define IGNORE_CR
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;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
res += buffer[pos];
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
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);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1e6);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(1, 1e6);
in.readSpace();
sn += n;
long long k = in.readLong(0, n * 1LL * n);
in.readEoln();
long long mn = n * 1LL * (n - 1) / 2;
long long mx = (n - 1) * 1LL * (n - 1);
if (k < mn || mx < k) {
cout << -1 << '\n';
continue;
}
vector<int> ans(n);
iota(ans.begin(), ans.end(), 0);
for (int i = n - 1; i >= 1; i--) {
int t = (int) min(n - 1LL - i, k - mn);
ans[i] += t;
mn += t;
}
vector<int> used(n);
for (int i = 0; i < n; i++) {
used[ans[i]] = 1;
}
vector<int> a;
for (int i = 0; i < n; i++) {
if (!used[i]) {
a.emplace_back(i);
}
}
used = vector<int>(n);
for (int i = 0; i < n; i++) {
if (used[ans[i]]) {
ans[i] = a.back();
a.pop_back();
}
used[ans[i]] = 1;
}
for (int i = 0; i < n; i++) {
cout << ans[i] + 1 << " ";
}
cout << '\n';
}
cerr << in.pos << " " << in.buffer.size() << endl;
in.readEof();
assert(sn <= 1e6);
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
mnsum, mxsum = n*(n-1)//2, (n-1)*(n-1)
if k < mnsum or k > mxsum:
print(-1)
continue
a = list(range(n))
for i in reversed(range(n)):
add = min(n-1 - a[i], k - mnsum)
a[i] += add
mnsum += add
ans = [1]*n
mark = [0]*(n+1)
for i in range(1, n):
ans[i] = ans[i-1] + (a[i] - a[i-1])
mark[ans[i]] = 1
if ans[i] == n: break
for i in reversed(range(n)):
if ans[i] == n: break
while mark[-1] == 1: mark.pop()
ans[i] = len(mark) - 1
mark.pop()
print(*ans)