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.

I solved it, but I have no idea how to prove my solution is correct. First I go left to right and set "next" candy value to either "previous+1" or "1". This way I get the up trends. Then I go right to left and do the same, this way getting the down trends. Very simple O(2xN) solution, but doesn't look like it's the intended one.

I think the problem might be that it's not exactly up or down trends, when you go throuth the sequence from both side, and meet in the middle, you don't have to raise all the value in the left part or the right part. I think the best way is divide and conquer algorithm.

I don't think it's a true dp as we are doing reinforcement in the dp array which is not done generally. I also had somewhat same solution but my array name was not dp as mentioned earlier.

brother your maths need to be brushed up
first off all you havn't included the last (1) in your result and even if you have not included, you haven't sum up all the values right
2+1+2+5+4+3+2+1+1 = 21

Interesting. I implemented both - dynamic and this solution and found that performance is about the same, but it varies - in some cases dynamic solution is better, while in others your solution is.

After the forward sweep, each child has 1 candy because each child has a rating equal to or less than that of its predecessor.

After the backward sweep, the 5th child has 1 candy and the 6th child has 4 candies (because the each have a rating of 6) while the 3rd child has 1 candy and the 4th child has 2 candies (because they each have a rating of 7).

So, the final rating:candies distribution is:
9:3 8:2 7:1 7:2 6:1 6:4 5:3 4:2 3:1 for a total of 19 candies.

Please check out this blog http://stackandqueue.com/?p=108, it explains why standard solution actually works. Trick is to understand why local minimas will get 1 candy and then you can get candies for other students

here is an explanation:
We basically have to find sequences of numbers which are always increasing and those which are decreasing. initialise a count array of length n with all 1. then whenever u see an increasing pattern, set the bigger number count = smaller number count + 1 while traversing the array forward.
then traverse the array backwards and check for the same increasing pattern (which would be decreasing since we are traversing backward). but only do the bigger number count = smaller number count + 1 when (bigger number count <= smaller number count). this is because we might already have set the value to something bigger before while traversing forward.
here is an example,
array : 2 4 5 6 7 8 9 5 4
count : 1 2 3 4 5 6 7 2 1
count array can look like a mountain. increase then decrease
the peak of the mountain (9 here) is determined by which slope is longer, left or right. that is why u have that check while traversing backards.
try manually doing this and u will see why:
array : 2 9 8 6 4 3 2 1
count : 1 7 6 5 4 3 2 1

My solution is simmilar to yours. Logic behind this is that if you make a graph between marking and index of child then local minima will always have 1(min) candy. Then next on both sides of local minima will have 1(min) + 1 candy and so on. This approach can be easily implemented by the method you mentioned above.

I don't quite understand this line in the second half of your code:
(markings[i] > markings[i+1] && (markings[i+1] + 1) > markings[i])

this logically translates to "markings[i] > markings[i+1] && markings[i] <= markings[i+1]", which will always evaluate to false...and thus candies[i] will be assigned to candies[i] every time...so how exactly will this still work as intended?

I did it in same way, and this is my explanation :

consider two arrays 'stairr'(for stair right) and 'stairl'(for stair left). Initialize it by 1.

stairr[i] contains number of consecutive decreasing elements(or ratings) on the right side of element 'i'(inclusive of element itself. So value will be >= 1). Similarly, we can define stairl[i].

Now, the reason I am using word stairs is because If we notice a candy value of particular element(or rating), it will depend on how many consecutive decreasing elements(or ratings) are on its left and right side. This 'consecutiveness' is like steps of stairs. More precisely, candy value will be maximum of both of these values. But why is it so?
Because -

(i) suppose an element has stairr and stairl value 1. So we can comfortably assign its candy value as 1.

(ii) Otherwise, suppose and element 'i' has stairr[i] > stairl[i]. Now, bottom elements of both right stair and left stair will have value 1, using (i) part. We can observe that to minimize the no of candies given, each 'step up' on the stair should increase the value of candy number by 1, if possible. This can be achieved it candie value of element 'i' is stairr[i] and candy value of each element in right stair of 'i' will decrease by 1 as we go down untill it reaches the bottom, which will have value 1.
Similarly, if stairl[i] > stairr[i], then candy value of element 'i' will be stairl[i].

(iii) What if two consecutive elements have equal value(or rating) ?
If 'i' and 'i + 1' have equal rating, then element 'i' enforce no constraint on element 'i + 1', so it is just like as if there is no stair step on left of 'i + 1' or stairl[i + 1] = 1(just the element itself).
Similarly, stairr[i] = 1.

This is exactly the right method because what we need to do is to take chunks of three at a time and compare the middle first with the value at left and then with the value at right and according to that increase the value of the middle value...
In the technique discussed above when we are traversing left to right we are actually comapring the value of that middle part with its left value and when we are traversing from right to left we are actually comparing value of middle with its right value.

Same, made 2 passes from left to right, then from right to left. All test passed. Think the variant with DP from editorial (implementation) is more complex. It's funny, but the "Problem Setter's code" is simplier and really close to my solution.

Here is the formal definition of Big-O:
f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k.
So,saying that there is no such thing as O(2xN) is wrong.
Although, you may say that O(N)=O(2xN).

intmain(){intn;cin>>n;vector<int>r(n);// children ratingsvector<int>c(n);// candies allocated to each child// take in r[] and parse left to rightintnumcandies=1;// num of candies to givec[0]=1;cin>>r[0];for(inti=1;i<n;i++){cin>>r[i];if(r[i]>r[i-1])numcandies++;elseif(r[i]<=r[i-1])numcandies=1;c[i]=numcandies;}// 2nd parse right to left and accumulate totalnumcandies=1;longtotal=c[n-1];for(inti=n-2;i>=0;i--){if(r[i]>r[i+1])numcandies++;elseif(r[i]<=r[i+1])numcandies=1;c[i]=(numcandies>c[i]?numcandies:c[i]);//use the larger of 2 parsestotal+=c[i];}cout<<total;return0;}

i made my solution using the same logic, just in one for, without the need of using two as most of people here , just arr1 from left to right, and arr2 right to left.

// Thank you, I applied this logic in Javascript, here's the code if anyone's introuble with any test cases.

function candies(n, arr) {
var candiesArray = new Array(n);
//Declare how much the first person starts with.
candiesArray[0]=1;
var sumCandies = 0;
//Loop forward -->
for( var i = 1 ; i < n ; i++ ) {
if( arr[i]>arr[i-1] ){
candiesArray[i]=candiesArray[i-1]+1;
} else {
candiesArray[i]=1;
}
}
//Loop back <--
for (var i = n-2; i>=0; i--){
if(arr[i]>arr[i+1] && candiesArray[i]<=candiesArray[i+1]){
candiesArray[i]=candiesArray[i+1]+1;
}
sumCandies += candiesArray[i];
}
sumCandies += candiesArray[n-1];
return(sumCandies);
}

that is exactly what I did. Does not seem complicated at all.

Pass one, you only consider the neighbour to the left and make sure, the current who has a higher score get at least one candy more than the left; Pass two, do in from right to left, check if the neighbour on the left who has a greater score gets at least one more than the right.

I think this is minimal because each element is only affected by its nearest neighbours, i.e., left and right, so two passes from different direction should make sure that the cost is minimal.

The o/p for the first pass is that every child with higher rating than his left neighbour has more no.of candies.
The Loop invariant can be that we are doing a safe move in giving a higher rated child 1 more candy than his left sided neighbour, because
1> the prob requires it to be done so
2> This the minimum possible increase (hence it is part of the optimal soln). Any other number of toffees must be >= this number.

The same argument can be given for your right sided pass

I did something similar but I am failing to see why this problem is part of the dynamic programming section in the interview practice set. Any one could explain?

Cause you can always memoize each of the paths to the solution; However, the truh is that once you do it using memoization is still not fast engough for some of the test cases.

## Candies

You are viewing a single comment's thread. Return to all comments →

I solved it, but I have no idea how to prove my solution is correct. First I go left to right and set "next" candy value to either "previous+1" or "1". This way I get the up trends. Then I go right to left and do the same, this way getting the down trends. Very simple O(2xN) solution, but doesn't look like it's the intended one.

did all the test cases pass?

Yes.

i did exactly the same,however it failed two test cases :(

I had the same - I think you accumulate the result on an int that is overflowing, try long long

I think the problem might be that it's not exactly up or down trends, when you go throuth the sequence from both side, and meet in the middle, you don't have to raise all the value in the left part or the right part. I think the best way is divide and conquer algorithm.

I had the same 2 tests failing. It was enough to save the sum in a long, rather than in a int.

Using long worked for me.

try this test case:-

10

9 2 3 6 5 4 3 2 2 2

how answer will be 20?

how it is 20?

In your solution '<' should be there instead of '<=', read first solved example.

I don't think it's a true dp as we are doing reinforcement in the dp array which is not done generally. I also had somewhat same solution but my array name was not dp as mentioned earlier.

9 2 3 6 5 4 3 2 2 2

1,1,2,3,1,1,1,1,1,1 right

2,1,1,5,4,3,2,1,1,1 left

find out the max for each reasult

2,1,2,5,4,3,2,1,1,1

`2+1+2+5+4+3+2+1+1= 20`

brother your maths need to be brushed up first off all you havn't included the last (1) in your result and even if you have not included, you haven't sum up all the values right 2+1+2+5+4+3+2+1+1 = 21

How you can give 1 1 to 9 and 2 because they are closet to each other so high ratuing must get the higher

how is this working i am unable to get it . could you please explain

22?

take the data type of result as long long int instead of int

Interesting. I implemented both - dynamic and this solution and found that performance is about the same, but it varies - in some cases dynamic solution is better, while in others your solution is.

Can you please explain how you applied dynamic programming method.

do you mind explaining your DP? I don't understand how DP can beat this linear solution.

how many candies did you give to the first child??

I have same solution working on given testcases but it doesn't work for hidden ones. I scored just 5 :-(

can thi algo traverse 9,8,7,7,6,6,5,4,3,

i think no????

Sure it does.

After the forward sweep, each child has 1 candy because each child has a rating equal to or less than that of its predecessor.

After the backward sweep, the 5th child has 1 candy and the 6th child has 4 candies (because the each have a rating of 6) while the 3rd child has 1 candy and the 4th child has 2 candies (because they each have a rating of 7).

So, the final rating:candies distribution is:

9:3 8:2 7:1 7:2 6:1 6:4 5:3 4:2 3:1 for a total of 19 candies.

thanks alot !!ur this post helped me!!

How about : 9:2 5:1 8:2 7:1 7:2 6:1 6:3 4:2 3:1 -> 15 candies there may be a better solution

their positions are fixed

Please check out this blog http://stackandqueue.com/?p=108, it explains why standard solution actually works. Trick is to understand why local minimas will get 1 candy and then you can get candies for other students

This link is now dead but accessible at http://web.archive.org/web/20170820045023/http://stackandqueue.com:80/?p=108

I did the same. Is O(N), so is optimal.

This is excellent solution. Note that two testcases may fail due to size of the resulting sum: Int vs Long

Ugh... yes got tripped up by int vs long (Java solution). Thanks!

Thank you so much!

But this gives me answer of second test case =20. Please explain. How do you explain the overlapping answers?

I solved it in the same manner. O(2xN) is O(N). This does not need DP at all.

here is an explanation: We basically have to find sequences of numbers which are always increasing and those which are decreasing. initialise a count array of length n with all 1. then whenever u see an increasing pattern, set the bigger number count = smaller number count + 1 while traversing the array forward. then traverse the array backwards and check for the same increasing pattern (which would be decreasing since we are traversing backward). but only do the bigger number count = smaller number count + 1 when (bigger number count <= smaller number count). this is because we might already have set the value to something bigger before while traversing forward. here is an example, array : 2 4 5 6 7 8 9 5 4 count : 1 2 3 4 5 6 7 2 1 count array can look like a mountain. increase then decrease the peak of the mountain (9 here) is determined by which slope is longer, left or right. that is why u have that check while traversing backards. try manually doing this and u will see why: array : 2 9 8 6 4 3 2 1 count : 1 7 6 5 4 3 2 1

Thank you!. Your explaination is very helpful.

My solution is simmilar to yours. Logic behind this is that if you make a graph between marking and index of child then local minima will always have 1(min) candy. Then next on both sides of local minima will have 1(min) + 1 candy and so on. This approach can be easily implemented by the method you mentioned above.

but what about when the adjacent enteries are equal??

I don't quite understand this line in the second half of your code: (markings[i] > markings[i+1] && (markings[i+1] + 1) > markings[i])

this logically translates to "markings[i] > markings[i+1] && markings[i] <= markings[i+1]", which will always evaluate to false...and thus candies[i] will be assigned to candies[i] every time...so how exactly will this still work as intended?

I did it in same way, and this is my explanation :

consider two arrays 'stairr'(for stair right) and 'stairl'(for stair left). Initialize it by 1.

stairr[i] contains number of consecutive decreasing elements(or ratings) on the right side of element 'i'(inclusive of element itself. So value will be >= 1). Similarly, we can define stairl[i].

Now, the reason I am using word stairs is because If we notice a candy value of particular element(or rating), it will depend on how many consecutive decreasing elements(or ratings) are on its left and right side. This 'consecutiveness' is like steps of stairs. More precisely, candy value will be maximum of both of these values. But why is it so? Because -

(i) suppose an element has stairr and stairl value 1. So we can comfortably assign its candy value as 1.

(ii) Otherwise, suppose and element 'i' has stairr[i] > stairl[i]. Now, bottom elements of both right stair and left stair will have value 1, using (i) part. We can observe that to minimize the no of candies given, each 'step up' on the stair should increase the value of candy number by 1, if possible. This can be achieved it candie value of element 'i' is stairr[i] and candy value of each element in right stair of 'i' will decrease by 1 as we go down untill it reaches the bottom, which will have value 1. Similarly, if stairl[i] > stairr[i], then candy value of element 'i' will be stairl[i].

(iii) What if two consecutive elements have equal value(or rating) ? If 'i' and 'i + 1' have equal rating, then element 'i' enforce no constraint on element 'i + 1', so it is just like as if there is no stair step on left of 'i + 1' or stairl[i + 1] = 1(just the element itself). Similarly, stairr[i] = 1.

This is exactly the right method because what we need to do is to take chunks of three at a time and compare the middle first with the value at left and then with the value at right and according to that increase the value of the middle value... In the technique discussed above when we are traversing left to right we are actually comapring the value of that middle part with its left value and when we are traversing from right to left we are actually comparing value of middle with its right value.

Same, made 2 passes from left to right, then from right to left. All test passed. Think the variant with DP from editorial (implementation) is more complex. It's funny, but the "Problem Setter's code" is simplier and really close to my solution.

No such thing as O(2xN), it is simply a O(N) solution

Here is the formal definition of Big-O:

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k.So,saying that there is no such thing as O(2xN) is wrong. Although, you may say that O(N)=O(2xN).Formally g(n) could be g(n)=2*n. Therefore it's correct to say O(2*n). And we all know, O(2*n)=O(n). Both is correct.

That's what I said

Passed all tests in c++:

thanks very good solution!!!!

thanks very good solution!!!!

Yup! The same I have done and passed all the test cases.

i made my solution using the same logic, just in one for, without the need of using two as most of people here , just arr1 from left to right, and arr2 right to left.

// Thank you, I applied this logic in Javascript, here's the code if anyone's introuble with any test cases.

that is exactly what I did. Does not seem complicated at all.

Pass one, you only consider the neighbour to the left and make sure, the current who has a higher score get at least one candy more than the left; Pass two, do in from right to left, check if the neighbour on the left who has a greater score gets at least one more than the right.

I think this is minimal because each element is only affected by its nearest neighbours, i.e., left and right, so two passes from different direction should make sure that the cost is minimal.

does this algo can be called Greedy method? if not is there any other paradigm this algo will form under?

Passed all the cases, thanks! But how this even comes to your mind? I was stuck on trying to solve it using iterative dp solution.

The o/p for the first pass is that every child with higher rating than his left neighbour has more no.of candies. The Loop invariant can be that we are doing a safe move in giving a higher rated child 1 more candy than his left sided neighbour, because 1> the prob requires it to be done so 2> This the minimum possible increase (hence it is part of the optimal soln). Any other number of toffees must be >= this number.

The same argument can be given for your right sided pass

For 1 2 2 with that logic you would get 1 2 2 which is wrog becuase final expected output is 4 in this case.

I did something similar but I am failing to see why this problem is part of the dynamic programming section in the interview practice set. Any one could explain?

Cause you can always memoize each of the paths to the solution; However, the truh is that once you do it using memoization is still not fast engough for some of the test cases.