**Problem reference:-** [USACO 248 (2016 US Open, Gold)](http://www.usaco.org/index.php?page=viewproblem2&cpid=646)↵
↵
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";↵
↵
}↵
~~~~~
↵
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";↵
↵
}↵
~~~~~
