### fatemehkarimi's blog

By fatemehkarimi, history, 2 years ago,

I had a hard time finding a solution to the problem "Sherlock and cost" [](https://www.hackerrank.com/challenges/sherlock-and-cost/problem)but I wasn't able to solve it. then I searched the whole internet and read the people's code. I understood what they do(i.e understand their code) but I can't understand why this algorithm is true and what is the recursion??

can anyone tell me how does its dynamic approach work?? this is the code I read for this problem

• +4

 » 2 years ago, # |   0 I think the dynamic programming state would be dp[i][k] which represents the optimal overall value if we place integer k at position i of A. There are 100 transitions (one for each value for k). If we memoize the states, then, we evaluate each transition once only. So we have 1e2 * 1e5 * 20 operations which is 2e8 operations and should be able to pass the time limit.I haven't tried out this solution on the judge. But this seems like a sensible solution to me.
 » 2 years ago, # | ← Rev. 4 →   0 It's easy to prove that for all i, the optimal A has either A[i] = 1 or A[i] = B[i]. Therefore you can just keep two values at every step, maximum value such that A[i-1] = 1 and maximum value such that A[i-1] = B[i-1]. The state transitions are trivial.Edit: State transitions:Let DP[prev][1] be the one where A[i-1] = B[i-1], and DP[prev][0] the one where A[i-1] = 1. Now: DP[curr][1] = max(DP[prev][1] + abs(B[i] - B[i-1]), DP[prev][0] + abs(B[i] - 1)); DP[curr][0] = max(DP[prev][1] + abs(B[i-1] - 1), DP[prev][0] + abs(1 - 1)); 
•  » » 2 years ago, # ^ |   +8 I can understand well that each A[i] is either 1 or B[i]. actually, those trivial state transitions are not trivial for me!! I mean I can't understand how these 2 arrays work(dp[i][0] and dp[i][1])
•  » » » 2 years ago, # ^ | ← Rev. 4 →   0 The answer we want is the maximum possible cost(the sum S) if, at any index 1<= i <=n we choose either A[i]=1 or A[i]=B[i].So, dp[i][0] is the maximum possible cost of the array A[1..i] if we choose to put A[i-1]=1. And similarly, dp[i][1] will store the best cost we can get of the array A[1..i] if we put A[i-1]=B[i].So the answer will be max(dp[n][0] , dp[n][1]).We begin by setting dp[1][0] = dp[1][1] = 0 because the sum S is 0 for any array of length 1(Base case for the recurrence formula).Then, at each index i(from 2 to n), there are two cases: We choose A[i]=B[i] so, depending on the previous state(i-1), we will compute the answer for this state.We will take the maximum of the two possible choices, either the previous element A[i-1] was put to B[i-1], so that will give us abs(B[i]-B[i-1])+dp[i-1][1].Else(in the case where A[i-1]=1) we will get abs(B[i]-1) + dp[i-1][0].So the answer(the sum S) for our current state (array A[1..i]) will be the maximum of these two. We choose A[i]=1.It's the same, you just change B[i] to 1. We just calculate the best possible answer for each A[1..i] using the best answer for A[1..i-1] until we reach A[1..n], that will be the best possible cost S for our entire array.
•  » » » » 8 months ago, # ^ |   +1 why abs(B[i] — 1) when A[i — 1] = 1?, I am a beginner so ...
•  » » » » » 8 months ago, # ^ |   +1 a[i-1]=1 means we consider taking 1 in the previous position and abs(B[i]-1) will give the the abs. diff. between current pos. and the previous one (which we are considering as 1).
•  » » 2 years ago, # ^ |   0 It's easy to prove that for all i, the optimal A has either A[i] = 1 or A[i] = B[i]Hmm. Seems intuitive. But I couldn't find a formal proof. Do you mind sharing the proof please?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I know that this was asked 2 years ago, Posting this for new readers Idea for ProofLets say you have values for A[i-1] and A[i+1], you need to find A[i] such that A[i] belongs to [1,B[i]] and |A[i]-A[i+1]| + |A[i]-A[i-1]| is maximized, draw the number line and mark A[i-1] and A[i+1], you then have to analyzed few cases then you will see that in every case either A[i]==B[i] or A[i]==1 gives the maximum.