Compress the Garbage
National Olympiad — National round (2015 season)
Submission name: garbage.cpp
Problem summary
Repeatedly remove a boundary row or boundary column of a digit matrix, paying the maximum digit on that boundary. Minimize the total cost to remove all cells.
Input
N M and the N×M matrix.
Output
Minimum total compression cost.
Constraints
1 ≤ N,M ≤ 100; 0 ≤ cell ≤ 9.
Worked example
An independently prepared example for this explanation.
Input
3 4 6 8 7 2 3 0 9 1 4 2 9 1
Output
24
Solution analysis
- After any sequence of presses, remaining cells form one axis aligned subrectangle. Let dp[top,bottom,left,right] be the optimal cost of clearing it. The next press removes exactly one of its four boundary sides.
- Precompute every row interval maximum and every column interval maximum. Each state takes the minimum of four smaller-rectangle values plus its corresponding boundary maximum. Evaluate row heights and column widths in increasing order, so all dependencies are ready.
- In the sample, remove top row for 8, right column for 1, another right column for 9, left column for 4, and the final boundary for 2: total 24. Compress row and column interval indices and store costs as unsigned short; even removing every row costs at most 900.
Why it works
Every legal first press is one of the four transitions. After paying it, the remaining problem is exactly the corresponding smaller rectangle. Thus every complete strategy has cost at least one recurrence candidate. Conversely, a chosen boundary press followed by an optimal smaller strategy attains that candidate. Induction on rectangle size proves the recurrence optimal.
Watch out. The boundary maximum is taken only over the currently remaining row or column interval. Empty rectangles cost zero. A full four-dimensional 100⁴ allocation wastes nearly four times the interval-compressed storage.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstddef>
// Algorithm: After any sequence of presses, remaining cells form one axis aligned subrectangle.
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>>a(n,vector<int>(m));
for(auto&row:a){
for(int&value:row){
cin>>value;
}
}
vector<vector<int>>rowId(n,vector<int>(n)),colId(m,vector<int>(m));
int rows=0,columns=0;
for(int top=0;top<n;++top){
for(int bottom=top;bottom<n;++bottom){
rowId[top][bottom]=rows++;
}
}
for(int left=0;left<m;++left){
for(int right=left;right<m;++right){
colId[left][right]=columns++;
}
}
vector<vector<int>>rowMax(n,vector<int>(columns)),colMax(m,vector<int>(rows));
for(int top=0;top<n;++top){
for(int left=0;left<m;++left){
int maximum=0;
for(int right=left;right<m;++right){
maximum=max(maximum,a[top][right]);
rowMax[top][colId[left][right]]=maximum;
}
}
}
for(int left=0;left<m;++left){
for(int top=0;top<n;++top){
int maximum=0;
for(int bottom=top;bottom<n;++bottom){
maximum=max(maximum,a[bottom][left]);
colMax[left][rowId[top][bottom]]=maximum;
}
}
}
vector<unsigned short>dp(static_cast<size_t>(rows)*columns,0);
auto get=[&](int top,int bottom,int left,int right)->int{
if(top>bottom||left>right){
return 0;
}
return dp[static_cast<size_t>(rowId[top][bottom])*columns+colId[left][right]];
};
for(int height=1;height<=n;++height){
for(int width=1;width<=m;++width){
for(int top=0;top+height<=n;++top){
int bottom=top+height-1;
for(int left=0;left+width<=m;++left){
int right=left+width-1;
int ri=rowId[top][bottom],ci=colId[left][right];
int best=min(get(top+1,bottom,left,right)+rowMax[top][ci],
get(top,bottom-1,left,right)+rowMax[bottom][ci]);
best=min(best,get(top,bottom,left+1,right)+colMax[left][ri]);
best=min(best,get(top,bottom,left,right-1)+colMax[right][ri]);
dp[static_cast<size_t>(ri)*columns+ci]=static_cast<unsigned short>(best);
}
}
}
}
cout<<get(0,n-1,0,m-1)<<'\n';
}