Hey, in this problem suppose we are calculating min cost for 10 cells. Then it would be min(min_cost(5)+x,min_cost(9)+y,min_cost(11)+z), so we need to know min_cost(11) which would be min(min_cost(10)+y,min_cost(12)+z), but already min_cost(10) was dependent on min_cost(11). Also, for min_cost(11) we should know min_cost(12), and then for min_cost(12) we should know min_cost(13) and so on, this would keep on increasing, there would not be any end to it. At first i thought the x<=y<=z constraint would come to play somehow but in the example x = 2 and y = 1, so that constraint is also being violated. Is this question correct, if yes please give some hint about it.
Is the question correct
@Akhil098 Let’s define dp[i] as minimum cost to make i number of cells. Then we could write the following recurrence: if i is even dp[i]= min(dp[i/2]+x,dp[i-1]+y} if i is odd dp[i]=min(dp[i-1]+y,dp[i+1/2]+x+z}.
For constraints like N<=10^18, we could do more optimisation. It can be proven that the number of doubling operations should be relatively small (less than 2+log2(n∗max(y,z))). Let’s iterate over this number of operations, and call it a.
Without any additions/subtractions, the final number would be 2a. Now, any addition or subtraction can add/subtract any power of two of form 2b, where b≤a, depending on where it is placed. Also, at most one addition/subtraction of 2b with b<a makes sense. In fact, we can argue that n will be formed by satisfying the equation n=2a∗k+b, where |b|<2a. It can be seen that only a handful of values for k make sense in a scenario like this (2 at most).
Let’s add cost n div 2a∗y to our current case, and set n′=n mod 2a. Now we’re left with an easier problem, writing n′ as a sum of powers of 2, with sign either +1 or −1 (note the fact that the upper bound on the power of 2 has disappeared, this is ultra important). It’s important that you convince yourself that we’re allowed to do thnt.
This problem can be solved using dp in complexity O(a).
Total complexity is O(log2(n∗(x+y+z)))