Snowboard Routes with Exactly P Flags
Autumn Tournament (2017)
Submission name: snowboard.cpp
Problem summary
The tilted rectangular course has N rows and M flags per row. From the top corner to the bottom corner, move one step along a row or to either nearest lower-row neighbor. In grid coordinates these are (r,c+1), (r+1,c), (r+1,c+1). Count routes visiting exactly P flags, including both endpoints, modulo 2^62.
Input
N M P.
Output
The route count modulo 2^62.
Constraints
0 < N ≤ M ≤ 200; 0 < P < N+M.
Worked example
Original statement sample.
Input
3 4 5
Output
12
Solution analysis
- The figure is a rectangular grid tilted downhill. Label the top flag (0,0) and bottom flag (N−1,M−1). The three permitted moves increase the column, the row, or both. A route never returns to a previous flag.
- Let dp[r][c] count routes with the current number of visited flags ending at (r,c). Start with dp[0][0]=1 for one visited flag. For each extra flag, create a fresh array and add the values from the three possible predecessor cells. Using a fresh array prevents mixing different route lengths.
- For N=3,M=4,P=5, four moves must increase the row twice and column three times. There must be one diagonal move, one row-only move and two column-only moves. Their order can be chosen in 4!/(1!·1!·2!)=12 ways. The same course gives 3 routes for P=4 and 10 for P=6.
Why it works
Every non-start state has exactly one last move of the three listed types. Removing it gives a route with one fewer visited flag to the corresponding predecessor. The recurrence therefore counts every route exactly once. Modular reduction preserves the required remainder.
Watch out. P counts flags rather than moves. The modulus is 2^62, not 262; PDF extraction may lose superscripts. Do not use signed overflow when adding residues.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int rows;
int columns;
int flags;
cin>>rows>>columns>>flags;
const unsigned long long mask=(1ULL<<62)-1;
vector<vector<unsigned long long>>previous(rows,vector<unsigned long long>(columns,0));
previous[0][0]=1;
for(int used=2;used<=flags;used++){
vector<vector<unsigned long long>>current(rows,vector<unsigned long long>(columns,0));
for(int row=0;row<rows;row++){
for(int column=0;column<columns;column++){
unsigned long long ways=0;
if(row>0){
ways+=previous[row-1][column];
}
if(column>0){
ways+=previous[row][column-1];
}
if(row>0&&column>0){
ways+=previous[row-1][column-1];
}
// Bit masking is reduction modulo a power of two.
current[row][column]=ways&mask;
}
}
previous.swap(current);
}
cout<<previous[rows-1][columns-1]<<'\n';
}