MERCO-Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice Link
Merge Companies

Author: vikiwarrior
Editorialist: vikiwarrior
Tester: dragno99

PROBLEM:

There are N companies in your area. Let A_i be the net-worth of the ith company.
After the pandemic, they start acquiring each other. A company can only acquire its adjacent
company (the nearest company to its left or to its right, provided it exists).

Let’s say, if company-1 of net-worth x acquires its adjacent company-2 of net-worth y then company-2 disappears and company-1 net-worth changes to x - y.
This goes on until only one company remains.

Now you need to answer Q queries of the following type :

L R

You need to find the maximum net-worth of the last remaining company if the companies in the range L to R (both inclusive) start acquiring each other.

NOTE: Each query is independent to each other and after each query the initial array will be retained in order to process the next query.

PREREQUISITES:

  • Maths
  • RMQ

DIFFICULTY:

MEDIUM

EXPLANATION:

Firstly, let’s see calculate the answer for a single query

Each company in the query range will either be added or subtracted to the final answer.
Now, observe that any combination of addition and subtraction is valid except adding all or subtracting all.

Now to maximize the answer we have a few cases :

  • If only positive net-worth companies are present, we add everything to the result except the minimum element which we subtract.

  • If only negative net-worth companies are present, we subtract everything to the result and add the minimum element.

  • Now if we have a mix of positive and negative net-worths, then we simply add the absolute values of all the net worths.

  • Also note, if we have 1 element in the range then the answer would the element itself and not the absolute value.

We have solved the problem for a single query. Let’s do it efficiently.

To calculator the sum of absolute values in a range we could use a prefix sum array.
And to find the minimum elements in a range we could use a segment tree or sparse table.

See setter and tester codes for implementation.

SOLUTION:

Setter's Solution in C++ 
//vikiwarrior - Vikrant Kumar
#include <bits/stdc++.h>
#define ll long long int

using namespace std;

const int MAXN = 100000;
const int K = 20;
int logg[MAXN + 1];
int st[MAXN][K + 1];

int main()
{
  
 logg[1] = 0;
 for (int i = 2; i <= MAXN; i++)
   logg[i] = logg[i / 2] + 1;

 ll n;
 ll i;
 cin >> n;

 ll a[n];
 ll sum[n + 1];
 sum[0] = 0;

 for (i = 0; i < n; i++)
 {
   cin >> a[i];
   sum[i + 1] = sum[i] + abs(a[i]);
 }

 for (ll i = 0; i < n; i++)
   st[i][0] = abs(a[i]);

 for (ll j = 1; j <= K; j++)
   for (ll i = 0; i + (1 << j) <= n; i++)
     st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);

 int neg_count[n + 1];
 neg_count[0] = 0;
 int count = 0;
 for (i = 0; i < n; i++)
 {
   if (a[i] < 0)
   {
     count++;
     neg_count[i + 1] = count;
   }
   else
     neg_count[i + 1] = count;
 }

 int q;
 cin >> q;


 for (i = 0; i < q; i++)
 {
   ll l, r;
   cin >> l >> r;
   
   if (r == l)
   {
     cout << a[r - 1] << endl;
   }
   else if (neg_count[r] - neg_count[l - 1] == r - l + 1 || neg_count[r] - neg_count[l - 1] == 0)
   {
    
     ll j = logg[r - l + 1];
     ll minimum = min(st[l - 1][j], st[(r - 1) - (1 << j) + 1][j]);
     cout << sum[r] - sum[l - 1] - 2 * minimum << endl;
     // cout<<minimum<<endl;
   }
   else
   {
     cout << sum[r] - sum[l - 1] << endl;
   }
 }

 return 0;
}
Tester's Solution in C++ 
/*  Jai Shree Ram 🚩🚩🚩 */
#include "bits/stdc++.h"
#define ll long long int
#define oo 1000000000000000000
#define forr(i,n) for(int i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define unique(v) sort(all(v)); v.resize(distance(v.begin(),unique(all(v))))
#define eb emplace_back
#define FF first
#define SS second
#define mem(a,v) memset(a,v,sizeof(a))
#define pb push_back
#define popcount(x) __builtin_popcount(x)

using namespace std;

template<typename T>
ostream &operator<<(ostream &output,const vector<T> &v){ 
   if(v.empty()) return output;
   for(int i=0;i<v.size()-1;i++) output << v[i] <<" ";
   output << v.back();
   return output;
}
template<typename T>
istream &operator>>(istream &input,vector<T> &v){ 
   for(auto &i: v) cin >> i;
   return input;            
}
struct SegTree{
   struct node{
       // variable
       int mn , mx;
       ll sum;
       node(){ // constructor 
           sum = 0;
           mn = INT_MAX;
           mx = INT_MIN;
       }
       friend node const operator + (const node &a,const node &b){
           node res;
           res.sum = a.sum + b.sum;
           res.mn = min(a.mn , b.mn);
           res.mx = max(a.mx , b.mx);
           return res;
       }
   };
   int n;
   // vector<node> v; 
   node* v;
   node dummy; // dummy node
   SegTree(int n){
       this->n = n;
       v = new node[4 * n + 10];
       for(int i=0;i<4*n+10;i++){
           v[i] = dummy;
       }
       // v.assign(4*n+10,dummy);
   }
   void update(int id,const int pos,const int val,int s,int e){
       if(s>e) return;
       if(s==e){ // base case
           v[id].sum = abs(val);
           v[id].mn = val;
           v[id].mx = val;
           return;
       }
       int mid = (s+e)/2;
       if(pos<=mid) update(2*id,pos,val,s,mid);
       else update(2*id+1,pos,val,mid+1,e);
       v[id] = v[2*id] + v[2*id+1];
       return;
   }
   void update(const int pos,const int val){
       update(1,pos,val,1,n);
   }
   node query(int id,const int l,const int r,const int s,const int e){
       if(s>e || r<s || l>e) return dummy;
       else if(l<=s && e<=r) return v[id];
       else return query(2*id,l,r,s,(s+e)/2) + query(2*id+1,l,r,(s+e)/2+1,e);
   }
   node query(const int l,const int r){
       return query(1,l,r,1,n);
   }
   ll get(int l,int r){
      node res = query(l,r);
      if(l == r) return res.mx;
      else if(res.mn >= 0) return res.sum - 2 * res.mn;
      else if(res.mx < 0) return res.sum + 2 * res.mx;
      else return res.sum; 
   }
};

void __sol(){
   int n; cin >> n;
   SegTree s(n);
   forr(i,n){
       int x; cin >> x;
       s.update(i + 1 , x);
   }
   int q; cin >> q;
   forr(_,q){
       int l,r;
       cin >> l >> r;
       cout << s.get(l,r)<<"\n";
   }
   return;
}


int main(){ 
   fastio;
   int tc=1;  // cin >> tc;
   while(tc--) __sol();
   return 0;
}
2 Likes