Maps for Splitting Groups
National Olympiad — National round
Submission name: maps.cpp
Problem summary
Each cell of an N×M matrix represents a hut with its given altitude. A group may move to ANY hut of strictly greater altitude. At a decision it may instead split into two groups choosing two different higher huts. Previously separated groups never merge, even when they meet, and can split independently. Choose the starting hut to maximize the final number of groups when no more splits are possible.
Input
N M, followed by the N×M altitudes.
Output
The maximum final group count modulo 1,000,000,007.
Constraints
1 ≤ N,M ≤ 500; 1 ≤ altitude ≤ 1,000,000.
Worked example
An independently prepared example for this explanation.
Input
1 4 1 2 3 4
Output
3
Solution analysis
- Process distinct altitudes in descending order. For a hut, the best outcome is the sum of the two largest outcomes at different higher huts; with fewer than two higher huts it is one.
- All huts of the same altitude must be calculated before adding that altitude to the available choices. Actual outcomes never decrease as altitude decreases, so keep the latest two outcomes in this monotone order, while storing only their residues.
Why it works
The first split produces two independent subproblems, so choosing the best two higher huts is optimal. Moving before splitting cannot improve on the best choices already available. Equal-altitude huts are unavailable to one another. Monotonicity, rather than residues, determines which outcomes are largest.
Watch out. Movement is not restricted to neighboring cells. Do not sort the modular residues as though they were actual counts.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<int>a(n*m);
for(int&x:a){
cin>>x;
}
sort(a.rbegin(),a.rend());
const long long P=1000000007;
long long first=0,second=0,ans=1;
int available=0;
for(int i=0;i<(int)a.size();){
int j=i;
while(j<(int)a.size()&&a[j]==a[i]){
j++;
}
ans=available<2?1:(first+second)%P;
// Newly processed huts have outcomes at least as large as all earlier huts.
if(j-i>=2){
first=second=ans;
}
else{
second=first;
first=ans;
}
available+=j-i;
i=j;
}
cout<<ans<<'\n';
}