https://www.codingame.com/training/easy/sum-of-spirals-diagonals
Send your feedback or ask for help here!
Created by @wyenat,validated by @HayTheFirst,@Photon and @UnicornP.
If you have any issues, feel free to ping them.
1 Like
Be aware of integer overflow
Hi @wyenat : 
thanks for your contribution ! I’ve done as suggested your puzzle challenge …
→ always so happy when all the validators pass at first submission 
!
Thanks to excel for testcases 
and @HayTheFirst,@Photon, @UnicornP for approval 
.
Have sun, fun and Codingames 
!
In the constraints, you can read :
0 < S < 2^32 - 1
That mean you shouldn’t have a unsigned integer overflow. But yes, one of the test case has an expected result of around 4 billion, which will result in a overflow for 32 bits signed integers.
Seems to be missing a test case for N=1. My solution fails for N=1 but gets 100%.
When I try to make diagonals for 5 I get 1+5+10+14+19+21+24+26+29+30 which is 150 and not 133 so obviously I am doing something wrong but I don’t see another way to make diagonals. What am I missing?
Your series is wrong starting from the 3rd term (10). Also note that it is not possible for numbers bigger than 25 to appear in a spiral of size 5
1 Like
looks like you have a problem with your spiral
corner should be 1 5 9 13 … not 1 5 10 14
3 Likes
Hi guys,
I can’t get a result for test cases 3 and 4 because “the process timed out”. In my code, I use a 2D-Array (without NumPy, just with a list of lists) to form the matrix, then procede to compute the sum. This implies using a for loop inside another for loop resulting in a complexity of O(n^2) (I guess).
It seems it’s not good enough. Can someone give me a clue (not the answer) on how to form the matrix with a better complexity ?
Thanks!
Values in the spiral follow a specific pattern. You can sum the diagonals without going through every number in the spiral.
4 Likes
My first naive Python solution of calculating the spiral matrix (as a nested list) and summing its diagonals got me 100%, so it’s should be a valid way of doing things. Not sure why some people time out trying that.
As for the author, props for making a task involving calculating terms of a sequence that doesn’t so far appear in OEIS. Finding the O(1) solution for this was fun.
You form the matrix, that’s the issue. The last test case is n=1453. That makes you generate over 2 millions numbers. Assuming each of them is a 4 bytes integer, that a 8 Megabyte matrix. Not huge, but overall big enough to timeout, assuming CodingGames lets you storing such a variable.
This puzzle’s inner goal is to teach you that sometimes, generating the whole problem to solve it is not a solution. Just like a question “what is the last digit of 10^10^10^10 ?” would be incredibly hard to answer if you wanted to generate the whole number, but really easy if you gave it some thoughts.
2 Likes
I am trying to get the diagonals by following the numbers of n-1 for the first four and then n-3 for the second four, n-5 for the 3rd etc. until I reach the max number. This works for the first set, but for the second I am off by almost half the total number. Am I thinking in the right direction?
You are thinking in the right direction. You may consider trying the small cases of n, where you can work out the relevant numbers easily, and compare the observed pattern with your code again
2 Likes
Hi,
any math lover like me that got the O(1) solution?
The solution is the sum of n/2 frames (if n odd then add an additional n² in the center),
and every frame is the sum of 4 numbers:
Q1= 1+n+(2n−1)+(3n−2)=6n−2
Q2= (4n−3)+(5n−6)+(6n−9)+(7n−12)=22n−30
Q3= (8n−15)+(9n−20)+(10n−25)+(11n−30)=38n−90
Q4= (12n−35)+(13n−42)+(14n−49)+(15n−56)=54n−182
…
Found the pattern? (the n coefficient grows at 16-constant-step, the other term grows with 32-growing-step (+28,+60,+92,…) )
So, each k-th frame adds to: Qk=(16k−10)n−(16k²−20k+6)
so adding those terms for k=1…n/2, gives:
[nope]
2 Likes
Thanks @nicola to hide the solution from the forum …
→ In order to progress, each one may find his own method to solve the equation !
Have 
sun, fun and CodinGames …
Continuing the discussion from [Community Puzzle] Sum of Spiral's diagonales:
Really good challenge.
Done with alogorithm and then single formula.This text will be hidden
Thanks @wyenat.
1 Like
Hi to all and Congratulations @Argyl :
→ algorithm, equations and formulae are always better than “brute force” !
There is error in task description.
In Example 1:
The sum of the diagonals is:
1 + 3 + 5 + 7 + 9 = 25
But should be
The sum of the diagonals is:
1 + 3 + 5 + 7 + 9 + 9 = 34
That is not an error, that is you changing the original task requirement 
1 Like