Header Ad

HackerEarth Zero subarray problem solution

In this HackerEarth Zero subarray problem solution, we have given an array A of N elements. You can apply the given operations on array A.

Type 1: Choose an index i (1 ≤ i ≤ N) and set A[i] = A[i] - 1.
Type 2: Choose an index i (1 ≤ i ≤ N) and set A[i] = 0.
Find the maximum length subarray in array A where all the elements in the subarray is 0 by using at most X operations of Type 1 and Y operations of Type 2.


HackerEarth Zero subarray problem solution


HackerEarth Zero subarray problem solution.

#include<bits/stdc++.h>
#define int long long int
using namespace std;
int n, x, y;
int a[100005];

bool check(int l){
multiset<int>p,q;
int sum = 0;

for(int i = 1 ; i <= l ; i++){
p.insert(a[i]);
if((int)p.size() > y){
int value = *(p.begin());
sum += value;
q.insert(value);
p.erase(p.begin());
}
}

if(sum <= x) return true;

for(int i = l + 1 ; i <= n ; i++){
p.insert(a[i]);
if((int)p.size() > y){
int value = *(p.begin());
sum += value;
q.insert(value);
p.erase(p.begin());
}

multiset<int>::iterator it = q.find(a[i - l]);
if(it != q.end()){
q.erase(it);
sum -= a[i - l];
}
else{
it = q.end();
it--;

int value = *it;
sum -= value;
q.erase(it);
p.insert(value);
p.erase(p.find(a[i-l]));
}

if(sum <= x) return true;
}

return (sum <= x);
}

void solve(){
cin >> n >> x >> y;
assert(1 <= n and n <= 100000);
assert(0 <= x and x <= 100000000000000);
assert(0 <= y and y <= 1000000000);
for(int i = 1 ; i <= n ; i++){
cin >> a[i];
assert(0 <= a[i] and a[i] <= 1000000000);
}

int ans = min(y, n);
int s = min(y, n) + 1;
int e = n;
while(s <= e){
int m = (s + e)/2;
if(check(m)){
ans = m;
s = m + 1;
}
else{
e = m - 1;
}
}
cout << ans << endl;
}

signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
assert(1 <= t and t <= 5);
while(t--){
solve();
}
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14;
int n, a[MAX_N], y;
ll x;

int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--) {
cin >> n >> x >> y;
for (int i = 0; i < n; ++i)
cin >> a[i];
multiset<int> bigs, smalls;
int ptr = 0, ans = 0;
ll sum = 0;
for (int i = 0; i < n; ++i) {
bigs.insert(a[i]);
if (bigs.size() > y) {
smalls.insert(*bigs.begin());
sum += *bigs.begin();
bigs.erase(bigs.begin());
}
while (sum > x) {
if (bigs.find(a[ptr]) != bigs.end()) {
bigs.erase(bigs.find(a[ptr]));
if (!smalls.empty()) {
bigs.insert(*smalls.rbegin());
sum -= *smalls.rbegin();
smalls.erase(--smalls.end());
}
}
else {
sum -= a[ptr];
smalls.erase(smalls.find(a[ptr]));
}
++ptr;
}
ans = max(ans, i - ptr + 1);
}
cout << ans << '\n';
}
}


Post a Comment

0 Comments