# CP06 Editorial

**URL:** <https://discuss.codechef.com/t/cp06-editorial/100426>\
**Category:** editorial\
**Tags:** constructive\
**Created:** [April 5, 2022, 4:50pm UTC](https://discuss.codechef.com/t/cp06-editorial/100426 "2022-04-05T16:50:41Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![saurav1717](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@saurav1717](https://discuss.codechef.com/u/saurav1717)\
**Post date:** [April 5, 2022, 4:50pm UTC](https://discuss.codechef.com/t/cp06-editorial/100426/1 "2022-04-05T16:50:41Z")

</div>

**Problem Link**

[Click here](https://www.codechef.com/SPY22022/problems/CP06)

**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**

```auto
#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;
}

```