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

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!!!