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. :slight_smile:

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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main{
public static void main(String args[]) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
long n=Long.parseLong(br.readLine());
long a[]=new long[(int) n];
long b[]=new long[(int) n];
for(int i=0;i<n;i++){
a[i]=Long.parseLong(br.readLine());
}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…:frowning: (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);
}

Can you please explain that? :slight_smile:

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! :slight_smile:

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… :stuck_out_tongue:

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 :stuck_out_tongue:

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