HackerEarth Leaf and Limelight Attack Java Solution

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:

https://www.hackerearth.com/submission/9074081/

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

https://www.hackerearth.com/submission/7229143/

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.

https://www.hackerearth.com/submission/4138095/

1 Like

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

1 Like