DSA sheet / Introductory
Number Spiral
The problem in brief
The positive integers fill an infinite grid in a spiral pattern that starts at the top-left cell (the statement shows the picture). For each of up to 100 000 queries you get a row y and column x, both up to a billion, and must print the number stored in that cell. Read the official statement for the exact shape of the spiral.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1071.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
You cannot build the grid: it has up to 10^18 cells. You need a formula, so first look for what stays constant along parts of the spiral.
-
Look at the layers. The cells with max(x, y) = k form an L-shape. Which numbers does the k-th L-shape hold, and how many are there?
-
Inside one L-shape the numbers run along it in one direction, and the direction flips between odd and even k. Where does it start and where does it end?
-
Decide which arm of the L your cell is on (the row arm or the column arm), then count its distance from an end whose value you know.
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
When the input is too large to simulate, write out a small grid by hand (say 5 by 5) and stare at it until you see the structure. Here the structure is “nested L-shapes”: the first k layers together fill exactly the top-left k by k square, so they hold the numbers 1 to k^2. Layer k therefore holds (k-1)^2 + 1 up to k^2, a run of 2k - 1 consecutive numbers.
Once you know the range of a layer, everything reduces to “where in the run is my cell?”. The direction alternation (odd layers run one way, even layers the other) is the only annoying part; handle it with a parity check and verify against your small hand grid.
The habit: turn a picture into arithmetic by finding the level sets of the picture (here max(x, y)), then solve a one-dimensional indexing problem inside a level.
Intuition
The spiral is a snail shell growing outward. Every time the shell finishes a full k by k square, the next number written is k^2 + 1, which starts the next L-shape. Each L is walked from one end to the other, and which end it starts from alternates from layer to layer.
Approach
Let m = max(x, y) be the layer.
- If the cell is on the row arm (y is at least x, so the row y = m): for odd m the value is (m-1)^2 + x; for even m it is m^2 - x + 1.
- Otherwise the cell is on the column arm (x = m, y less than x): for even m the value is (m-1)^2 + y; for odd m it is m^2 - y + 1.
Test it on a small grid you build by simulation before trusting it: check the corner cells and the first row and column.
Pitfalls: m^2 reaches 10^18, which fits in a signed 64-bit integer but not in a JavaScript double, so use BigInt there; C++ and Java need long long / long.
Complexity
O(1) per query, so O(t) overall. Read all queries quickly and print with one buffered write.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
long long y, x;
cin >> y >> x;
long long m = max(x, y), ans;
if (y >= x) {
ans = (m % 2 == 1) ? (m - 1) * (m - 1) + x : m * m - x + 1;
} else {
ans = (m % 2 == 0) ? (m - 1) * (m - 1) + y : m * m - y + 1;
}
cout << ans << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.read().split()
t = int(data[0])
out = []
for i in range(t):
y = int(data[1 + 2 * i])
x = int(data[2 + 2 * i])
m = max(x, y)
if y >= x:
ans = (m - 1) ** 2 + x if m % 2 == 1 else m * m - x + 1
else:
ans = (m - 1) ** 2 + y if m % 2 == 0 else m * m - y + 1
out.append(ans)
print("\n".join(map(str, out)))
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(in.readLine().trim());
StringBuilder sb = new StringBuilder();
while (t-- > 0) {
StringTokenizer st = new StringTokenizer(in.readLine());
long y = Long.parseLong(st.nextToken());
long x = Long.parseLong(st.nextToken());
long m = Math.max(x, y), ans;
if (y >= x) {
ans = (m % 2 == 1) ? (m - 1) * (m - 1) + x : m * m - x + 1;
} else {
ans = (m % 2 == 0) ? (m - 1) * (m - 1) + y : m * m - y + 1;
}
sb.append(ans).append('\n');
}
System.out.print(sb);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean);
const t = Number(data[0]);
const out = [];
for (let i = 0; i < t; i++) {
// BigInt: m * m reaches 10^18, beyond the 2^53 range where doubles are exact.
const y = BigInt(data[1 + 2 * i]);
const x = BigInt(data[2 + 2 * i]);
const m = x > y ? x : y;
let ans;
if (y >= x) {
ans = m % 2n === 1n ? (m - 1n) * (m - 1n) + x : m * m - x + 1n;
} else {
ans = m % 2n === 0n ? (m - 1n) * (m - 1n) + y : m * m - y + 1n;
}
out.push(ans.toString());
}
console.log(out.join('\n'));Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).