dush1729's blog

How to solve Chef and Way using Dynamic Programming?
By dush1729, history, 9 years ago, In English

I am trying to solve this using dynamic programming with complexity of O ( N ^ 2 ) which will give TLE because N <= 10 ^ 5.

Problem Link

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First, store an array b, b[i] = log2(a[i]) to get rid of big numbers.
Now, calculate the following DP:

DP[1]=0

DP[i]=min(DP[j]+b[i]) for all i - k <  = j < i (note that the problem is now changed to addition instead of multiplication becasue log(a * b) = log(a) + log(b)
Store the best path, and calculate the product of all A[i]'s that occur in the path.

You can solve the above DP in O(nlogn) by maintaining a set of the last k DP values.

Code

→ Reply