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.
"Wording of problem statement" is perhaps the only thing difficult about this problem. Coders are needlessly getting confused by that. Few points to avoid confusion :
• Array B containing elements B1, B2,..., Bn is provided as input.
• Elements A1, A2,.., An for array A has to be decided by the coder/code. An element Ai can be any integer such that 1 <= Ai <= Bi.
• Select elements for array A such that it maximizes S (sum of difference between consecutive elements of A).
• Output required : the maximized value S.
Example : Suppose B = [2, 4, 3]. Then 1<=A1<=2, 1<=A2<=4 and 1<=A3<=3. Hence, there are 24 possible options for A, some of them are :
Thank you so much for clarifying. I think the biggest mistake they made in the wording of the problem is that they used a VERY special case in which A == B! No?
It seems to me that [10, 1, 10, 1, 10] should be the array to calculate the answer (A), not the input (B).
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
LMFAO Holy Hop Scotching Kangaroo Batman, Thank you! That simplifies this so much. Wow, I was reading that explanation and was like, there is no way anyone figures this out with getting a headache and stroke until it is rephrased. You are a real life Hero
Hi, I want to ask, though this problem was simple but still it was difficult to solve. How did you divide DP problem into subproblem? And how did you decided structure for DP? Is is like it will be learnt through practice only? Because I am facing really hard time in solve DP problems
Sherlock and Cost
You are viewing a single comment's thread. Return to all comments →
"Wording of problem statement" is perhaps the only thing difficult about this problem. Coders are needlessly getting confused by that. Few points to avoid confusion :
• Array B containing elements
B1, B2,..., Bnis provided as input.• Elements
A1, A2,.., Anfor array A has to be decided by the coder/code. An elementAican be any integer such that1 <= Ai <= Bi.• Select elements for array A such that it maximizes S (sum of difference between consecutive elements of A).
• Output required : the maximized value S.
Example : Suppose B = [2, 4, 3]. Then
1<=A1<=2,1<=A2<=4and1<=A3<=3. Hence, there are 24 possible options for A, some of them are :Out of all the possible options, A = [1, 4, 1] maximizes S.
Thus, the answer is : |4-1| + |1-4| = 3 + 3 = 6.
PS : Only Sherlock knows why the problem is named "Sherlock and Cost" ! ;-)
you lacked [2, 1, 3]
Not only that, I lack 15 more.
Please read again, I wrote : "there are 24 possible options for A, some of them ... "
Thanks bro! Much more clear...
explanation was much helpful
Thank you so much for clarifying. I think the biggest mistake they made in the wording of the problem is that they used a VERY special case in which A == B! No?
It seems to me that [10, 1, 10, 1, 10] should be the array to calculate the answer (A), not the input (B).
True !
AandBare same for the example used, that adds to confusion.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
why not [1,1,1]?
because |1-1|+|1-1|=0 which is contradictory to the maximum sum needed
Thank you for your explanation and the example. Helped me to figure out the problem :)
Thanks, for explaining the problem. This makes sense.
how to find [1,4,1] is maximizes out of all.
great! This will help.the question mentioned was so vague.
The only comment I have is that elements of B may not be integers, as it isn't specified as such in the problem statement.
Please find under the heading Input Format, it is mentioned there:
what would be the expected output of: 15100 2 100 2 100
I'm assuming that you meant :
Output for the above should be : 396
Why not 392 ?
Because the result S is calculated using A (not B).
For the given
B = 100, 2, 100, 2, 100, maximum value occurs forA = 100, 1, 100, 1, 100.alternative postitions in array should be 1 then the sum will be maximum
eg: 100 1 100 1 100
I agree, this problem is poorly explained. Thanks for your clarification, it helps a lot.
LMFAO Holy Hop Scotching Kangaroo Batman, Thank you! That simplifies this so much. Wow, I was reading that explanation and was like, there is no way anyone figures this out with getting a headache and stroke until it is rephrased. You are a real life Hero
thanks bro
Thank you Abhishek, this was very helpful in interpreting objective!
thanks for brief Before i feel i am the only one who don't understand the question.
Why do we need 'T' test case?
static int cost(int[] B) { int cost=0; for(int i=1;i
Hi, I want to ask, though this problem was simple but still it was difficult to solve. How did you divide DP problem into subproblem? And how did you decided structure for DP? Is is like it will be learnt through practice only? Because I am facing really hard time in solve DP problems
I have tried to explain this in a video https://youtu.be/7qMMqAIve78
x-D