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

1.Initialize Ratings[] with the given ratings.

2.We'll first give 1 Candy to each of the children. So initialize all members in Val[] with 1.

3.Now traverse through and check with the 2 adjacent children (i + 1 and i - 1) whether the condition is held.

4.Keep doing this until we get an entire traversal where the condition is never broken. We're done then!

bool done = false;
while (!done) 
{
    done = true;
    for (int i = 0 to i = Ratings.size() - 1) 
    {
        for (int k = 1 and k = -1) 
        {
            int adjacent = i + k;
            if (adjacent >= 0 && adjacent < N) 
            {
                if (Ratings[adjacent] > Ratings[i] && Val[adjacent] <= Val[i]) 
                {                       
                    Val[adjacent] = Val[i] + 1;
                    done = false;
                }
            }
        }
    }

}

Answer 2

Think of these possible rating configurations: 1 2 3 4 5 or any increasing sequence and 5 4 3 2 1 or any decreasing sequence

what can be done in the first case? 1 2 3 4 5 is the candies that are allocated in the second case the candies are 5 4 3 2 1

The solution can be obtained by scanning the array from left to right and identifying intervals of increase and scanning from right to left and again identifying intervals of increase & allocating minimal amounts of candies in this process. for exact details, please look at the code:

#include <stdio.h>
#include <algorithm>
using namespace std;

#define N 100000

int c[N];
int val[N];

int solve(int n)
{
  int res=n;
  int i=0,value=0;
  while(i<n)
  {
    value=0;
    i+=1;
    while(i<n && c[i]>c[i-1])
    {
      value+=1;
      val[i]=value;
      i+=1;
    }
  }

  i=n-1;
  while(i>=0)
  {
    value=0;
    i-=1;
    while(i>=0 && c[i]>c[i+1])
    {
      value+=1;
      val[i]=max(val[i],value);
      i-=1;
    }
  }

  for(i=0;i<n;++i) res+=val[i];

  return res;
}

int main()
{
  int n,i;
  scanf("%d",&n);
  for(i=0;i<n;++i) scanf("%d",&c[i]);
  printf("%d\n",solve(n));
  return 0;
}

Answer 3

Perhaps the simplest solution:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {

int children;
int sum=0;

cin >> children;
int ratings[children];
int candies[children];

//give all children 1 candy to start
for(int i=0;i<children;++i)
{
     cin >> ratings[i];  
     candies[i] = 1;
}

//if the current child has a better rating than the child
//before him he is entitled to +1 greater candy than that child
for(int i=1;i<children;++i) 
{
     if(ratings[i] > ratings[i-1])
         candies[i] = candies[i-1]+1;
}

// work backwards to break any discrepancies ex.
// rating[5,4,3] -> candies[1,1,1] -> candies [1,1,1] -> candies [3,2,1]
// starting ratings  give everyone 1   first loop         second loop
for(int i=children-1;i>=0;--i)
{
     if(ratings[i] > ratings[i+1])
     {
          candies[i] = max(candies[i],candies[i+1]+1);   
     }
}

for(int i=0;i<children;++i)
{ 
     sum+=candies[i];
}

cout << sum;
return 0;

}

Answer 4

# this python code solves the problem for all test cases on interviewstreet

#!/usr/bin/python

if __name__ == "__main__":
N = int(raw_input().strip())
scores = []
for i in range(N):
    scores.append(int(raw_input().strip()))
nc = []
if(scores[0]>scores[1]):
    nc.append(-1)
    else:
    nc.append(0)
    for i in range(1,N-1):
        if (scores[i] > scores[i-1]) and (scores[i]>scores[i+1]):
        nc.append(2)
    elif (scores[i] > scores[i-1]):
        nc.append(1)
    elif (scores[i]>scores[i+1]):
        nc.append(-1) 
    else:
        nc.append(0)

    if(scores[N-1]> scores[N-2]):
        nc.append(1)
    else:
    nc.append(0)

    noc = []
    for i in range(N):
    noc.append(0)

    for i in range(N):
    if(nc[i]==0):
            noc[i] = 1

    for i in range(N):
    if(nc[i]==1) and (noc[i-1]!=0):
        noc[i] = noc[i-1]+1 

    for i in range(N-1,-1,-1):
    if(nc[i]==-1) and (noc[i+1]!=0):
        noc[i] = noc[i+1]+1

    for i in range(N):
    if(nc[i]==2) and (noc[i-1]!=0) and (noc[i+1]!=0):
        noc[i] = max((noc[i-1],noc[i+1]))+1 
    nt = sum(noc)


    print nt

Answer 5

To summarize:

#include <vector>
#include <iostream>
using namespace std;

int main() {
    int N;
    cin>>N;
    vector<int> A(N,0),B(N,1);
    for(int i=0;i<N;++i) cin>>A[i];
    for(int i=0;i<N;++i) if(A[i]>A[i-1]) B[i]=B[i-1]+1;
    for(int j=N-2;j>=0;--j) if (A[j]>A[j+1]) B[j] = max(B[j], B[j+1]+1);
    int sum=0;
    for(int i=0;i<N;++i) sum+=B[i];
    cout<<sum<<endl;
    return 0;
}

Answer 6

Actually this question can be solved by passing two times over the array. And the solution will be O(N) time. I solved this problem by using geeksforgeeks Trapping Rain Water (http://www.geeksforgeeks.org/trapping-rain-water/ ) problem. Same principles can be applied to this questions.

First of all we have two rules. - Each student gets at least 1 candy. - Each student who has a better rating than his/her neighbor (the next or the previous student) he will get at least one more candy then them.

Just as I've said we need two passing over the array. The first one will be from left to right; - At first we will assign one candy to the first one. - Then loop over the array by checking if current one has bigger rating then give him one more than the previous student, otherwise give him 1 candy.

The second pass will be from right to left. - This time we start by assigning one candy to the last one. - Then loop over the array from right to left and do the similar things just in the first loop.

After this two loops, we will loop over right and left by getting the maximum of the array and add this value to the total candies.

    Test cases :
    input  : { 1, 2, 2 }
    output : { 1, 2, 1 } => 4 
    input  : { 9, 2, 3, 4, 4, 4, 2, 1, 3, 4 }
    output : { 2, 1, 2, 3, 1, 3, 2, 1, 2, 3 } => 20

Below you can find a Java solution for this problem.

public int calculate(int[] arr) {
    int m = arr.length;
    int[] left = new int[m];
    int[] right = new int[m];
    int candies = 0;
    left[0] = 1;
    for (int i = 1; i < m; i++)
        left[i] = arr[i] > arr[i - 1] ? left[i - 1] + 1 : 1;
    right[m - 1] = 1;
    for (int i = m - 2; i >= 0; i--)
        right[i] = arr[i] > arr[i + 1] ? right[i + 1] + 1 : 1;
    for (int i = 0; i < m; i++)
        candies += Math.max(left[i], right[i]);
    return candies;
}