# SOLVEMORE - Editorial

Author: iceknight1093
Testers: tabr, yash_daga
Editorialist: iceknight1093

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;
}

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);
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);
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);
assert(minv <= res);
assert(res <= maxv);
return res;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
input_checker in;
int sn = 0;
while (tt--) {
sn += n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
}
vector<int> b(n);
for (int i = 0; i < n; i++) {
}
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);
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;
}

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";
}
}


Can you please provide the last test case for this problem. My code with almost same logic is passing all the test case except last one. If u provide me the last test case, i can know my miskate.Thank you!

@iceknight1093 What is wrong in this ---- as soon as the sum is about to exceed k (we are traversing from left to right in the sorted array in the same way as discussed by you) we break from that point and go on for looking from that point onwards and see for the existence of any Ai which is <=(k-sum) in that case we do ans++ otherwise no increment ?

4 Likes

I was also doing the same thing as editorial but I missed one which was
Assume I have taken i sorted elements from a[x]+b[x] array. Now if I am not able to take i+1 element, I can take this i+1 element as whole make try to make one of the i element partial or more specifically I can pick the element with largest break time.

Other cases were i do not take partial, or i take a different partial element

Very Similar problem 1791 G2

I got the answer by working out on it myself. If some one has similar doubt here is the test case for the special case :

n=3 k=10
1 2 6
2 1 0

In sorted form:
{1,2},{2,1},{6,0} (here if we include the third one it’s paper time is exceeding beyond limit 3+3+6=12 > 10 )

therefore, {6,0},{2,1},{1,2} (6+3+1=10 which is within limit)

7 Likes

They’re similar because they use the same technique: sorting by a certain parameter.
Rather common technique, often called exchange arguments. You can find an explanation and more similar problems in this blog.

1 Like

Why is my code receiving RuntimeError (SIGSEGV) ? Nowhere in my code I am accessing out of bound memory location.