Spiral Walk Queries
National Olympiad — Regional round (2024 season)
Submission name: spwalks.cpp
Problem summary
A walk starts at a grid cell and repeatedly jumps to the nearest strictly smaller value in the next direction, cycling up, right, down, left. It stops when no such cell exists. A jump is big if its value decreases by at least K. For each starting cell and positive l, report the cell reached immediately after its l-th big jump, or 0 0 if that jump never occurs.
Input
M N K; M rows of N values; Q; then Q triples r c l, with coordinates starting at 1.
Output
For each query, the target row and column, or 0 0.
Constraints
1 ≤ MN ≤ 10⁶; 1 ≤ K,Q ≤ 10⁶; cell values are in [1,10⁹]; 1 ≤ l ≤ MN.
Worked example
An independently prepared example for this explanation.
Input
5 4 3 5 4 7 3 16 18 17 15 15 20 30 25 9 14 15 10 1 2 1 2 4 3 2 1 3 3 3 4 3 2 4 3 7
Output
1 2 1 1 1 4 0 0
Solution analysis
- The next cell depends on both the current cell and the direction due next. Represent these four possibilities as separate states. Four monotone-stack sweeps find the nearest strictly smaller cell in each direction in linear time. Pop values greater than or equal to the current value so equal entries never become destinations.
- Every transition strictly decreases the cell value, so states form an acyclic successor graph. Process cells in increasing value order. If a transition is big, keep its destination state as the first-big successor. If it is small, replace it by the already computed first-big successor of its destination. A missing transition stays missing. This skips all small jumps while preserving the exact state immediately after a big jump.
- Build binary-lifting tables on the first-big successors. A query starts in the up state and follows l such successors using the set bits of l. In the example the walk from (3,2), value 20, first moves upward to value 18, then right to 17, then down to 15. The first two drops are small; the walk eventually makes its first big drop to (1,2), which is the first answer.
Why it works
A monotone stack discards only cells blocked by a nearer cell with no greater value, so its remaining top is precisely the nearest strictly smaller candidate. The first-big recurrence is correct by induction on increasing value: a big edge ends the desired prefix, while a small edge leaves the same first big jump to be found from its successor. Lifting composes this exact successor 2^j times at level j. Applying the binary expansion of l therefore reaches precisely the l-th big-jump destination, or detects that it does not exist.
Watch out. Include the next direction in a state. Equality is not a legal smaller value. Return immediately after the big jump, before any subsequent small jumps. Use a missing-state sentinel throughout lifting.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int rows,columns,threshold;
cin>>rows>>columns>>threshold;
int cells=rows*columns;
vector<int>value(cells);
for(int&entry:value){
cin>>entry;
}
vector<int>first(4*cells,-1),stack;
auto process=[&](int cell,int direction){
while(!stack.empty()&&value[stack.back()]>=value[cell]){
stack.pop_back();
}
if(!stack.empty()){
first[4*cell+direction]=4*stack.back()+(direction+1)%4;
}
stack.push_back(cell);
};
for(int column=0;column<columns;++column){
stack.clear();
for(int row=0;row<rows;++row){
process(row*columns+column,0);
}
stack.clear();
for(int row=rows-1;row>=0;--row){
process(row*columns+column,2);
}
}
for(int row=0;row<rows;++row){
stack.clear();
for(int column=columns-1;column>=0;--column){
process(row*columns+column,1);
}
stack.clear();
for(int column=0;column<columns;++column){
process(row*columns+column,3);
}
}
vector<int>order(cells);
iota(order.begin(),order.end(),0);
sort(order.begin(),order.end(),[&](int a,int b){
return value[a]<value[b];
});
for(int cell:order){
for(int direction=0;direction<4;++direction){
int state=4*cell+direction;
int destination=first[state];
if(destination!=-1&&value[cell]-value[destination/4]<threshold){
// Smaller-valued destination states have already been compressed.
first[state]=first[destination];
}
}
}
int levels=1;
while((1<<levels)<=cells){
++levels;
}
vector<vector<int>>jump;
jump.push_back(move(first));
for(int level=1;level<levels;++level){
jump.emplace_back(4*cells,-1);
for(int state=0;state<4*cells;++state){
int middle=jump[level-1][state];
if(middle!=-1){
jump[level][state]=jump[level-1][middle];
}
}
}
int queries;
cin>>queries;
while(queries--){
int row,column,count;
cin>>row>>column>>count;
int state=4*((row-1)*columns+column-1);
for(int level=0;level<levels&&state!=-1;++level){
if((count>>level)&1){
state=jump[level][state];
}
}
if(state==-1){
cout<<"0 0\n";
}
else{
int cell=state/4;
cout<<cell/columns+1<<' '<<cell%columns+1<<'\n';
}
}
}