I know how to solve this, but I am getting a TLE for large test cases. Can anyone help out? Here’s my solution:
Hey this can be solved by precomputing and answering each query in O(1).see my code and comment if you have any doubt.
here is my code
You can also solve this in O(1) per query without any pre-computation at all. Observe the pattern.
Let N = Even (Say 4), the spiral looks like this
16 15 14 13
5 4 3 12
6 1 2 11
7 8 9 10
Let D1 be the diagonal from top-right to bottom-left and D2 be the diagonal from top-left to bottom-right.
D1 = 1 + 3 + 7 + 13
= (1^2 - 0) + (2^2 -1) + (3^2 - 2) + (4^2 - 3)
= (1^2 + 2^2 + 3^2 + 4^2) - (1 + 2 + 3)
= SUM(N^2) - SUM(N-1)
D2 = 2 + 4 + 10 + 16
= (1^2 + 1) + (2^2 + 0) + (3^2 + 1) + (4^2 + 0)
= (1^2 + 2^2 + 3^2 + 4^2) + (N/2 times 1)
= SUM(N^2) + N/2
Therefore, answer = D1 + D2
Let N = Odd (Say 5), the spiral looks like this
17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23 24 25
D1 = 1 + 3 + 7 + 13 + 21
= (1^2 - 0) + (2^2 -1) + (3^2 - 2) + (4^2 - 3) + (5^2 - 4)
= (1^2 + 2^2 + 3^2 + 4^2 + 5^2) - (1 + 2 + 3 + 4)
= SUM(N^2) - SUM(N-1)
D2 = 1 + 5 + 9 + 17 + 25
= (1^2 + 0) + (2^2 + 1) + (3^2 + 0) + (4^2 + 1) + (5^2 + 0)
= (1^2 + 2^2 + 3^2 + 4^2 + 5^2) + ( (N-1)/2 times 1 )
= SUM(N^2) + (N-1)/2
Therefore, answer = D1 + D2 - 1 (because we have counted ‘1’ 2 times)
You can have a look at my solution in the following link.
Ya I used dynamic programming and inspite of doing everything , 6 test cases give a TLE. Look at my solution first, I did the same thing.
yeah i have seen your submission.Instead of calculating answer every time for n,calculate answers for all numbers upto 10^7 and store them.Now you can answer each query in O(1).see my submission if you have any doubt
ok…my bad…thanks a lot…
Great approach…thanks!!!