The Happy Bear
National Olympiad — National round (2011 season)
Submission name: bear.cpp
Problem summary
Hexagonal rooms form a larger regular hexagon of side n, with 2n−1 rows and 3n²−3n+1 rooms. Number rooms left to right, top row to bottom row. Move only to an adjacent room with a larger number. Starting at a and ending at b, maximize rooms visited and count the paths attaining that maximum. If b is unreachable the gain and count are zero.
Input
n a b.
Output
Maximum visited rooms and the number of paths attaining that gain.
Constraints
1 < n < 19; 1 ≤ a < b ≤ 3n²−3n+1. No modulus is specified for the count.
Worked example
An independently prepared example for this explanation.
Input
4 6 13
Output
4 3
Solution analysis
- Represent rooms by axial hex coordinates (q,r), where r increases by row. With s=n−1, row r ranges from q=max(−s,−r−s) through min(s,−r+s). In increasing number order the only forward neighbors are (q+1,r), (q,r+1), and (q−1,r+1).
- The increasing room numbers make a directed acyclic graph. Initialize the start length to 1 and count to 1. For each reachable room extend to its forward neighbors: replace the best length and count on improvement, or add counts on a tie.
- For n=4,a=6,b=13 the longest routes visit four rooms and three routes attain that length. Store path counts as decimal strings with exact addition, since the statement gives no modulus or upper bound on the answer.
Why it works
Axial coordinates generate exactly the six hex neighbors; the three listed directions are exactly those with larger room numbers. Thus numbering is a topological order. Every path to a room ends with one incoming edge, so taking the maximum predecessor length plus one and summing counts precisely over maximizing predecessors computes the optimal length and its exact multiplicity.
Watch out. Count both the starting and ending room. Equal-length updates add counts; longer updates replace them. Decimal-string addition avoids assuming a 64-bit bound absent from the statement.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<map>
#include<string>
#include<utility>
#include<vector>
using namespace std;
string add(string a,string b){
string result;
int i=static_cast<int>(a.size())-1;
int j=static_cast<int>(b.size())-1;
int carry=0;
while(i>=0||j>=0||carry){
int value=carry;
if(i>=0){
value+=a[i--]-'0';
}
if(j>=0){
value+=b[j--]-'0';
}
result.push_back(static_cast<char>('0'+value%10));
carry=value/10;
}
reverse(result.begin(),result.end());
return result;
}
int main(){
// Compute the exact archive answer using the method explained above.
int n,a,b;
cin>>n>>a>>b;
int s=n-1;
vector<pair<int,int>>cells(1);
map<pair<int,int>,int>id;
for(int r=-s;r<=s;r++){
for(int q=max(-s,-r-s);q<=min(s,-r+s);q++){
id[{q,r}]=static_cast<int>(cells.size());
cells.push_back({q,r});
}
}
vector<int>best(cells.size(),0);
vector<string>count(cells.size(),"0");
best[a]=1;
count[a]="1";
const int dq[3]={1,0,-1};
const int dr[3]={0,1,1};
for(int v=a;v<=b;v++){
if(best[v]==0){
continue;
}
auto[q,r]=cells[v];
for(int direction=0;direction<3;direction++){
auto found=id.find({q+dq[direction],r+dr[direction]});
if(found==id.end()){
continue;
}
int u=found->second;
int length=best[v]+1;
if(length>best[u]){
best[u]=length;
count[u]=count[v];
}
else if(length==best[u]){
count[u]=add(count[u],count[v]);
}
}
}
cout<<best[b]<<' '<<count[b]<<'\n';
}