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 don't have a C question, but rather I'd like input about algorithmic approaches.
https://cses.fi/problemset/task/1071
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?
DFS <nospam@dfs.com> writes:
My full C code submission was accepted the first time.
How would you have done it?
This posting is not appropriate for comp.lang.c. Putting "OT" in
the subject line doesn't excuse its lack of suitability.
On 20/03/2025 18:38, Tim Rentsch wrote:
DFS <nospam@dfs.com> writes:
<snip>
My full C code submission was accepted the first time.
How would you have done it?
This posting is not appropriate for comp.lang.c. Putting "OT" in
the subject line doesn't excuse its lack of suitability.
You're right, of course, but would it have hurt so very much to point
the OP towards comp.programming?
This posting is not appropriate for comp.lang.c. Putting "OT" in
the subject line doesn't excuse its lack of suitability.
On 3/20/2025 2:38 PM, Tim Rentsch wrote:
This posting is not appropriate for comp.lang.c. Putting "OT" in
the subject line doesn't excuse its lack of suitability.
Aren't you too old to be a net-nanny?
DFS <nospam@dfs.com> writes:
On 3/20/2025 2:38 PM, Tim Rentsch wrote:
This posting is not appropriate for comp.lang.c. Putting "OT" in
the subject line doesn't excuse its lack of suitability.
Aren't you too old to be a net-nanny?
I see now why you are having difficulties doing these
simple programming exercises.
DFS <nospam@dfs.com> writes:
On 3/20/2025 2:38 PM, Tim Rentsch wrote:
This posting is not appropriate for comp.lang.c. Putting "OT" in
the subject line doesn't excuse its lack of suitability.
Aren't you too old to be a net-nanny?
I see now why you are having difficulties doing these
simple programming exercises.
Richard Heathfield <rjh@cpax.org.uk> writes:
On 20/03/2025 18:38, Tim Rentsch wrote:
DFS <nospam@dfs.com> writes:
<snip>
My full C code submission was accepted the first time.
How would you have done it?
This posting is not appropriate for comp.lang.c. Putting "OT" in
the subject line doesn't excuse its lack of suitability.
You're right, of course, but would it have hurt so very much to point
the OP towards comp.programming?
An oversight on my part. Thank you for chiming in.
On 20/03/2025 20:10, Tim Rentsch wrote:
Richard Heathfield <rjh@cpax.org.uk> writes:
On 20/03/2025 18:38, Tim Rentsch wrote:
DFS <nospam@dfs.com> writes:
<snip>
My full C code submission was accepted the first time.
How would you have done it?
This posting is not appropriate for comp.lang.c. Putting "OT" in
the subject line doesn't excuse its lack of suitability.
You're right, of course, but would it have hurt so very much to point
the OP towards comp.programming?
An oversight on my part. Thank you for chiming in.
His questions were tailor-made for comp.programming, but it turns out
he's just another toy-thrower, so it matters not.
On 2025-03-20, DFS <nospam@dfs.com> wrote:
I don't have a C question, but rather I'd like input about algorithmic
approaches.
https://cses.fi/problemset/task/1071
> Time limit: 1.00 s Memory limit: 512 MB
Is that just for the solution itself?
If I deploy a Kubernetes cluster, with seven different versions of
Fedora and Debian sporting thousands of packages running in different containers, does all that count toward these limits?
Or just the small end program I will end up runnig in the end?
In any case, I could put it into a Docker image that has been staged and optimized to just contain that binary and its minimal dependencies ...
... haha! I looked years younger there for a second, didn't I!
On 3/20/2025 2:32 PM, Kaz Kylheku wrote:
On 2025-03-20, DFS <nospam@dfs.com> wrote:
I don't have a C question, but rather I'd like input about algorithmic
approaches.
https://cses.fi/problemset/task/1071
> Time limit: 1.00 s Memory limit: 512 MB
Is that just for the solution itself?
If I deploy a Kubernetes cluster, with seven different versions of
Fedora and Debian sporting thousands of packages running in different
containers, does all that count toward these limits?
Or just the small end program I will end up runnig in the end?
In any case, I could put it into a Docker image that has been staged and
optimized to just contain that binary and its minimal dependencies ...
... haha! I looked years younger there for a second, didn't I!
heh!
Were you wearing skinny jeans when you wrote it?
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?
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:
The pattern is called a spiral by CSES, but the numbers don't
follow a spiral at all.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 546 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 146:31:43 |
| Calls: | 10,383 |
| Calls today: | 8 |
| Files: | 14,054 |
| D/L today: |
2 files (1,861K bytes) |
| Messages: | 6,417,708 |