PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: nikhil_010309
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Greedy
PROBLEM:
You are given an array A and a binary string S.
The resonance of a subarray is the sum of its elements minus the sum of adjacent pairwise minimums.
A subarray is called valid if its resonance equals its maximum element.
You can flip characters of the binary string for a cost, given by an array C.
The total cost of this must not exceed B.
The ones in the binary string partition A into several subarrays.
Find the lexicographically largest S that can be reached within the given budget, such that every subarray in the partition is valid.
EXPLANATION:
First, we need to understand resonance, and when a subarray can be valid.
The resonance of A[L, R] is given by
which can be written as
Now, the term A_k - \min(A_k, A_{k-1}) equals 0 if A_k \le A_{k+1}, and equals A_k - A_{k+1} otherwise.
One way of looking at this is that is measures the “fall” in value from index k to index k+1, lowerbounded by 0.
So, that entire summation measures the total “fall” in value of the subarray, plus the last element.
For the subarray to be valid, this must equal the maximum element.
This is only possible when the subarray is first non-decreasing, and then non-increasing, i.e. there’s some x \in [L, R] such that the subarray looks like
Now that we know what a valid subarray must look like, let’s see what it means for a subarray to be not valid.
We’ll call the subarray from L to R a valley if:
- L+2 \le R, i.e. the subarray has length at least 3,
- A_L \gt A_{L+1} and A_{R-1} \lt A_R, i.e. the endpoints are larger than their neighbors, and
- A_{L+1} = A_{L+2} = \ldots = A_{R-1}, i.e. the “middle” elements are all equal.
Observe that a subarray is not valid if and only if it contains a valley; since being not valid means it has to fall and then rise again later, and valleys are minimal examples of such a situation.
Thus, for each valley in the array, we definitely need to have a subarray divider placed within it - that is, one among S_L, \ldots, S_{R-1} must equal 1.
Conversely, as long as this condition is satisfied for every valley, every subarray in the resulting partition will certainly be valid.
Helpfully, note that two valleys cannot intersect except at their endpoints; which means that the dividers corresponding to different valleys are disjoint.
This allows us to solve the problem greedily.
For a solution to exist at all, every valley must have at least one divider chosen within it. In particular, for any valley that doesn’t initially have a divider, the best we can do is activate the cheapest divider within it.
If doing this minimal amount of activation already gets us past the budget, then no solution exists.
Otherwise, a solution exists for sure; so we only need to find the lexicographically largest one.
That can be done greedily.
For each i = 1, 2, \ldots, N-1,
- If S_i = 1, do nothing. Leaving this divider activated doesn’t hurt anything, and un-activating it is not helpful in any way (and might be detrimental.)
- If S_i = 0, try activating it by paying C_i.
This is valid only if, after doing it, we still have enough budget to activate all yet-unsatisfied valleys; which can be checked by just storing the sum of costs of all unsatisfied valleys and updating this sum appropriately.
Everything here can be done in linear time.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (PyPy3)
t = int(input())
while t:
t-=1
n,B = map(int,input().split())
a = list(map(int,input().split()))
b = [int(x) for x in input()]
c = list(map(int,input().split()))
coll = []
last = -1
for i in range(n-1):
if a[i]>a[i+1]: last = i
elif a[i]<a[i+1] and last>-1: coll.append((last,i)); last = -1;
mi = [0]*n
team = [-1]*n
for i in range(len(coll)):
l,r = coll[i]
flag = 0
mii = float("inf")
for j in range(l,r+1):
flag+=b[j]
mii = min(mii,c[j])
team[j] = i
if not flag: mi[i] = mii
B -= sum(mi)
if B<0: print(-1); continue
for i in range(n-1):
if b[i]: continue
if B-c[i]+mi[team[i]]>=0:
B-=c[i]-mi[team[i]]
mi[team[i]] = 0
b[i] = 1
print(*b,sep='')
Tester'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());
void Solve()
{
// inc and then dec is good
// if decrease and then increase, need to have cut?
int n, b; cin >> n >> b;
vector <int> a(n + 1);
for (int i = 1; i <= n; i++){
cin >> a[i];
}
string str; cin >> str;
str = "0" + str;
vector <int> c(n);
for (int i = 1; i < n; i++){
cin >> c[i];
}
// dp[i][0/1] = given that you are at index i, with 0/1 denoting "have seen dec", how much cost to finish
vector<vector<int>> dp(n + 1, vector<int>(2, INF));
dp[n][0] = 0;
dp[n][1] = 0;
for (int i = n - 1; i >= 1; i--){
int split = str[i] == '0' ? c[i] : 0;
int keep = str[i] == '0' ? 0 : c[i];
for (int s = 0; s < 2; s++){
int ns = s;
dp[i][s] = split + dp[i + 1][0];
if (s == 1 && a[i] < a[i + 1]) continue;
if (s == 0 && a[i] > a[i + 1]) ns = 1;
dp[i][s] = min(dp[i][s], keep + dp[i + 1][ns]);
}
}
if (dp[1][0] > b){
cout << -1 << "\n";
return;
}
string ans = "";
int s = 0;
for (int i = 1; i < n; i++){
int split = str[i] == '0' ? c[i] : 0;
int keep = str[i] == '0' ? 0 : c[i];
int opt1 = split + dp[i + 1][0];
int ns = s;
if (s == 0 && a[i] > a[i + 1]) ns = 1;
int opt2 = keep + dp[i + 1][ns];
if (opt1 <= b){
ans += "1";
b -= split;
s = 0;
} else {
ans += "0";
b -= keep;
s = ns;
}
}
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;
}