PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Testers: tabr, yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Sorting, binary search
PROBLEM:
There are N problems; Chef needs A_i minutes to solve the i-th one and will afterwards take a break of B_i minutes.
If he has K minutes of free time, what’s the maximum number of problems he can solve?
EXPLANATION:
Let’s call a problem fully solved if Chef both solves it and completely exhausts its break time, and partially solved if Chef solves it but does not exhaust its break time before K minutes are up.
It should be obvious that there can be at most one partially solved problem.
Further, if there is a partially solved problem, it will always be the last problem Chef solves.
Now, if Chef fully solves problem i, it will take A_i + B_i seconds. In particular, the order of fully solved problems doesn’t matter at all: only their A_i and B_i values since the total time taken is just their sum.
This means that ideally, we fully solve problems in increasing order of A_i + B_i.
So, sort the problems in increasing order of A_i + B_i.
Now, we have two cases: either there is a partially solved problem, or there isn’t.
Treat them separately and take the best answer.
No partially solved problem
Since there is no partially solved problem, if Chef solves i problems the time taken is simply A_1 + B_1 + A_2 + B_2 + \ldots + A_i + B_i.
Find the highest i such that this sum is \leq K; this can be done by simply iterating across the sorted array of A_i + B_i values.
There is a partially solved problem
There are a couple of different ways to solve this case. Here’s one method using binary search (though there exist ways to do it without binary search as well).
Suppose we fix problem x to be the partially solved problem. Problem x then takes up only A_x time; the B_x minutes of resting time can be ignored entirely.
Now, we need to choose some problems to solve fully, before problem i.
We can choose as many as we want, as long as their A_i + B_i values are at most K - A_x.
Once again, this can be done greedily: go from smallest to largest A_i + B_i values, pick as long as the sum is within the limit. Just make sure to ignore A_x + B_x, since we’re fixing it to be partially solved.
In particular, note that we take a prefix of the sorted A_i + B_i values (except maybe one element, if A_x + B_x belongs to this prefix).
That is, if we consider the prefix of length j, its value is A_1 + B_1 + A_2 + B_2 + \ldots + A_j + B_j, maybe minus A_x + B_x.
This is a non-decreasing sequence, so we can find the optimal j in \mathcal{O}(\log N) by binary searching!
The only thing that needs to be done is to compute prefix sums of the (sorted) A_i + B_i values, and check whether A_x + B_x lies in the given prefix (which is easy since you know x, just check if x \leq j).
This allows us to answer a fixed x in \mathcal{O}(\log N). Try every possibility of x for \mathcal{O}(N\log N) time.
TIME COMPLEXITY
\mathcal{O}(N\log N) per test case.
CODE:
Setter's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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, k; cin >> n >> k;
vector<array<int, 2>> v(n);
for (int i = 0; i < n; ++i) cin >> v[i][0];
for (int i = 0; i < n; ++i) cin >> v[i][1];
sort(begin(v), end(v), [](auto a, auto b) {
return a[0] + a[1] < b[0] + b[1];
});
int ans = 0, cur = 0;
for (int i = 0; i < n; ++i) {
cur += v[i][0] + v[i][1];
if (cur <= k) continue;
ans = i;
int mn1 = INT_MAX, mn2 = INT_MAX;
for (int j = 0; j < n; ++j) {
if (v[j][0] + v[j][1] <= v[i][0] + v[i][1]) mn1 = min(mn1, cur - v[j][1]);
}
if (mn1 <= k) ans = i+1;
cur -= v[i][0] + v[i][1];
for (int j = i; j < n; ++j) {
mn2 = min(mn2, cur + v[j][0]);
}
cur += v[i][0] + v[i][1];
if (mn2 <= k) ans = i+1;
break;
}
if (cur <= k) ans = n;
cout << ans << '\n';
}
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#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() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
// cerr << res << endl;
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);
if (res > maxv) cerr << res << " " << maxv << endl;
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;
}
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() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
input_checker in;
int tt = in.readInt(1, 2e4);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(1, 2e5);
sn += n;
in.readSpace();
int k = in.readInt(1, 1e8);
in.readEoln();
vector<int> a(n);
for (int i = 0; i < n; i++) {
a[i] = in.readInt(1, 1e8);
(i == n - 1 ? in.readEoln() : in.readSpace());
}
vector<int> b(n);
for (int i = 0; i < n; i++) {
b[i] = in.readInt(0, 1e8);
(i == n - 1 ? in.readEoln() : in.readSpace());
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
if (a[i] + b[i] == a[j] + b[j]) {
return a[i] > a[j];
}
return a[i] + b[i] < a[j] + b[j];
});
int ans = 0;
for (int i = 0; i < n; i++) {
k -= a[order[i]] + b[order[i]];
if (k < 0) {
k += a[order[i]] + b[order[i]];
for (int j = i; j < n; j++) {
if (k >= a[order[j]]) {
ans = max(ans, i + 1);
}
}
k -= a[order[i]] + b[order[i]];
for (int j = 0; j < i; j++) {
if (0 <= k + b[order[j]]) {
ans = max(ans, i + 1);
}
}
break;
}
ans = max(ans, i + 1);
}
cout << ans << '\n';
}
assert(sn <= 2e5);
in.readEof();
return 0;
}
Tester's code (C++, binary search)
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14
//Check ans for n=1
// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007ll //998244353ll
#define lld long double
#define mii map<int, int>
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=200005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
int g=__gcd(a, b);
return a/g*b;
}
int power(int a, int b, int p)
{
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int getRand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
int32_t main()
{
IOS;
int t;
cin>>t;
while(t--)
{
int n, k;
cin>>n>>k;
int a[n], b[n];
rep(i,0,n)
cin>>a[i];
rep(i,0,n)
cin>>b[i];
vector <pii> v;
rep(i,0,n)
v.pb({a[i]+b[i], a[i]});
sort(all(v));
vi pref={v[0].ff};
rep(i,1,n)
pref.pb(pref[i-1]+v[i].ff);
int res=0;
for(int i=0;i<n;i++)
{
if(v[i].ss<=k)
{
int lef=k-v[i].ss;
int lb=0, ub=n-1, ans=0;
while(lb<=ub)
{
int md=(lb+ub)/2;
int cur=0;
if(md)
{
if(md>i)
cur=(pref[md]-v[i].ff);
else
cur=pref[md-1];
}
if(cur<=lef)
{
ans=md;
lb=md+1;
}
else
ub=md-1;
}
res=max(res, ans+1);
}
}
cout<<res<<"\n";
}
}
