SNAKE - Editorial

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Aayush Agarwal
Tester: Aayush Agarwal
Editorialist: Aakash Jain

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

Elementary Maths

PROBLEM:

Form an NxN matrix following the given snaking pattern starting at the bottom left (example for 4x4):

7 13 14 16
6  8 12 15
2  5  9 11
1  3  4 10

Report the value at (X, Y).

QUICK EXPLANATION:

Divide the matrix along the principal diagonal. First fill the bottom half along the diagonals, changing the limits appropriately for each diagonal. Use a flag variable to indicate the direction in which the diagonal is to be filled, and flip it after each diagonal. Repeat the process for the upper half of the matrix.

EXPLANATION:

We can divide the problem into two loops, each filling one half of the NxN matrix. We divide a 4x4 matrix as follows:

x o o o
x x o o
x x x o
x x x x

The halves will be filled diagonally. We will be needing the following variables for our task:

  • A counter that tells us the value to be stored at each place in the matrix.
  • A flag variable that we flip after filling each diagonal. Its value tells us the direction in which to fill the current diagonal.
  • The top and bottom row numbers for the current diagonal.
  • The leftmost and rightmost column numbers for the current diagonal.

First we will fill the lower half, starting at the bottom right. For this, we initialize our variables as follows:

value = 1
direction = 1
rowTop = rowBottom = N-1
colLeft = colRight = 0

For each successive diagonal, you will find that we have to decrement rowTop and increment colRight. We also have to flip direction (this can be done by XORing it with 1). To fill each diagonal, we check the value of direction. If it is 1, we fill the diagonal from bottom to top (equivalently, right to left). If it is 0, we fill from top to bottom (equivalently, left to right).
Pseudo-code:

while rowTop >= 0
    if direction == 0
        i = rowTop
        j = colLeft
    while i <= rowBottom
        matrix[i][j] = value++
            i++
            j++
    else
        i = rowBottom
        j = colRight
        while i >= rowTop
            matrix[i][j] = value++
            i--
            j--
    rowTop--
    colRight++
    direction ^= 1

We have now filled the lower half of the matrix. Next, we will be starting with the lowest diagonal of the top half and moving to the top right. This is similar to what we did for the lower half, with some changes.
Pseudo-code:

rowTop = 0
rowBottom = N-2
colLeft = 1
colRight = N-1
while rowBottom >= 0
    if direction == 0
        i = rowTop
        j = colLeft
        while i <= rowBottom
            matrix[i][j] = value++
            i++
            j++
    else
        i = rowBottom
        j = colRight
        while i >= rowTop
            matrix[i][j] = value++
            i--
            j--
    rowBottom--
    colLeft++
    direction ^= 1

We have now filled the matrix and simply have to return matrix[X][Y]. Optionally, we could return our value as soon as the value at matrix[X][Y] is filled, instead of filling the entire matrix first.

AUTHOR’S SOLUTION:

Author’s solution can be found here.