Not getting the solution

#1

https://www.codechef.com/INFY20B/problems/SOLDVAL

in this question i am not able to understand the solution, i read the whole editorial still not able to solve this problem, can to please help me in this problem and tell me how to approach and solve this problem

#2

have you read this editorial??
in this question and answer both are explained clearly

exactly which part of this solution is not clear??
I will explain that part in detail

#3

i dont understand why we take left_dp and right_dp

#4

this is because we are dividing the questions into two parts and take min of both

We can divide the questions into two parts i.e. in the first part we will consider only left elements (j<=ij<=i) for calculating sold values and in the second part we will consider only right elements (j>=ij>=i) for sold values. We will maintain two dps for each part and then find the minimum of them.

  • For calculating left_dp iterate through 22 to NN calculating minimum value as min(A[i],left_dp[i-1]+1).
  • For calculating right_dp, iterate through N-1 to 1 calculating minimum value as min(A[i],right_dp[i+1]+1).

And now minimum value of left_dp and right_dp will be the answer for each index.

#5

i want to say why we are calculating left_dp and right_dp

#6

because we have to consider both side of array at a particular index
so we have to take 2 dp left and right

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.