Minimum Damage on Hexagonal Tiles
National Olympiad — National round (2017 season)
Submission name: damage.cpp
Problem summary
A hexagonal strip has n columns, alternating lengths m and m+1. Passing between neighbouring tiles costs the absolute height difference, and entering or leaving height-zero asphalt costs the absolute boundary-tile height. Find the minimum bottom-to-top damage under the rule that the ride makes no sharp turns.
Source clarification. This 2017 National-round task was shared by Groups C and D; its existing permanent URL is retained. One paragraph misnames the alternating column lengths; the input definition and example confirm m and m+1.
Input
m and n, then the n columns of heights, each listed bottom to top. The first column has m tiles.
Output
The minimum total damage.
Constraints
1 ≤ m,n < 1000; −10^9 ≤ tile height ≤ 10^9.
Worked example
Input and output for the worked example discussed below.
Input
4 3 5 3 -1 2 4 1 3 2 -2 3 6 7 -3
Output
10
Solution analysis
- Treat each tile as a graph vertex and connect its six side-sharing neighbours. Every edge has nonnegative weight |h[u]−h[v]|. A virtual asphalt source reaches each bottom tile at cost |h|; each top tile has an exit cost |h|. Asphalt is not an intermediate free route through the strip.
- A direction state is unnecessary. At a sharp turn A→B→C in a hexagonal grid, A and C are neighbours themselves. Replace the detour by A→C: the triangle inequality shows that damage cannot increase. Repeating this shortening removes all sharp turns. At a boundary, the corresponding shortcut can instead choose a neighbouring entry or exit tile.
- Run Dijkstra, initializing every bottom tile with its entry cost. At the end take the minimum of distance[top]+|height[top]|. In the sample an optimal sequence of heights is 3,1,3,2,2, with total 3+2+2+1+0+2=10.
- Generate adjacency implicitly. A short-column tile at row r touches rows r and r+1 in each adjacent long column. A long-column tile touches rows r and r−1 in adjacent short columns. Both also have vertical neighbours r−1 and r+1 in their own column. Bounds checks discard missing tiles; stride m+1 encodes a tile as column×stride+row.
Why it works
Shortcutting a sharp turn never increases cost and strictly shortens the tile sequence, so an unrestricted shortest path can be converted to a valid ride of no greater cost. Every valid ride is also an unrestricted graph path, hence the optima agree. Dijkstra gives the correct minimum costs because every edge weight is nonnegative; minimizing over final exit costs completes the route.
Watch out. Use hexagonal rather than square-grid neighbours. Include both asphalt costs. Use 64-bit height differences and distances. The source has a variable typo: the alternating column lengths are m and m+1, not n and n+1.
Commented C++17 solution
An independently written complete program with standard headers.
#include<cstdlib>
#include<functional>
#include<iostream>
#include<limits>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m;
int n;
cin>>m>>n;
int stride=m+1;
auto columnLength=[&](int column){
return m+column%2;
};
vector<long long>height(n*stride);
for(int column=0;column<n;column++){
for(int row=0;row<columnLength(column);row++){
cin>>height[column*stride+row];
}
}
const long long infinity=numeric_limits<long long>::max()/4;
vector<long long>distance(n*stride,infinity);
using Entry=pair<long long,int>;
priority_queue<Entry,vector<Entry>,greater<Entry>>pending;
// A virtual asphalt source reaches every bottom tile at its entry cost.
for(int column=0;column<n;column++){
int vertex=column*stride;
distance[vertex]=llabs(height[vertex]);
pending.push({distance[vertex],vertex});
}
while(!pending.empty()){
auto[cost,vertex]=pending.top();
pending.pop();
if(cost!=distance[vertex]){
continue;
}
int column=vertex/stride;
int row=vertex%stride;
auto relax=[&](int nextColumn,int nextRow){
if(nextColumn<0||nextColumn>=n){
return;
}
if(nextRow<0||nextRow>=columnLength(nextColumn)){
return;
}
int next=nextColumn*stride+nextRow;
long long candidate=cost+llabs(height[vertex]-height[next]);
if(candidate<distance[next]){
distance[next]=candidate;
pending.push({candidate,next});
}
};
relax(column,row-1);
relax(column,row+1);
for(int side:{-1,1}){
relax(column+side,row);
relax(column+side,row+(column%2==0?1:-1));
}
}
long long answer=infinity;
for(int column=0;column<n;column++){
int top=column*stride+columnLength(column)-1;
answer=min(answer,distance[top]+llabs(height[top]));
}
cout<<answer<<'\n';
return 0;
}