Problem Link
Difficulty
Hard
Solution
Let’s assume that we have partitioned the array into m partitions like part_1,part_2..part_m. We define the pivot value of some partition as the minimum element in that partition. Suppose that the pivot value of part_k is 1, then it is easy to prove that we can club all the partitions lying to its left with it.
In general we can always club all the partitions from part_i to part_j where i<j, given that the pivot value of part_j is the smallest among them.
Based on this idea we can say that if it is possible to partition the original array, then we can always do so with partitions having pivot values, some subset of the longest increasing subsequence of arr having the first element equal to 1. Note that there will always be a partition with pivot value equal to 1.
Let’s assume that the longest increasing subsequence starting from 1 has indices p_1,p_2…p_k. We will iterate over these indices from the right side trying to form valid partitions. Let’s say we are currently at p_i and we have been able to partition arr[k...n] where p_i < k. So we will check if arr[(p_{i-1}+1)...(k-1)] is left heavy, if it is left heavy then we go down and check the same for arr[(p_{i-2}+1)...p_{i-1}]. In case arr[(p_{i-1}+1)...(k-1)] is not left heavy, we would check the same for arr[(p_{i-2}+1)...(k-1)].
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
vector<int>arr(n+1);
vector<ll>sum(n+1);
for(int i=1; i<=n; i++){
cin>>arr[i];
sum[i]=(sum[i-1]+arr[i]);
}
vector<int>pf(n+1);
pf[n]=arr[n];
for(int i=n-1; i>=1; i--){
pf[i]=min(arr[i],pf[i+1]);
}
vector<int>pivots;
for(int i=n; i>=1; i--){
if(arr[i]==pf[i])
pivots.push_back(i);
}
pivots.push_back(0);
int m=pivots.size();
int last=n;
vector<int>lengths;
for(int i=0; i<m-1; i++){
int len=last-pivots[i+1];
if(len<2)
continue;
ll sum1=sum[last]-sum[pivots[i]];
ll sum2=sum[pivots[i]-1]-sum[pivots[i+1]];
if(sum1<sum2){
lengths.push_back(len);
last=pivots[i+1];
}
}
if(last==0){
cout<<lengths.size()<<"\n";
int m=lengths.size();
for(int i=m-1; i>=0; i--)
cout<<lengths[i]<<" ";
cout<<"\n";
}
else
cout<<"-1\n";
}
return 0;
}