0 like 0 dislike
3,193 views

edited | 3,193 views

0 like 0 dislike

Given an array nums of n integers. Delete a subsequence of length k (where k =n/3) from the array. Let's call the array B after deleting the subsequence. Now boy will be happy if the array B can be divided into 2 subarray of equal length such that difference between sum of elements of first subarray and sum of elements of second subarray is minimum possible. Boy asked you to make him happy. Note: It is guaranted that n is divisible by 3. Example 1: Input: nums = {7,9,5,7,2,1} Output: 3 Explanation: Delete the nums[2] and nums[6]. Then array B will be- {7, 5, 7, 2}. Now the array can be divided into {7,5} and {7,2}. So the answer will be (7+5)-(7+2) = 3. Example 2: Input: nums = {5,6,3} Output: -1 Explanation: Delete nums[3]. Then array B will be- {5,6}. Now the array can be divided into {5} and {6}. So the answer will be 5-6 = -1.

Contraints: 1<=n<=10^5

1<=nums[i]<=10^9

by Expert (119,060 points)
edited
0 like 0 dislike

Efficient C++ Code :

```#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

using namespace __gnu_pbds;
using namespace std;

typedef
tree<
pair<int,int>,
null_type,
less<pair<int,int>>,
rb_tree_tag,
tree_order_statistics_node_update>
st;

typedef long long int ll ;
ll g5[500005],v[500005];
ll a [200005];
ll rr = -1e18 ;
unordered_map <ll,ll> b ;
unordered_map <ll,ll> kk ;
unordered_map <ll,ll> u ;

ll c[200000];
ll segtree[1000000];

void build(ll node,ll start,ll end)
{
if(start==end)
{
segtree[node] = 0 ;
c[start] = 0 ;
}
else
{
ll mid=(start+end)/2;
build(2*node,start,mid);
build(2*node+1,mid+1,end);
segtree[node]=segtree[2*node]+segtree[2*node+1];
}
}

ll query(ll node,ll start,ll end,ll l,ll r)
{

if(start>r || end<l)
{
return 0;
}

if(start>=l && end<=r)
{
return segtree[node];
}

ll mid=(start+end)/2;

ll left=query(node*2,start,mid,l,r);
ll right=query(node*2+1,mid+1,end,l,r);

return (left+right);

}

void update(ll node,ll start,ll end,ll ind,ll value)
{
if(start==end)
{
segtree[node]+=value;
c[ind]+=value;
}
else
{
ll mid=(start+end)/2;

if(ind<=mid)
{
update(2*node,start,mid,ind,value);
}
else
{
update(2*node+1,mid+1,end,ind,value);
}

segtree[node]=segtree[2*node] + segtree[2*node+1];

}

}

int main() {

ll n ;
cin>>n ; ll w = 0 ;
ll i = 1 ; vector <ll> r ;
while(i<=n){
cin>>a[i];w = w + a[i];
kk[a[i]]++;
r.push_back(a[i]);
i++;
}
sort(r.begin(),r.end()) ;

i = 0 ;
while(i<r.size()) {
b[r[i]] = i + 1 ;
i++;
}
st t ;

i = 1 ;
while(i<=n){

update(1,0,200000,b[a[i]],a[i]) ;

u[a[i]]++;

t.insert({a[i],u[a[i]]});

//cout<<a[i]<<" "<<u[a[i]];
//cout<<"\n";

if(i>=n/3){

ll count = i - n/3 ;

//cout<<i<<"\n";
//cout<<count<<"\n";
auto g = t.find_by_order(count-1);
pair <int,int> r = *g ;
//cout<<r.first<<" "<<r.second ;
//cout<<"\n";

ll ookk = r.first ;

ll sum = query(1,0,200000,0,b[r.first]-1);
sum = sum + r.first*r.second ;
g5[i] = sum ;
//cout<<i<<" ";cout<<g5[i]<<"\n";
}

i++;
}

//cout<<"\n";
u.clear();
build(1,0,200000);
t.clear();
ll c = 1 ;
i = n ;
while(i>=1){

update(1,0,200000,b[a[i]],a[i]) ;

u[a[i]]++;

t.insert({a[i],u[a[i]]});

//cout<<a[i]<<" "<<u[a[i]];
//cout<<"\n";

if(c>=n/3){

ll count = c - n/3 ;

//cout<<i<<"\n";
//cout<<count<<"\n";
auto g = t.find_by_order(c-count);

if(count!=0){

pair <int,int> r = *g ;
//cout<<r.first<<" "<<r.second ;
//cout<<"\n";

ll ookk = r.first ;

ll sum = query(1,0,200000,b[r.first]+1,200000);

//cout<<"\n";
//cout<<sum ;
//cout<<"\n";

sum = sum + r.first*(abs(r.second-kk[r.first]) + 1) ;
v[i] = sum ;
//cout<<i<<" ";cout<<v[i]<<"\n";
}
else
{
v[i] = 0 ;
//RM_RM!!!!!!!!!
//cout<<i<<" "<<v[i]<<"\n";
}

}

c++;
i--;
}

i = 1 ;
ll sum2 = a[1] ;
ll sum5 = w - a[1] ;
while(i<=n){

ll y2 = i ;
ll y5 = n - i ;

if(y2>=n/3 && y5>=n/3){

ll v2 = (sum2-g5[i]);
ll v5 = (sum5-v[i+1]);

//cout<<i<<" "<<g[i]<<" "<<v[i+1];
//cout<<"\n";
ll ans = v2 - v5 ;
//cout<<ans ;
//cout<<"\n";
rr = max(ans,rr);
}

sum2 =  sum2 + a[i+1] ;
sum5 = w - sum2 ;
i++;
}
cout<<rr ;

return 0 ;
}```
by Expert (119,060 points)
0 like 0 dislike

Brute Force code :

```#include <bits/stdc++.h>

using namespace std;
typedef long long int ll ;
ll g[200005],v[200005];
ll rr = -1e18 ;
int main() {

ll n ;
cin>>n ; ll w = 0 ;
ll a[n+1]={0};
ll i = 1 ;
while(i<=n){
cin>>a[i];w = w + a[i];
i++;
}

i = 1 ;
while(i<=n){

if(i>=n/3){

vector <ll> t ;
ll j = 1;
while(j<=i){
t.push_back(a[j]);
j++;
}
sort(t.begin(),t.end());
ll sum = 0 ;
j = 0 ;
ll diff = i - n/3 ;
while(j<diff){
sum = sum + t[j] ;
j++;
}

g[i] = sum ;
cout<<i<<" ";cout<<g[i]<<"\n";
}

i++;
}

ll c = 1 ;
i = n ;
while(i>=1){

if(c>=n/3) {

vector <ll> t ;
ll j = i;
while(j<=n){
t.push_back(a[j]);
j++;
}
sort(t.begin(),t.end());
reverse(t.begin(),t.end());
ll sum = 0 ;
ll diff = (c-n/3);
j = 0 ;
while(j<diff){
sum = sum + t[j] ;
j++;
}

v[i] = sum ;
//cout<<i<<" ";cout<<v[i]<<"\n";
}

c++;
i--;
}

i = 1 ;
ll sum2 = a[1] ;
ll sum5 = w - a[1] ;
while(i<=n){

ll y2 = i ;
ll y5 = n - i ;

if(y2>=n/3 && y5>=n/3){

ll v2 = (sum2-g[i]);
ll v5 = (sum5-v[i+1]);

//cout<<i<<" "<<g[i]<<" "<<v[i+1];
//cout<<"\n";
ll ans = v2 - v5 ;
//cout<<ans ;
//cout<<"\n";
rr = max(ans,rr);
}

sum2 =  sum2 + a[i+1] ;
sum5 = w - sum2 ;
i++;
}
cout<<rr ;

return 0 ;
}```
by Expert (119,060 points)