# Need solution for- "Hackerrank - Candies"

I had been trying this problem since over 4 hours, only to realize that all of the 3 approaches I thought of are horribly wrong. I would appreciate if anyone can share a good approach to solve the problem.

This is the code, and its AC http://ideone.com/x58uJV

3 Likes

This my solution to Candies: https://www.hackerrank.com/challenges/candies/submissions/code/37181251 if you need any further explanation let me know.

import java.io.IOException;
class Main{
public static void main(String args[]) throws IOException{
long a[]=new long[(int) n];
long b[]=new long[(int) n];
for(int i=0;i<n;i++){
}long res=0;b[0]=1;
for(int i=1;i<n;i++){
if(a[i]>a[i-1])
b[i]=b[i-1]+1;
else
b[i]=1;
}for(int i=(int) (n-2);i>=0;iâ€“){
if(a[i]>a[i+1] && b[i]<=b[i+1])
b[i]=b[i+1]+1;
res+=b[i];
}

``````	System.out.println(res+b[(int) (n-1)]);
}
``````

}

1 Like

Before answering this question i wanna know about your level in DP. Do you have a good command in DP?

1 Like

depends on what you interpret as â€śgood commandâ€ť. I am able to solve problems involving concept of storing answer of series upto index I and using it to find final ans (Eg-LIS). Usually problems regarding 1-D dp table are solvable (provided I am able to grasp the trick). For 2-D table requirement, its kinda tricky. I am aware of concepts of LCS, but I get overwhelmed by number of possibilities usually (in thinking stage).

It can be solved with two pointer, start from beginning allotting minimum to first child, calculate as stated till end, then iterate from end and maintain the conditions. Itâ€™ll get AC. Calculate sum of the array then.

What about this one then- â€ś5 4 3 2 1â€ť? We are kind of concerned with the length till which it is monotonically increasing or decreasing, if I get the Q correctlyâ€¦And lol, I tried to do as you stated, but T_Tâ€¦ (Failed at implementing what I have in mind)

check the answer, probably you are doing different than what I had said. Check it in ideone

Thanks for code dear! I was able to figure out the first loop which you used, but whats the purpose of your second loop-

for(int i=n-2;i>=0;iâ€“){
if(arr[i]>arr[i+1])
dp[i]=max(dp[i],dp[i+1]+1);
}

1 Like

Unable to access your code dear! Hackeerank doesnâ€™t allow anyone else to pry upon your code and submissions. Can you copy paste it? Also, I am looking for explanations, so if you can explain, then I would REALLY appreciate it!

check the 2nd test case
it is 2 4 2 6 1 7 8 9 2 1
so in the first pass dp values will be 1 2 1 2 1 2 3 4 1 1
when i iterate it from reverse side I need to maintain condition that if two people are sitting next to each other I should allot more candie to one with higher rating That part maintains that condition
so on reverse pass the dp values will change to 1 2 1 2 1 2 3 4 2 1
and if I donâ€™t include that the dp values will be 1 2 1 2 1 2 3 3 2 1 which is incorrect. As you stated if you do only forward pass the condition wonâ€™t be satisfied for the case above, tht is the reason for rev pass

1 Like

@vijju you can access others code, only if you have solved itâ€¦

1 Like

This isâ€¦beautiful. Wow. I was also thinking how to overcome it, and went on to concept of hill and valley numbers (Check till when the ratings monotonically inc/dec, find length and add candies likewise. The peaks gave me tough time as they were getting included twice :/)

Thanks for explanation dear! Your solution is really elegant.

T_T. Oh! This â€śkrooowalâ€ť world XD

1 Like

You were thinking too complicatedly

And ironically I was trying to â€śkeep it simple.â€ť

Lol.

1 Like

I suggest you to learn markdown format for writing efficient code and answers here

1 Like