PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Testers: apoorv_me, tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N, L, and R, find any permutation of length N that minimizes the number of prefix sums lying in [L, R].
EXPLANATION:
First, let’s find a lower bound on the answer.
Observe that the minimum number of integers needed to ‘cover’ the segment [L, R] can be obtained greedily, by choosing N, N-1, N-2, \ldots till we reach a length greater than R-L+1.
Let K be the last element chosen in this order, i.e, K is the largest integer such that
N + (N-1) + (N-2) + \ldots + K \gt R-L+1.
N-K is a clear lower bound on the answer.
Now, we find a construction that attains this bound.
One relatively simple greedy construction is as follows:
- First, place the numbers 1, 2, 3, \ldots in order, till their sum exceeds L-1 for the first time.
Let x be the last number placed this way.
The sum can exceed L-1 by at most x, so by deleting one number \leq x, we can make the sum exactly equal L-1.
Let y be the deleted number. - Now that the current sum is L-1, place the numbers N, N-1, \ldots, x+1 in order, finally followed by y (which was deleted earlier).
For instance, if N = 7 and L = 5, R = 12 we have:
- x = 3, since 1+2+3 = 6 \gt L-1 = 4.
y = 6 - 4 = 2 is the deleted number. - Place [1, 3], then [7, 6, 5, 4], and then finally 2, to obtain [1, 3, 7, 6, 5, 4, 2].
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nline "\n"
#define all(x) x.begin(),x.end()
const ll MAX=200200;
const ll till=20;
const ll MOD=998244353;
ll get_freq(vector<ll> p,ll l,ll r){
ll sum=0,found=0;
for(auto it:p){
sum+=it;
cout<<it<<" ";
if(l<=sum and sum<=r){
found++;
}
}
cout<<nline;
return found;
}
ll getv(ll n,ll l,ll r){
ll left_end=l-1,cur=n,till=(n*(n+1))/2;
if(r==till){
vector<ll> ans(n);
iota(all(ans),1);
return get_freq(ans,l,r);
}
vector<ll> left_part,mid_part,used(n+5,0);
while(left_end<r){
mid_part.push_back(cur);
left_end+=cur,used[cur]=1,cur--;
}
ll target=l-1,sum=0;
while(cur>=1 and sum!=target){
ll now=min(target-sum,cur);
left_part.push_back(now);
sum+=now,used[now]=1,cur--;
}
vector<ll> ans=left_part;
ans.insert(ans.end(),all(mid_part));
for(ll i=1;i<=n;i++){
if(used[i]==0){
ans.push_back(i);
}
}
return get_freq(ans,l,r);
}
void solve(){
ll n,l,r; cin>>n>>l>>r;
ll till=(n*(n+1))/2;
ll prediction=0,len=r-l+1;
ll cur=n;
while(len>=1 and len>=cur){
prediction++;
len-=cur;
cur--;
}
ll check=getv(n,l,r);
if(r!=till){
assert(prediction==check);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
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 (apoorv_me, C++)
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...)
#endif
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
auto __solve_testcase = [&](int test) {
int N; cin >> N;
int64_t L, R, S; cin >> L >> R;
int64_t sum = L - 1;
deque<int> dq;
while(sum < R) {
sum += N;
dq.push_back(N--);
}
--L;
for(int i = N ; i >= 1 ; --i) {
if(L >= i) {
dq.push_front(i); L -= i;
} else {
dq.push_back(i);
}
}
for(auto &i: dq)
cout << i << " ";
cout << '\n';
};
int NumTest = 1;
cin >> NumTest;
for(int testno = 1; testno <= NumTest ; ++testno) {
__solve_testcase(testno);
}
return 0;
}
Tester's code (tabr, C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
void solve(int n, long long l, long long r) {
deque<int> ans;
long long s = 0;
int t = n;
while (t > 0 && s < r - l + 2) {
s += t;
ans.emplace_front(t);
t--;
}
s = l - 1;
for (int i = t; i > 0; i--) {
if (s >= i) {
s -= i;
ans.emplace_front(i);
} else {
ans.emplace_back(i);
}
}
for (int i : ans) {
cout << i << " ";
}
cout << "\n";
}
////////////////////////////////////////
#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, 1e5);
in.readEoln();
cerr << tt << endl;
int sn = 0;
while (tt--) {
int n = in.readInt(1, 2e5);
in.readSpace();
long long m = n * 1LL * (n + 1) / 2;
long long l = in.readLong(0, m);
in.readSpace();
long long r = in.readLong(0, m);
in.readEoln();
if (l > r)
cerr << l << " " << r << endl;
sn += n;
solve(n, l, r);
}
cerr << sn << endl;
assert(sn <= 2e5);
in.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, l, r = map(int, input().split())
sm, i = 0, 1
while sm < l:
sm += i
i += 1
ans = list(range(1, i)) + list(reversed(range(i, n+1))) + [sm - (l-1)]
ans.remove(sm - (l-1))
print(*ans)
