Same rating, but less candies !

• I think one of the tricky points of this problem is that we might not come up
the most "optimal" solution ourselves, given a simple example.

e.g.
with the following ratings:

``````   ratings = {1, 2, 4, 4, 4, 3};
``````

The most "optimal" solution that can be came up by some evil capitalist is follows:

``````   distribution =  {1, 2, 3, 1, 2, 1}
``````

As you see, it happens that the three kids that have the same rating `4`, got different candies !

Yet, this distribution still meets the fairness principle of the problem,
i.e. a kid has a higher rating than its neighbor should have more candies.

The principle does not regulate how we assign candies to neighbors with the same rating !
As a result, the first kid got a rating `4` eventually got `3` candies since it is next to an ascending slope.
And the kid in the middle who also got a rating `4`, was left with the minimal one candy.
And the last kid got rating `4` has a slightly more compensation since it is next to a lower-rated (`3`) neighbor in addition.

Voila. Bearing the above tricky point, it should be easier to understand the following implementation (with comments):

``````public int candy(int[] ratings) {
int lastAscend = 0;
// The baseline is that each child got at least one candy.
int lastCandy = 1;
int total = 1;

for(int i=1; i<ratings.length; i++){

if(ratings[i] > ratings[i-1]){
lastAscend = i;
lastCandy ++;
total += lastCandy;

}else if(ratings[i] == ratings[i-1]){
lastAscend = i;

/* A flat growth, two peers with the same rating might be given different candies.
* To minimize the number of candies, consecutive peers with the same rating
*  are given the minimal one candy for each.
* It might seem unfair that a peer right next to a ascending peek would be given
*  much more candies than its equivalent peers.
*/
lastCandy = 1;
total += lastCandy;

}else{
/*
*  This is a descending slope, since we give the minimal candy (1) up to this point,
*  we need to compensate the previous children, to make sure that they have one
*  more candy than the one next to them.
*/
if(lastCandy == 1){
total += i - lastAscend;
}

/* When the slope starts to descend, reset the baseline to 1,
*  instead of giving candy that is one less than the previous one (peak).
*  to reduce the total number of candies that are given,
*  yet it still meet the requirements.
*/
lastCandy = 1;
total += lastCandy;
}
}

}``````

• Did you test this code ? It seems to give a wrong answer on [1,6,10,8,7,3,2] (gives 19, expected was 18)

• Because not all children in the descending slope need to have one more candy in case 3("lastCandy==1"), if the child's left neighbor's candy - child's candy > 1.

• The problem of this code is that it unconditionally compensates all the children on the descending path, including the last ascending one. But in some cases the last ascending child already has enough candies to keep balance, e.g., ratings = [1, 2, 3, 1, 0].

The fix is to replace "lastAscend" with "lastAscendCandy" + "descendLength". For children in [lastAscend, i] where ratings[i] < ratings[i-1] and ratings[i-1] = 1: all children in [lastAscend + 1, i - 1] need to have one more candy. Whether child at "lastAscend" need one more, it depends on whether it already has the enough candies.

Here is the code:

``````int candy_v3(vector<int> ratings)
{
int lastAscendCandy = 0;
int descendLength = 0;
int lastCandy = 1;
int total = 1;

for(int i = 1; i < ratings.size(); ++i)
{
if(ratings[i] > ratings[i-1])
{
descendLength = 0;
++lastCandy;
lastAscendCandy = lastCandy;
total += lastCandy;

}
else if(ratings[i] == ratings[i-1])
{
descendLength = 0;
lastCandy = 1;
lastAscendCandy = lastCandy;
total += lastCandy;

}
else
{
++descendLength;

if (lastCandy == 1)
{
if (lastAscendCandy - 1 >= descendLength)
total += descendLength - 1;
else
total += descendLength;
}

lastCandy = 1;
total += lastCandy;
}
}