Number Spiral

Editorial written by Sri Vidya Sundar.

Abridged problem statement

Given a grid with numbers filled in the form of an outward spiral, find the number that is present in the cell $(x,y)$.

Observation

Consider a square from the top left corner to a cell $(a,a)$. This square contains all the numbers from $1$ to $a^2$. For example, a square starting at cell $(1,1)$ and ending at cell $(3,3)$ has values from $1$ to $9$.

Solution

Now let us divide the grid into squares starting from the top left corner.

Once the square of side length $\max(x,y)-1$ has been filled, all numbers up to $(\max(x,y)-1)^2$ have already been used. After this, the spiral fills the next layer in one of two ways:

We use case (i) when the blue square has an odd side length, and case (ii) otherwise.

For simplicity, assume $x \ge y$. Then the already-filled square has side length $x-1$, so the last used number is $(x-1)^2$.

In case (i), we first move $x$ cells down, then move back $x-y$ cells. So the answer is

In case (ii), we move $y$ more cells, so the answer is

The case $y > x$ is symmetric.

Implementation

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  long long t;
  cin >> t;

  while (t--) {
    long long x, y;
    cin >> x >> y;

    if (x > y) {
      if (x % 2 == 1) {
        cout << (x - 1) * (x - 1) + y;
      } else {
        cout << (x - 1) * (x - 1) + 2 * x - y;
      }
    } else {
      if (y % 2 == 0) {
        cout << (y - 1) * (y - 1) + x;
      } else {
        cout << (y - 1) * (y - 1) + 2 * y - x;
      }
    }

    cout << '\n';
  }
}