Problem reference:- USACO 248 (2016 US Open, Gold)

I recently solved the USACO. The standard expected solution is an O(n^3) range dp. I tried a greedy divide and conquer approach with O(nlogn) avg. and O(n^2) worst case complexity, which to my surprise worked.

I wanted to share the logic here to see if this is a known trick for similar combination games.

The problem asks us to find the maximum possible number we can generate by adjacent equal numbers.

The O(N^2) Observation Instead of looking at all possible subarray splits, we can just look at the global minimum element in the current array. Let this be mini. Because it is the absolute minimum, it is impossible to ever create a new mini. You can only combine existing ones. -> Even length Clumps of adj mini Collapse -> Odd length clumps are permanent partitions

The Algorithm Find mini in the current array. Traverse the array and group adjacent minis into clumps. For purely even clumps, convert them directly into mini+1. For odd clumps, use them as split points to divide the array into smaller chunks, branching to try collapsing the left-side of the clump vs the right-side of the clump. Recursively call the function on these new, smaller partitioned arrays.

#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll func(const vector<ll>& arr) {
    int n=arr.size();
    if (n==0)return -1;
    if (n==1)return arr[0];

//Find the global minimum element
    ll mini=1e18;
    for(ll x:arr) {
        mini=min(mini,x);
    }

//Identify partition points (boundaries of odd clumps)
    vector<ll>part_start,part_end;
    ll pre=-1;
    ll cnt=0;
    
//Find starting boundaries for partitions
    part_start.push_back(-1);
    for (int j=0; j<n; j++) {
        if (arr[j]!=pre&&arr[j]==mini) {
            if (cnt%2==0&&cnt!=0)part_start.pop_back();
            part_start.push_back(j);
            cnt=0;
        }
        if(arr[j]==mini)cnt++;
        pre=arr[j];
    }
    if(cnt%2==0&&cnt!=0)part_start.pop_back();

    pre=-1;
    cnt=0;
    
//Find ending boundaries for partitions
    for(int j=n-1; j>=0; j--) {
        if(arr[j]!=pre&&arr[j]==mini) {
            if (cnt%2==0&&cnt!=0)part_end.pop_back();
            part_end.push_back(j);
            cnt=0;
        }
        if(arr[j]==mini)cnt++;
        pre=arr[j];
    }
    if (cnt%2==0&&cnt!=0)part_end.pop_back();

    reverse(part_end.begin(),part_end.end());
    part_end.push_back(n);

    ll ans=0;

    

//Process elements inside each valid partition
    for(int p=0; p<part_start.size(); p++) {
        vector<ll>temp;
        
        int ind1=part_start[p]+1;
        int ind2=part_end[p]-1;
        int cnt1=0, cnt2=0;
        
        //Count overlapping minimums at the boundaries
        while(ind1<=ind2&&arr[ind1]==mini) {
            cnt1++;
            ind1++;
        }
        while(ind2>=ind1&&arr[ind2]==mini) {
            cnt2++;
            ind2--;
        }

        //Collapse even pairs of 'mini' on the left boundary
        for (int i=0; i<cnt1/2; i++) {
            temp.push_back(mini+1);
        }
        
        //Process the middle part: collapse isolated pairs of 'mini'
        for (int i=ind1; i<=ind2; i++) {
            if(arr[i]==mini){
                temp.push_back(mini+1);
                i++; // Skip the paired element
            }
            else{
                temp.push_back(arr[i]);
            }
        }
        
        //Collapse even pairs of 'mini' on the right boundary
        for (int i=0; i<cnt2/2; i++) {
            temp.push_back(mini+1);
        }

        //Recursively branch on this partitioned state
        ans=max(ans,func(temp));
    }

    return ans;
}

int main() {
    freopen("248.in","r",stdin);
    freopen("248.out","w",stdout);
    ll n;
    cin >> n;
    vector<ll>arr(n);

    for (auto &x:arr)cin>>x;

    cout<<func(arr)<<"\n";
    
}