PROBLEM LINK:
Author: Jenish Monpara
Tester: Daanish Mahajan
Editorialist: Aditi Goel
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Min-Heap Data Structure
PROBLEM:
At every second, we have to select one battery from the remaining batteries and it to the total energy. The battery being selected must be valid, i.e., it should not be destroyed and should be within the range of [t, N-t+1] at t^{th} second.
At the end of \lfloor \frac {(n+1)}{2}\rfloor^{th} second, we have to see if the total energy is \geq X to destroy the tanks and escape.
QUICK EXPLANATION:
We will see at the left and right end of the valid range at the t^{th} second, i.e., at t^{th} and N-t+1 ^{th} positions. Add greater of the two to the total energy. Now, we have to see if the lesser one is greater than least of the previously added values. If so, we will subtract the previously added value from the total energy and instead add this to it.
EXPLANATION:
We will see at the left and right end of the valid range at the t^{th} second, i.e., at t^{th} and N-t+1 ^{th} positions. Let mx and mn be maximum and minimum of these two values. We will add mx to the total energy. Now, we have to see if mn is greater than least of the previously added values. Let L be the least of the previously added values. If mn \gt L, we will subtract L from the total energy and instead add mn to it. This can be done using a min-heap data structure. At the end of \lfloor \frac {(n+1)}{2}\rfloor^{th} second, we have to see if the total energy is \geq X to destroy the tanks and escape.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 100050;
#define int long long
int32_t main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t,n,x,a[N];
cin>>t;
while(t–)
{
cin>>n>>x;
for(int i = 1;i <= n;i++)
{
cin>>a[i];
}
priority_queue<int,vector<int>,greater<int>> minheap;
int energy = max(a[1],a[n]);
minheap.push(max(a[1],a[n]));
for(int i = 2;i <= (n+1)/2 ;i++)
{
int left = i, right = n - i + 1;
int mx = max(a[left],a[right]), mn = min(a[left],a[right]);
if(left != right)
{
if(minheap.top() < mn)
{
energy -= minheap.top();
minheap.pop();
minheap.push(mn);
energy += mn;
}
}
energy += mx;
minheap.push(mx);
}
if(energy >= x)
{
cout<<"YES\n";
}
else
{
cout<<"NO\n";
}
}
}
Tester's Solution
include <bits/stdc++.h>
define pb push_back
define ll long long int
using namespace std;
FILE *fp;
ofstream outfile;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g==‘-’){
assert(fi==-1);
is_neg=true;
continue;
}
if(‘0’<=g && g<=‘9’){
x*=10;
x+=g-‘0’;
if(cnt==0){
fi=g-‘0’;
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret=“”;
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,’ ‘);
}
long long readIntLn(long long l,long long r){
return readInt(l,r,’\n’);
}
string readStringLn(int l,int r){
return readString(l,r,‘\n’);
}
string readStringSp(int l,int r){
return readString(l,r,’ ');
}
const int maxt = 1e5;
const int maxn = 1e5;
const int maxv = 1e6;
const int maxx = 1e9;
// int a[maxv + 10];
vector v;
multiset st;
int main()
{
int t = readIntLn(1, maxt);
int tn = 0;
while(t–){
v.clear(); //memset(a, 0, sizeof(a));
st.clear();
int n = readIntSp(1, maxn), x = readIntLn(1, maxx);
tn += n;
for(int i = 0; i < n - 1; i++)v.pb(readIntSp(0, maxv));
v.pb(readIntLn(0, maxv));
int first = max(v[0], v[n - 1]);
ll sum = first;
st.insert(first);
for(int i = 1; i < (n + 1) / 2; i++){
int vmax = max(v[i], v[n - i - 1]), vmin = min(v[i], v[n - i - 1]);
sum += vmax; st.insert(vmax);
if(i == n - i - 1)break;
multiset::iterator mval = st.begin();
if(vmin > *mval){
sum += vmin - *mval;
st.erase(mval);
st.insert(vmin);
}
}
cout << ((sum >= x) ? “YES” : “NO”) << endl;
}
assert(tn <= maxn);
assert(getchar()==-1);
// assert(getc(fp)==-1);
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll tc;
cin >> tc;
while(tc–){
ll n,x;
cin >> n >> x;
ll a[n+2];
for(int i=1; i<=n; i++) {
cin>>a[i];
}
multiset s;
s.insert(max(a[1],a[n]));
for(int i=2; i<=(n+1)/2; i++) {
s.insert(max(a[i],a[n-i+1]));
if(i == n-i+1)
break;
if(min(a[i],a[n-i+1])> *s.begin()) {
s.erase(s.begin());
s.insert(min(a[i],a[n-i+1]));
}
}
ll total=0;
for(auto itr: s) {
total += itr;
}
if(total >= x) {
cout<<"YES\n";
}
else {
cout<<"NO\n";
}
}
}
