What is the logic behind and approach for this piece of code?

Question

You have to visit all cells is n*m grid, you can only visit each cell only once and you have to visit them is such a way such that when moving from one cell to another cell, the vector(mathematically speaking) (i.e. ordered_pair(dx,dy)) is never used again for any other moves. There could be other solutions as well but I am particularly interested in why this solution works. This question is from codeforces https://codeforces.com/contest/1180/problem/D

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n,m;
    cin>>n>>m;
    int st=0,end=n*m-1;
    for(int i=0;i<n*m;i++) {
        if(i%2==0) {
             cout<<st/m+1<<' '<<st%m+1<<endl;
             st++;
        }
        else {
            cout<<end/m+1<<' '<<end%m+1<<endl;
            end--;
        }
    }
}

[Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — Evg, Jun 23 '19 at 13:52
It jumps from top-left cell to bottom-right, then back to top-second-from-left, then down again to bottom-second-from-right, and so on, jumping up and down between two sequences. Proving that this never repeats the delta is left as an exercise for the reader. — Igor Tandetnik, Jun 23 '19 at 14:04

score 2 · Answer 1 · edited Jun 29 '19 at 07:22

The algorithm cycles between the first and last yet to be entered cell in some ordering of the grid. We need 2 pieces to show why it works:

First off, we note that for the typical ways to order such a grid (row or column major), any vector is uniquely identified by the length of its step in the ordering (with the major and minor part being effectively the divisor and remainder of the length of the respective side, and these 2 parts are independent of each other).

Second off, we have the length of the steps in the ordering is monotonically decreasing, since we decrease the amount of possible ordering values it can move each step, as we remove the further-most point it could have went to.

When we combine this, we get that all the moves must be different, since each move has a different length in the ordering, and different length steps have unique vector movements.

Note that since there is also a sign on the moves, and that also constitutes a different vector, and that we have taken all the ordering lengths, we have that we have used up exactly half of all the possible move-vectors (the other half being the reverse movement), and we can from this prove that all move-sets that satisfy the problem must also have this property.

score 0 · Accepted Answer · answered Jun 23 '19 at 14:10

Consider if it were a 1D array. The equivalent 1D algorithm would start at the first cell, jump forward to the last cell, backward to the second cell, forward to the second-to-last cell, backward to the third cell, and so on until the jumps took it to the middle. Since each forward jump is smaller than the last one, and the same is true of each backwards jump, each jump has a different displacement.

The 2D version is just a nested version of that. First it visits the first and last rows (as defined by X coordinate); then it visits the second and second-to-last rows; and so on. Within each row it uses the 1D algorithm.

What is the logic behind and approach for this piece of code?

2 Answers2