Noncrossing Polygonal Paths
National Olympiad — National round
Submission name: lines.cpp
Problem summary
Vertices of a regular n-gon are numbered consecutively from 1 to n. Count the polygonal paths from vertex i to vertex j that use sides or diagonals, never revisit any point, and never self-intersect. A path may omit vertices.
Input
n i j.
Output
The number of paths modulo 1,000,000,007.
Constraints
1 ≤ i < j ≤ n ≤ 1000.
Worked example
An independently prepared example for this explanation.
Input
4 1 3
Output
5
Solution analysis
- Let f(a,b) count paths when the two boundary arcs between the current vertex and the destination contain a and b available vertices. The direct edge contributes one.
- If the next vertex is on the first arc, the edge just drawn discards the vertices before it: entering that region later would require crossing the edge or revisiting its endpoint. The remaining state is f(t,b), for exactly one t from 0 to a−1. The other arc similarly contributes f(a,t).
- Thus f(a,b)=1+sum(t<a)f(t,b)+sum(t<b)f(a,t). Maintain column prefix sums and a running row sum. Return f(j−i−1,n−(j−i)−1).
Why it works
The first edge partitions a convex polygon. Every continuation must stay in the part containing the destination; otherwise it cannot return without an intersection. Conversely every path in that remaining polygon extends safely by this first edge. The cases are disjoint and exhaustive, proving the recurrence.
Watch out. Counting arbitrary simple graph paths is wrong: geometrically crossing edges are forbidden. The direct edge always counts.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The first edge partitions a convex polygon. Every continuation must stay in the part
// containing the destination; otherwise it cannot return without an intersection.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,i,j;
cin>>n>>i>>j;
const long long MOD=1000000007;
int A=j-i-1,B=n-(j-i)-1;
vector<long long>col(B+1);
long long ans=0;
for(int a=0;a<=A;a++){
long long row=0;
for(int b=0;b<=B;b++){
long long f=(1+col[b]+row)%MOD;
col[b]=(col[b]+f)%MOD;
row=(row+f)%MOD;
if(a==A&&b==B){
ans=f;
}
}
}
cout<<ans<<'\n';
}