Sherlock and Cost Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Input and output are independent events. You can follow any order you prefer. Irrespective of when you take inputs, only output matters. Output of the program is compared with the expected output, if it matches, the solution is accepted.
abs(ar[i]-1) is not added to dp[i][0] because dp[i][0] means we are taking ar[i]=1 and dp[i+1][0] means we are taking ar[i+1] as 1 now abs(ar[i]-1) will be abs(1-1) which is 0.so there is no need to add someting which is always going to be zero
Here are two columns '0' and '1'.
'0' column indicates take present ar[i] = 1
while
'1' column indicates take present ar[i] = b[i] i.e. the max possible value .
for dp[i][0] (present value = 1) :
either dp[i-1][0] + abs(1 - 1) as previous value=1 and present value=1
or dp[i-1][1] + abs(1 - ar[i-1]) as previous value=max and present value=1
for dp[i][1] ( present value = max i.e. arr[i] ) :
either dp[i-1][0] + abs(1 - ar[i]) as previous value=1 and present value=max
or dp[i-1][1] + abs(ar[i]- ar[i-1]) as previous value=max and present value=max
Sherlock and Cost
You are viewing a single comment's thread. Return to all comments →
And also, what is the test case workflow?
Do I get all the inputs and then spit out all the outputs or...
Do I get input for test case #1, output for test case #1, then get input for test case #2, output for test case #1, and so on ?
Input and output are independent events. You can follow any order you prefer. Irrespective of when you take inputs, only output matters. Output of the program is compared with the expected output, if it matches, the solution is accepted.
Thank you for clarifying.
So I can just put the whole app in a big loop and do input/output/input/output?
Yup !
Hey can you explain me this pls!
In this statement,dp[i+1][0]=max(dp[i][0],dp[i][1]+abs(ar[i]-1)); why is abs(ar[i]-1) added to dp[i][1] and not to dp[i][0]?
abs(ar[i]-1) is not added to dp[i][0] because dp[i][0] means we are taking ar[i]=1 and dp[i+1][0] means we are taking ar[i+1] as 1 now abs(ar[i]-1) will be abs(1-1) which is 0.so there is no need to add someting which is always going to be zero
thank for your explaning.
Here are two columns '0' and '1'. '0' column indicates take present ar[i] = 1 while '1' column indicates take present ar[i] = b[i] i.e. the max possible value .
for dp[i][0] (present value = 1) :
either dp[i-1][0] + abs(1 - 1) as previous value=1 and present value=1 or dp[i-1][1] + abs(1 - ar[i-1]) as previous value=max and present value=1
for dp[i][1] ( present value = max i.e. arr[i] ) :
either dp[i-1][0] + abs(1 - ar[i]) as previous value=1 and present value=max or dp[i-1][1] + abs(ar[i]- ar[i-1]) as previous value=max and present value=max
therefore, dp[i][0]=max(dp[i-1][0],dp[i-1][1]+abs(ar[i-1]-1));
dp[i][1]=max(dp[i-1][0]+abs(ar[i]-1),dp[i-1][1]+abs(ar[i-1]-ar[i]));
thankyou for the great explanation
thanku...it really helped.
What is the base case for this dp array? Like what should I initialise for dp[0][0] and dp[0][1]?
both with 0 becz we will start adding value when we have atleast two elements.
please explain me again. I still not understand
please explain me the above snippet of the code. I still not