Count Self-Avoiding Walks in a Quadrant
Autumn Tournament (2014)
Submission name: avoider.cpp
Problem summary
Begin at(0,0), take the first step to(1,0), and then move between lattice neighbours without visiting any point twice or leaving the nonnegative quadrant. Sum the numbers of such walks over lengths a…b.
Source clarification. Offline tabulation is explicitly the intended full solution in the official editorial: https://infos.infosbg.com/files/Contests/ETI/2014/B/analyses/avoider_analysis.pdf . Count data is verified against the official archive. The optional small DFS mode is educational, not the maximum-bound judge algorithm.
Input
Two integers a and b.
Output
The total number of allowed walks of lengths a through b, inclusive.
Constraints
0<a<b<29.
Worked example
Original statement sample.
Input
2 4
Output
19
Solution analysis
- For a fixed length, backtracking marks the current point, tries each unused nonnegative neighbour, and unmarks it on return. Fixing the first step removes rotational choices. For lengths2,3,4 the counts are2,5,12, so the sample sum is19.
- The search tree grows exponentially: this direct method is not fast enough to regenerate length28 during an ordinary judge run. The official editorial explicitly calls for offline tabulation. The complete submission below contains the official verified counts for every permitted length and sums only the requested range.
- The optional --generate mode computes small prefixes independently using the described DFS, making the table’s meaning reproducible for learning. It is capped at12 to prevent accidentally launching a huge computation. The full table is source data from the official archive, not an invented recurrence or a claim that the offline search is constant time.
Why it works
In DFS, a branch specifies exactly one next lattice point; visited-point and coordinate checks reject exactly the forbidden moves. Every legal continuation has one such branch, so the enumeration counts each walk once. The retained table stores these counts for all allowed lengths. Summing its entries over the inclusive interval gives the requested result.
Watch out. Do not count the first step in four directions; it is fixed. Both axes are allowed, but negative coordinates are not. Counts exceed32-bit range. Do not run the exponential generator at the maximum length during a judge submission.
Commented C++17 solution
An independently written complete program with standard headers.
#include<array>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void explore(int x,int y,int steps,int limit,vector<vector<bool>>&used,vector<long long>&count){
count[steps]++;
if(steps==limit){
return;
}
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
for(int direction=0;direction<4;direction++){
int nx=x+dx[direction];
int ny=y+dy[direction];
if(nx>=0&&ny>=0&&nx<=limit&&ny<=limit&&!used[nx][ny]){
used[nx][ny]=true;
explore(nx,ny,steps+1,limit,used,count);
used[nx][ny]=false;
}
}
}
int main(int argc,char**argv){
if(argc==3&&string(argv[1])=="--generate"){
int limit=stoi(argv[2]);
if(limit<1||limit>12){
return 1;
}
vector<vector<bool>>used(limit+1,vector<bool>(limit+1,false));
vector<long long>count(limit+1,0);
used[0][0]=true;
used[1][0]=true;
explore(1,0,1,limit,used,count);
for(int length=1;length<=limit;length++){
cout<<length<<' '<<count[length]<<'\n';
}
return 0;
}
// Exact offline counts for lengths1..28; index0 is an unused dummy.
const array<long long,29>count={0,1,2,5,12,30,73,183,456,1151,2900,7361,18684,47652,
121584,311259,797311,2047384,5260692,13542718,34884239,89991344,232282110,600281932,
1552096361,4017128206LL,10401997092LL,26957667445LL,69892976538LL};
int first,last;
cin>>first>>last;
long long answer=0;
for(int length=first;length<=last;length++){
answer+=count[length];
}
cout<<answer<<'\n';
}