Number Spiral
For each grid coordinate, compute the value stored there in the square spiral without simulating the whole grid.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
For each query \((y, x)\), determine which number appears at that cell in the square number spiral. The coordinates can be large, so filling the whole grid is not an option.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
The spiral is organized in square layers. For a cell \((y, x)\), the relevant layer is \[ L = \max(y, x). \]
That layer ends at either \(L^2\) or \((L - 1)^2 + 1\), depending on the parity of \(L\) and whether the cell lies on the bottom edge or the right edge.
The clean way to reason about it is to split into two cases:
if \(y > x\), the cell lies on the row where layer \(y\) finishes
otherwise, the cell lies on the column where layer \(x\) finishes
Then parity tells us which direction that layer was traversed.
If \(y > x\):
when \(y\) is odd, the row grows left-to-right, so the answer is \((y - 1)^2 + x\)
when \(y\) is even, the row grows right-to-left, so the answer is \(y^2 - x + 1\)
If \(x \ge y\):
when \(x\) is even, the column grows top-to-bottom, so the answer is \((x - 1)^2 + y\)
when \(x\) is odd, the column grows bottom-to-top, so the answer is \(x^2 - y + 1\)
That gives an \(O(1)\) formula per query.
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(1)\) per query
Memory: \(O(1)\)
C++ Solution
The exact repository source used for this solution page.
#include <cstdint>
#include <iostream>
int main() {
int t;
std::cin >> t;
while (t--) {
std::int64_t y, x;
std::cin >> y >> x;
std::int64_t answer;
if (y > x) {
if (y % 2 == 1) {
answer = (y - 1) * (y - 1) + x;
} else {
answer = y * y - x + 1;
}
} else {
if (x % 2 == 0) {
answer = (x - 1) * (x - 1) + y;
} else {
answer = x * x - y + 1;
}
}
std::cout << answer << '\n';
}
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
The coordinates can be large enough that the computed values need 64-bit integers.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.