PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Binary search
PROBLEM:
There are N space stations. The i-th has capacity C_i.
Answer M independent queries, each detailing a mission:
- You are given values X and Y, representing the required crew capacity and storage capacity.
You should choose one of the space stations to accommodate the crew, and can use the others as storage.
If chosen optimally, find the minimum extra space needed to satisfy both constraints.
EXPLANATION:
Let S = C_1 + C_2 + \ldots + C_N denote the total capacity of all N space stations.
For a mission which has a crew capacity requirement of X and a storage requirement of Y, if we select the i-th space station to accommodate the crew, we need two inequalities to be satisfied:
- C_i \geq X to accommodate the crew.
- S - C_i \geq Y to satisfy storage requirements.
Note that S - C_i is exactly the sum of all capacities other than C_i.
Now, once C_i is chosen, there are four possibilities depending on which of the inequalities are satisfied.
If some inequality isn’t satisfied, we need to add more capacity to it.
Depending on which C_i is chosen, there are two cases: either C_i \geq X initially, or C_i \lt X initially.
Let’s look at each case, and specifically what the optimal choice of C_i would be in each case.
Case 1: C_i \geq X
Here, we don’t need to expand the crew space, but we might need to expand the storage space.
In particular, if Y \gt S - C_i, we’ll need (Y - S + C_i) tokens (and 0 otherwise).
Note that in this case, it’s ideal to choose the smallest valid C_i: this gives us the maximum possible storage space, minimizing the amount of extra that needs to be added.
Case 2: C_i \lt X
Here, we need (X - C_i) tokens, and potentially another Y - S + C_i more if there’s a lack of storage space.
In this case, it’s best to choose C_i as large as possible.
This is because increasing C_i by k will reduce X - C_i, while also increasing Y-S+C_i by k (and if the available storage space was initially more than Y, it will in fact increase by less than k). This means increasing C_i can never make the overall cost higher.
So, the optimal choice in this case is to just choose whichever C_i is just smaller than X.
We thus have a simple way to compute the answer for each query.
Sort the array C, and compute its sum S. Then, for the query (X, Y):
- Find the smallest C_i that’s \geq X (using binary search).
- If S - C_i \geq Y for this value, the answer is 0.
- Otherwise, Y - S + C_i tokens are needed.
- Find the largest C_i that’s \lt X, we need X - C_i tokens here (or 0, if X \leq C_i), along with another (Y-S+C_i) tokens if Y-S+C_i \geq 0.
- The answer is the minimum of the two above cases.
Each query needs only a couple of binary searches, taking \mathcal{O}(\log N) time.
TIME COMPLEXITY:
\mathcal{O}((N+M)\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int sumn = 0;
int sumq = 0;
void Solve()
{
int n; cin >> n;
assert(n != 1);
assert(2 <= n && n <= 200000);
sumn += n;
assert(sumn <= 200000);
vector <int> a(n);
for (auto &x : a) cin >> x;
for (auto x : a){
assert(1 <= x && x <= 1000000000);
}
// change the smallest < x to = x
// use the first >= x
sort(a.begin(), a.end());
int sum = accumulate(a.begin(), a.end(), 0LL);
// cout << sum << "\n";
int q; cin >> q;
sumq += q;
assert(sumq <= 200000);
vector <int> b(q), c(q);
for (int i = 0; i < q; i++){
cin >> b[i] >> c[i];
assert(1 <= min(b[i], c[i]) <= max(b[i], c[i]) <= 1000000000);
}
for (int i = 0; i < q; i++){
auto id = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
int ans = INF;
if (id != a.size()){
int x = a[id];
int left = sum - x;
ans = max(0LL, c[i] - left);
}
if (id > 0){
id--;
int x = a[id];
int left = sum - x;
ans = min(ans, b[i] - x + max(0LL, c[i] - left));
}
cout << ans << '\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++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n; cin >> n;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
sort(a.begin()+1,a.begin()+n+1);
ll sum = accumulate(all(a),0ll);
ll q; cin >> q;
while(q--){
ll x,y; cin >> x >> y;
ll pos = lower_bound(a.begin()+1,a.begin()+n+1,x)-a.begin();
ll ans = inf2;
if(pos <= n){
ll have = sum-a[pos];
ll need = y;
ll add = max(need-have,0ll);
amin(ans,add);
}
pos--;
if(pos >= 1){
ll have = sum-a[pos];
ll need = y;
ll add = max(need-have,0ll)+x-a[pos];
amin(ans,add);
}
cout << ans << endl;
}
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector a(n, 0);
for (int &x : a) cin >> x;
int q; cin >> q;
ranges::sort(a);
ll s = accumulate(begin(a), end(a), 0LL);
while (q--) {
ll x, y; cin >> x >> y;
ll ans = 1e18;
// find first a[i] that's >= x
auto it = ranges::lower_bound(a, x);
if (it != end(a)) ans = min(ans, max(0ll, y - s + *it));
if (it != begin(a)) ans = min(ans, x - *prev(it) + max(0ll, y - (s - *prev(it))));
cout << ans << '\n';
}
}
}