candies - interviewstreet

Question

Alice is a teacher of kindergarten. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each children. Because children are somehow jealousy. Alice must give her candies according to their ratings subjects to for any adjacent 2 children if one's rating is higher than the other he/she must get more candies than the other. Alice wants to save money so she wants to give as few as candies in total.

Input

The first line of the input is an integer N, the number of children in Alice's class. Each of the following N lines contains an integer indicates the rating of each child.

Output

On the only line of the output print an integer describing the minimum number of candies Alice must give.

Sample Input

3
1
2
2

Sample Output

4

Explanation

The number of candies Alice must give are 1,2 and 1.

Constraints:

N and the rating of each children is no larger than 10^5.

Can anyone please help me?

Answer 1

I felt this may be one of the possible solutions...

def candy(N,r):
    H=[0]*N
    R=r
    cur_can=1
    cand=[0]*N
    cand[0]=1
    #print R#,'\n',cand
    for i in range(0,N):
        if i!=0:
            #print R[i],'  ',R[i-1]
            if R[i]>R[i-1]:
                cand[i]=cand[i-1]+1
            else:
                cand[i]=1
##            print R[i],i
    sum=0
##    print i
    print cand
    for j in range(0,N):
        sum+=cand[j]
    return sum
r=[1,2,2,4,1,2,4]
N=len(r)
print candy(N,r)

The output for the values used as a sample in th codes gives 12 as the answer, which seems right to me... What do you think?

Answer 2

AS mentioned by others,scanning left to right and then right to left,and getting max candies used at certain postion is working.

Before this, i used other way,which seemed to be working and i checked it with many different inputs,although i couldnt clearly write it in code,Here is the Algo:

Algorithm:
1.Use an int[]index array  and store all the indexes in the sorted value of thie ranks.

so here
int values[]=9 2 3 6 5 4 3 2 2 2
so index sorted array would be
int index[]= 1 7 8 9 2 6 5 4 3 0


now int[] result=new result[10];
and initialize it with -1.

sending each value from index[]in the order and make sure that each one is satifying the given condtions.
that

i=index;
while(i>=0)
{
if(i-1>=0 && arr[i]>arr[i-1])
break;
if(i-1>=0 && arr[i]<arr[i-1])
result[i-1]=result[i]+1;
else
if(i-1>=0 && arr[i]==arr[i-1])
 result[i-1]=1
 i--;
}

//similary towards the right

i=index;
while(i<arr.length)
{
if(i+1<arr.length && arr[i]>arr[i+1])
break;
if(i+1<arr.length && arr[i]<arr[i+1])
 result[i+1]=1+result[i];
else
if(i+1<arr.length && arr[i]==arr[i+1])
 result[i+1]=1

 i++;
}


so result array will be like this for index 1

2 1 2 3 - - - - - -

then for index 7
2 1 2 5(its modifed from 3) 4 3 2 1 1

followe by indeices :8 9 2 6 5 4 3 0 

which all satifies the condtion and more modification occurs in this case..so total number of candies =22

Answer 3

To make the analysis of this algorithm more interesting I will the following input:

9
2
3
4
4
4
2
1
3
4

Firstly, notice if a kid sits next to a kid who is getting x candies and that kid has a lower rating then the first kid should get at least x+1 candies. Making the difference more than 1 will just waste candies. The difference sometimes must be greater than 1, but I'll get to when that happens later.

Now on to finding the kids who should get only one candy. I visualise the ratings as a mountain range (The greater the rating the higher the mountains at that point) and finding the kids who should get one candy as finding valleys (points where both neighbours have a higher rating or the same rating) in the mountain range. The example given would look like (the valleys are indicated by the arrows):

  ***   *
 ****  **
****** **
*********
^  ^  ^

For the purpose of this process I assume there are 2 peaks of "infinite" height before the beginning and after the end of this line. (When I say infinite I just mean larger than any possible value in the input so you can just use 10^5+1 for "infinity". In practice, I'd use a value larger than that in case the problem setters have bugged input data.)

You can easily find the valleys using the following code:

ratings = ...
N = ...
valleys = []

def get_rating(i):
    if i < 0 or i > N-1:
        return INFINITY
    return ratings[i]

for i from 0 to N-1:
    if get_rating(i) <= get_rating(i-1) and get_rating(i) <= get_rating(i+1):
        valleys.append(i)

The array valleys contains the indices of the valleys. We know each kid representing a valley should get one candy. For illustration assume the valley is at index 4. Now we know the kids at index 3 and 5 should get at least 2 candies. If the kid at index 2 has a higher rating than the kid at index 3 that kid should get at least 3 candies. And so on for 2 and down. Similarly for 6 and up.

Note I say "at least", this is because of peaks (kids whose ratings are higher than both of their neighbour's, note unlike valleys I don't include equality in this definition). Peaks can have two minimum constraints and we simply choose the greater of the two.

Now we can find the number of candies each kid should get with the following code:

candies = [0] * N # An array of N 0s
for valley_idx in valleys:
    candies[valley_idx] = 1

    cur_idx = valley_idx-1
    cur_candies = 2
    while cur_idx >= 0 and ratings[cur_idx] > ratings[cur_idx+1]:
        candies[cur_idx] = max(candies[cur_idx], cur_candies)
        cur_idx -= 1
        cur_candies += 1

    cur_idx = valley_idx+1
    cur_candies = 2
    while cur_idx < N and ratings[cur_idx] > ratings[cur_idx-1]:
        candies[cur_idx] = max(candies[cur_idx], cur_candies)
        cur_idx += 1
        cur_candies += 1

Then the number of candies the teacher needs to buy is the sum of the values in the candies array.

Doing this the answer turns out to be 18 for our sample input or in the form of a graph:

  * *   *
 ** ** **
*********

Solution to slightly altered problem statement

In the above solution I assumed that adjacent kids with the same rating don't place any restrictions on the amount of candy either should get with relation to the other. If it is instead the case that both kids need to get the same amount of candy we can quite easily alter the algorithm to take this into account.

The basic idea is that we do a sort of run length encoding, because we can notice that whether there are 1 or more kids in a row that have the same rating it doesn't alter the amount of candies their neighbours should get. We need to keep track of the number of kids in a row though since 5 kids in a row getting 5 candies means we have to dole out 25 candies and not just 5. We do this with a multipliers array. Using the following code we find the new ratings array and the multipliers array:

new_ratings = [ratings[0]]
multipliers = [1]
for i from 1 to N-1:
    if ratings[i] == new_ratings[len(new_ratings)-1]:
        multipliers[len(new_ratings)-1] += 1
    else:
        new_ratings.append(ratings[i])
        multipliers.append(1)

Now we just run the original algorithm on the new_ratings array and get a candies array. Then to get the actual amount of candies we can just run:

answer = 0
for i from 0 to len(new_ratings)-1:
    answer += multipliers[i] * candies[i]

Doing this the answer turns out to be 20 for our sample input or in the form of a graph:

  ***   *
 ***** **
*********

Answer 4

I used simple DP approach to solve this problem. Increment the ith value in DP table if u get the rating greater than previous one, else there might be two conditions. One condition is DP value of previous index is 1 then traverse in reverse order till you get value lesser than its next value and keep updating the DP. A another condition is DP value of previous index is greater than 1, in that case present index in DP is assigned 1.

for(int i=1; i <= n; i++){
    scanf("%d", ra+i);
    if( ra[i] > ra[i-1] )
        dp[i] = dp[i-1] + 1;
    else if( dp[i-1] == 1 ){
        dp[i] = 1;
        for( int j=i-1; j>0; j-- )
            if( ra[j] > ra[j+1] )
                dp[j] = max ( dp[j+1] + 1, dp[j] );
            else
                break;
    }       
    else
        dp[i] = 1;
}
long long sum = 0;
for(int i = 1;i <= n; i++)sum+= dp[i];
printf("%lld\n",sum);