PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
An anti-subarray is any subset that’s not a subarray.
Given an integer array A, a boolean array B, and X, find the minimum number of the following operations needed to obtain an anti-subarray with sum at least X:
- Choose an index i such that B_i = 1, and increase A_i by 1.
EXPLANATION:
Observe that an anti-subarray must have a “hole” in it somewhere - meaning, there must exist some index i such that:
- i is not part of the anti-subarray; and
- There are elements both to the left and to the right of i present in the anti-subarray.
Next, suppose we fix an anti-subarray, say with sum S.
Then, observe that:
- If S \geq X, no operations are needed.
- Otherwise, S \lt X.
- If there’s some non-negative element present in S that has B_i = 1, we can simply increase it X-S times and obtain a sum of X, and this is clearly optimal.
- Otherwise, only negative elements of S have B_i = 1. In this case, it’s of course optimal to choose the largest element of S to increase.
Let M be the largest element present; we then need (X-S)-M moves (note that M is negative here). - The above two points can be generalized into a single one: if M is the largest element of the anti-subarray that can be modified, the number of moves needed is X - S - \min(M, 0).
Let’s fix i to be the index of the “hole”, and try to obtain as large a sum as we can when considering only anti-subarrays.
This is fairly simple to do:
- When considering indices \lt i, if there are any non-negative elements then we can take all non-negative elements.
Otherwise, everything’s negative, and we take just one element: the largest one. - Similarly, for indices \gt i, take either all non-negative elements (if they exist), or just the largest negative one if everything’s negative.
Let L_i be the sum of elements taken from the left side, and R_i be the sum from the right side.
The maximum possible sum of an anti-subarray that doesn’t include i is then L_i+R_i.
Now, if L_i+R_i \geq X, we already have a subset with sum \geq X so we’re done.
Otherwise, we need some addition operations.
It should be obvious that it’s ideal to perform all the addition operations on a single element.
We now consider two cases: all the additions are performed on an element on the left side, or on the right side.
The cases are symmetric, so we’ll focus on just the left side for now.
Recall that L_i is the sum of elements chosen on the left side.
Also, let M_L be the maximum value of some element on the left side which can be modified.
Now,
- If M_L \geq 0, some non-negative element can be modified.
This means we’ll need exactly X - (L_i+R_i) moves, since each move increases the sum by 1. - If M_L \lt 0, we have a couple of cases.
- First, suppose L_i \geq 0, meaning we’ve taken all positive elements.
Then, our best shot is to just keep increasing the element M_L till the required sum is reached.
This needs X - (L_i+R_i) - M_L operations, since we need -M_L operations to make this element 0 first. - Next, suppose L_i \lt 0, so we’ve taken a single negative element.
Here, since we’ve decided to modify something on the left anyway (and it will end up being positive due to our needs), we can ignore the already taken negative element.
So, the number of moves needed is X - R_i - M_L.
- First, suppose L_i \geq 0, meaning we’ve taken all positive elements.
- All the above cases can be nicely folded into the expression X - R_i - \max(L_i, 0) - \min(M_L, 0) to avoid any casework.
Similarly, for the right side we obtain X - L_i - \max(R_i, 0) - \min(M_R, 0) as the minimum number of modifications needed on that side.
As seen above, if we fix i and know the values L_i, R_i, M_L, M_R the rest of the computations take only constant time.
So, if we can find these quantities quickly, we’ll be done.
They can all be precomputed in linear time easily enough:
- M_L is the largest modifiable value on the prefix, it’s easy to just store this for every prefix.
- L_i is the maximum possible sum of some non-empty subset of the prefix before i.
This can be computed as follows:- Initialize L_i = L_{i-1}.
- Then, if L_i \lt 0, set L_i := \max(L_i, A_{i-1}), since only the largest element on the prefix before i matters.
- Otherwise, add \max(0, A_{i-1}) to L_i since we’re taking all non-negative elements.
With this precomputation, each index can be processed in constant time.
The final answer is, of course, the minimum of the answers across all “holes” i.
The problem is also solvable using dynamic programming, which can be seen in the tester’s code below.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
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--) {
ll n, x; cin >> n >> x;
vector a(n, 0ll);
for (auto &y : a) cin >> y;
vector b(n, 0);
for (auto &y : b) cin >> y;
const ll inf = 1e18;
vector pre(n, -inf), suf(n, -inf);
vector mxl(n, -inf), mxr(n, -inf);
for (int i = 0; i < n; ++i) {
if (i) pre[i] = pre[i-1], mxl[i] = mxl[i-1];
if (pre[i] < 0) pre[i] = max(pre[i], a[i]);
else pre[i] += max(0ll, a[i]);
if (b[i] == 1) mxl[i] = max(mxl[i], a[i]);
}
for (int i = n-1; i >= 0; --i) {
if (i < n-1) suf[i] = suf[i+1], mxr[i] = mxr[i+1];
if (suf[i] < 0) suf[i] = max(suf[i], a[i]);
else suf[i] += max(0ll, a[i]);
if (b[i] == 1) mxr[i] = max(mxr[i], a[i]);
}
ll ans = inf;
for (int i = 1; i+1 < n; ++i) {
ll lt = pre[i-1], rt = suf[i+1];
if (lt + rt >= x) {
ans = 0;
break;
}
// Increase on left
if (mxl[i-1] > -inf) {
ans = min(ans, x - rt - max(0ll, lt) - min(0ll, mxl[i-1]));
}
// Increase on right
if (mxr[i+1] > -inf) {
ans = min(ans, x - lt - max(0ll, rt) - min(0ll, mxr[i+1]));
}
}
cout << ans << '\n';
}
}
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,k; cin >> n >> k;
vector<ll> a(n+5), b(n+5);
rep1(i,n) cin >> a[i];
rep1(i,n) cin >> b[i];
ll dp[n+5][2][2][2]; // dp[i][started][gap][bi=1 taken?]
memset(dp,-0x3f,sizeof dp);
dp[1][0][0][0] = 0;
ll ans = inf2;
rep1(i,n){
rep(started,2){
rep(gap,2){
rep(one_taken,2){
ll curr = dp[i][started][gap][one_taken];
// pick curr guy
amax(dp[i+1][1][gap][one_taken|b[i]],curr+a[i]);
if(gap){
// gap and take --> upd ans
ll val = curr+a[i];
ll ot = one_taken|b[i];
if(val >= k){
ans = 0;
}
else if(ot){
amin(ans,k-val);
}
}
// ignore curr guy
amax(dp[i+1][started][gap|started][one_taken],curr);
}
}
}
}
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}