Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.lang.c
Subject: Re: OT: CSES Number Spiral algorithm
Date: Thu, 20 Mar 2025 18:02:51 +0000
Organization: Fix this later
Lines: 63
Message-ID: <vrhl8b$3njm0$1@dont-email.me>
References: <vrhgqd$3ku1m$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 20 Mar 2025 19:03:00 +0100 (CET)
Injection-Info: dont-email.me; posting-host="6f460b36cc498e8c1c99eefb8f44e3e6";
	logging-data="3919552"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/rmeWkWl5nLzDasYj208HkBNoTDR6ZSkMnl5dwres8cA=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:w9GCFlSUDwGwtsoRHmq1TIWfqqU=
In-Reply-To: <vrhgqd$3ku1m$2@dont-email.me>
Content-Language: en-GB
Bytes: 2904

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).

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).

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

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within