Minimum and Maximum Adjacent-Cell Sums
National Olympiad — Municipal round (2025 season)
Submission name: minmax.cpp
Problem summary
Find the minimum and maximum sum among all cell pairs sharing a side.
Input
m n and an m×n integer table.
Output
Minimum and maximum pair sums.
Constraints
1<m,n<100; entries are positive and below 1000.
Worked example
Input and output for the worked example discussed below.
Input
3 4 1 2 3 4 8 5 6 8 1 2 5 7
Output
3 15
Solution analysis
- Valid pairs are horizontal or vertical neighbours; diagonal cells do not qualify.
- From each cell inspect only its right and lower neighbour when present. This enumerates each unordered side-neighbour pair exactly once, updating both extrema.
- The sample minimum is 1+2=3. The maximum is the vertical pair 8+7=15 in the final column, demonstrating why both directions matter.
Why it works
Each valid pair has exactly one left or upper endpoint. The scan therefore visits precisely the required pairs, and extrema over that complete set give the result.
Complexity: O(mn) time and O(mn) space.
Watch out. Initialize extremes outside the possible sums. Check neighbour bounds and do not include diagonals.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
int m;
int n;
cin>>m>>n;
vector<vector<int>>grid(m,vector<int>(n));
for(auto&row:grid){
for(int&value:row){
cin>>value;
}
}
int low=numeric_limits<int>::max();
int high=numeric_limits<int>::min();
for(int row=0;row<m;row++){
for(int column=0;column<n;column++){
// Right and down enumerate each required pair once.
if(column+1<n){
int sum=grid[row][column]+grid[row][column+1];
low=min(low,sum);
high=max(high,sum);
}
if(row+1<m){
int sum=grid[row][column]+grid[row+1][column];
low=min(low,sum);
high=max(high,sum);
}
}
}
cout<<low<<' '<<high<<'\n';
}