vatsalseth33's blog

By vatsalseth33, history, 4 years ago, In English

Problem — Link
Editorial — Link
Should'nt the solution be dp[i] = sum(dp[j]*dp[i-j]) for j=3 to i-3 where i is the required sum for the iteration ? My reasoning is that when ever we use a sequence of sum j (whose count is dp[j]) then we can append another sequence of sum i-j to it to make total sum i. The editorial says to find dp[i] we just find sum(dp[j]) for j=i-3 to 0. Can someone explain how?

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

By vatsalseth33, history, 4 years ago, In English

Problem : Given an array A of integers,you can remove some elements as per your wish without changing the order of the remaining elements. After removing, value of A becomes sum(i*A[i]) from i = 1 to K(new size of A). Find maximum value of A possible after modification.

Example:
A = [-1,-9,0,5,-7]

Answer = 14 (remove -9 and -7 so value = -1*1 + 0*2 + 5*3)
I feel it is dp but cannot visualise it. Can anyone please help me out here?

Full text and comments »

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