Re: OT: CSES Number Spiral algorithm

On 3/20/2025 2:02 PM, Richard Heathfield wrote:

On 20/03/2025 16:47, DFS wrote:

I don't have a C question, but rather I'd like input about algorithmic approaches.
>
https://cses.fi/problemset/task/1071
>
It's an 'infinite grid'.  You have to find the value at rows-columns from 1 to 10^9.
>
First thing you notice about the 5x5 grid is the values in odd-numbered columns begin with the square of the column number, and the values in even-numbered rows begin with the square of the row number.
>
I followed the number pattern and built a grid in Excel and expanded it to 10x10 for more testing.
>
https://imgur.com/x4VymmA
>
Then coded 4 conditions      solution
1. row <= col and col odd    (col * col) - row + 1
2. row <= col and col even   ((col-1) * (col-1)) + row
3. row >  col and row odd    ((row-1) * (row-1)) + col
4. row >  col and row even   (row * row) - col + 1
>
My full C code submission was accepted the first time.
>
How would you have done it?

  I see that you've already solved it, so that's good.
 My first observation was the main diagonal, which goes:
 1 3 7 13 21...
>
Differences are 2 4 6 8... respectively
 Consider the triangle numbers (n(n+1)/2):
 0 1 3 6 10 15 21 28...
 Double and add 1:
 1 3 7 13 21 31...
 So the main diagonal is readily calculable - either (row, row) or (col, col).

Even easier when row=column is: r^2-(r-1), or if you prefer: (r^2-r)+1
I just now noticed that.
After my code was accepted I looked online at other solutions, and most were similar to mine: 4 conditions/formulas.
But I wouldn't doubt it can be done shorter/more efficiently.

I'd then have picked the biggest out of (row, col) and calculated its triangle number: n(n+1)/2, doubled (so don't divide) and add 1, for (n(n+1))+1 and then either added the column or subtracted the row (whichever of them is smaller).

Let's try that:
refer to https://imgur.com/x4VymmA
row 8, col 7
value at 8,7 is 58
your method (as I understand it)
8(8+1) + 1 - 7 = 66
Did I mess it up?

Reviewing your solution after the fact, I don't see the need to
distinguish between odd and even. What did I miss?

The number patters are different:
- Odd rows increase at all times
- Even rows decrease until they hit the matching # column, then start
   increasing
- Odd columns decrease until they hit the matching # row, then start
   increasing
- Even columns increase at all times
The pattern is called a spiral by CSES, but the numbers don't follow a spiral at all.
https://ramandeepsingh.hashnode.dev/number-spiral