BATTERY - Editorial

PROBLEM LINK:

Practice

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

}
}

9 Likes

I am having trouble understanding , why cant we simply keep on adding the greatest of the two available options each time( the two options are the two batteries that will be immediately destroyed in the next second)?

1 Like

Consider this kind of battery arrangement
1 1 100 105 1 1

1 Like

I understand now :sweat_smile:

Can you tell me why I’m getting wrong answer with this solution? My solution approach is same as described in this editorial but I didn’t use min-heap.
https://www.codechef.com/viewsolution/40953089

Your code might be adding the middle element twice in some cases.
Try this case:
5 15
1 1 10 1 1
Your code will give the output as YES, which is not correct

1 Like

i am not getting what’s wrong in my piece of code…so pls anyone check and guide me through…my code

Thank you so much for the help. Now I got it.

I think you are taking the maximum available value i s.t. ( t ≤ i ≤ N−t+1). And then you are replacing the value with 0. But, as the maximum values can be at middle sometimes, and the lower values at the ends of the array, you will miss the end energies as those energies will be gone by then anyway.
For better understanding, let’s take an example:
1
6 6
1 1 2 3 1 1

What your code does is that, at first takes the 4th index(1 based) valued 3, then takes the 3rd index valued 2 and then a 0, giving a total of 5. Thus giving output NO.

But, at the 1st second we can take any value from the either end as both are 1. then we can the 2, and at last second we can take the value 3, giving a total of 6. So, correct output will be YES.

You can read the editorial again. It’s a nicely written editorial. I hope the approach will be more clear to you after that.

2 Likes

I am not getting what’s wrong in my piece of code… Please someone tell me about my code where does it lagging?
https://www.codechef.com/viewsolution/40977397

Could you once provide a counter example for this submission:
https://www.codechef.com/viewsolution/40985372
My approach might be different from the one mentioned in the editorial as I want to try my best before I give up on this problem. But I am stuck with WA.
Thanks in advance.