fatemehkarimi's blog

By fatemehkarimi, history, 2 years ago, In English

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

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

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

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   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it +1 Vote: I do not like it

        why abs(B[i] — 1) when A[i — 1] = 1?, I am a beginner so ...

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      I know that this was asked 2 years ago, Posting this for new readers
      Idea for Proof

      Lets 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.