PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: fuehrercheem
Preparation: raysh07
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
For an array A, an index i\gt 1 is called cursed if A_1+A_2+A_3 + \ldots+A_{i-1}\geq A_i.
You’re given an array A, which you can rearrange as you like.
What’s the minimum number of cursed indices attainable?
EXPLANATION:
Instead of minimizing the number of cursed indices, let’s attempt to maximize the number of non-cursed indices.
An index is not cursed if A_i \gt A_1 + A_2 + \ldots + A_{i-1}.
Observe that it’s always possible to rearrange an array such that its non-cursed indices form some prefix of the array.
How?
Consider an array A such that x is a non-cursed index but (x-1) is cursed.
Consider what happens when we swap the elements at these indices.
- The cursedness of indices \lt x-1 isn’t affected at all.
- x was initially non-cursed, so A_x \gt A_1 + A_2 + \ldots + A_{x-1} was true.
After the swap, this element will still be larger than the sum A_1 + A_2 + \ldots + A_{x-2}, so index x-1 is now non-cursed. - (x-1) was initially cursed, and after the swap x will be cursed instead.
- The cursedness of indices \gt x isn’t affected at all either.
So, the number of cursed indices remains the same; but we were able to move one non-cursed index one step to the left.
Repeat this process till the non-cursed indices form a prefix.
With this in mind, let’s try to form the largest possible prefix of non-cursed indices.
That is, we’d like to choose elements such that:
- A_1 has no conditions
- A_2\gt A_1
- A_3\gt A_1 + A_2
- A_4\gt A_1 + A_2 + A_3
\vdots
Clearly, at each step it’s best to choose the smallest element that satisfies the condition (if it exists).
This gives us the best chance of being able to satisfy further inequalities.
This gives us a straightforward algorithm to solve the problem.
Let B denote the answer array, initially empty.
For i = 1, 2, \ldots, N in order, repeat the following:
- Let S = B_1 + B_2 + \ldots + B_{i-1}.
- If there’s an element of A that’s \gt S, find the smallest such element and append it to B; while also removing it fro A. Update S appropriately.
- Otherwise, append any remaining element to B; we can’t make any more non-cursed indices anyway.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Preparer's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
vector <int> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
int ans = n;
int v = 0;
vector <int> b1, b2;
for (auto x : a){
if (x > v){
ans--;
v += x;
b1.push_back(x);
} else {
b2.push_back(x);
}
}
cout << ans << "\n";
for (auto x : b1) cout << x << " ";
for (auto x : b2) cout << x << " ";
cout << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif
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;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
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);
}
};
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
input_checker input;
int sum_n = 0;
auto __solve_testcase = [&](int testcase) -> void {
int n = input.readInt(1, (int)2e5); input.readEoln();
sum_n += n;
vector<int> a = input.readInts(n, 1, (int)1e9); input.readEoln();
sort(a.begin(), a.end());
long long sm = 0, cnt = 0;
vector<int> b, vis(n);
for(int i = 0 ; i < n ; ++i) {
if(a[i] > sm) {
b.push_back(a[i]); vis[i] = 1;
sm += a[i];
++cnt;
}
}
for(int i = 0 ; i < n ; ++i) if(!vis[i])
b.push_back(a[i]);
cout << n - cnt << '\n';
for(int i = 0 ; i < n ; ++i) {
cout << b[i] << " \n"[i == n - 1];
}
};
int no_of_tests = input.readInt(1, (int)2e4); input.readEoln();
for(int test_no = 1 ; test_no <= no_of_tests ; test_no++)
__solve_testcase(test_no);
assert(sum_n <= (int)2e5);
input.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
mark, cursum, ans = [0]*n, 0, []
while True:
ch = -1
for i in range(n):
if mark[i]: continue
if a[i] > cursum:
if ch == -1 or a[i] < a[ch]: ch = i
if ch == -1: break
mark[ch] = 1
ans.append(a[ch])
cursum += a[ch]
print(n - len(ans))
for i in range(n):
if not mark[i]: ans.append(a[i])
print(*ans)
