CAC2 - Editorial

editorial
, , ,
1

PROBLEM LINK:

True Game
Practice

Author: chirag_mathur
Editorialist: chirag_mathur

DIFFICULTY:

MEDIUM

PROBLEM:

Given the heights and widths of the boxes in a single line
Find Longest Increasing Subsequence from the left end such that the sum of widths of all the boxes chosen is maximum i.e distance of Amit.
Find Longest Non - Decreasing Subsequence from the right end such that the sum of widths of all the boxes chosen is maximum i.e distance of Saurav.
Print the name of Winner and distance traveled by him, in case of a tie print the name of Amit and distance traveled by him.

Prerequisites:

Stronghold on the concept of Weighted LIS, Dynamic Programming, and Segment Tree.
A little amount of brain to be applied while solving or understanding the editorial :wink:

EXPLANATION:

The idea is the same as finding the LIS but just to make sure that every time the weights of respective indexes to be updated. This can be implemented in various ways, one is the seg tree.
The i^th index tells that if we will choose I as the last element of LIS then we will get a total s[i] score.
Firstly, we will compress the array of heights and build a segment tree on it where the nodes will contain the max value( which will initially be 0). Then we will iterate over the array and will store the number of total elements(id) less than it (by using lower_bound), then we will make a query of 1 to id-1 to get the max value in this range (mx), then our current answer will be max( score[i]+mx, value at that node), which will be updated to our current index in the segment tree.
After N iterations, The max element in the entire range will be our answer.

##Another approach:
Maintain pairs (height[i], i) and sort them by heights, and now maintain a BIT Tree over N elements of the array, where the ith index of the BIT Tree denotes the ith index of the original array.
Now for every index 1<=i<=N, in pairs(described above), update the BIT array at index pair[i].second with value pair[i].first and dp[i] = Prefix sum of the elements of the BIT Tree from 1 to pair[i].second.
The answer will be the max(dp[i]) , 1<=i<=N.

SOLUTIONS:

Setter's Solution 
#include "bits/stdc++.h"
#define ll long long int
#define MOD 1000000007 
#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))

using namespace std;


struct SegTree{ 
   struct node{
       ll mx;
       node(){
           mx = 0;
       }
   };
   int n;
   vector<node> v; 
   node dummy;
   SegTree(int n){
       this->n = n;
       v.assign(4*n,dummy);
   }
   node merge(const node &a,const node &b){ 
       node res;
       res.mx = max(a.mx,b.mx);
       return res;
   }
   void update(int id,const int pos,const ll val,int s,int e){
       if(s>e) return;
       if(s==e){ 
           v[id].mx = max(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] = merge(v[2*id],v[2*id+1]);
       return;
   }
   void update(const int pos,const ll 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 merge(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 k){
      if(k<1) return 0;
      return query(1,k).mx; 
   }
};


vector<int> temp,h,w;
int n;

ll solve(bool x){
   SegTree s(temp.size()+2);
   for(int i=1;i<=n;i++){
       int id = lower_bound(all(temp),h[i]) - temp.begin() + 1;
       ll cnt = s.get(id - 1 + x);
       s.update(id , w[i] + cnt);
   }
   return s.get(temp.size()+2);
}

void __sol(){
   cin >> n;
   h.clear();
   w.clear();
   temp.clear();
   h.resize(n+1);
   w.resize(n+1);
   forr(i,n) cin >> h[i+1] , temp.eb(h[i+1]);
   forr(i,n) cin >> w[i+1];
   unique(temp);
   ll p1 = solve(0); // amit's score
   reverse(h.begin()+1,h.begin()+1+n);
   reverse(w.begin()+1,w.begin()+1+n);
   ll p2 = solve(1); // saurav's score
   if( p2 > p1 ) cout << "Saurav\n" << p2 <<"\n";
   else cout << "Amit\n" << p1 <<"\n";
   return;
}


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