jsaita96's blog

By jsaita96, history, 8 years ago, In English

While practicing DP problems on various sites, I came across this problem:- https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/leaf-and-limelight-attack-circuit/description/ on HackerEarth.

According to the editorial, we pre-process the values in the solution. Queries are divided into even and odd. DP[i] gives the solution for ith query. So, DP[1] = 1, DP[3] = 25, DP[5] = 101.

So, they have derived a formula which is :-

DP[i] = DP[i-2] + (i-2)2 + (i-1) + (i-2)2 + 2(i-1) + (i-2)2 + 3(i-1) + (i-2)2 + 4(i-1) which gets reduced to

DP[i] = DP[i-2] + 4i2 — 6*(i-1)

So my question is, how was this formula derived? What was the approach in deriving this ?

Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

If you already know the value of DP[i], then you can easily calculate the value of DP[i + 2].

The last number of an i * i square will be i2 and it will be located in a corner. To expand the square, you will make i - 1 steps to the next corner, then another i - 1 steps to the next one, and so on, so you can express DP[i + 2] = DP[i] + i2 + i - 1 + i2 + 2(i - 1) + i2 + 3(i - 1) + i2 + 4(i - 1) = DP[i] + 4i2 + 10(i - 1).

The formula is different because I calculated i + 2 from i instead of calculating i from i - 2, but it's the same principle.