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.

ok…my bad…thanks a lot…

Great approach…thanks!!!