https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/leaf-and-limelight-attack-circuit/
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
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
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.
1 Like
ok…my bad…thanks a lot…
Great approach…thanks!!!
1 Like