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

A very easy implementation

Space Complexity: O(n) Time Complexity : O(n)

Step 1: Start traversing the array from left to right and assign the value 1 to each index in dp array.

Step 2: Start traversing the array from left to right and if the person scored more marks then the person sitting to his left then dp of that person will be dp[i-1]+1;

Step 3: Start traversing the array from right to left and if the person scored more marks then the person sitting to his right then dp of that person will be max(dp[i],dp[i+1]+1);

Step 4 : Add all the values in dp array.

#include<bits/stdc++.h>
using namespace std;
long int arr[100005];
long int dp[100005];
int main()
{
    int n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
      scanf("%ld",&arr[i]);
    long int ans=0;
    dp[0]=1;
    for(i=1;i<n;i++)
         {
            if(arr[i]>arr[i-1])
                dp[i]=dp[i-1]+1;
            else
                dp[i]=1;
         }
      for(i=n-2;i>=0;i--)
      {
          if(arr[i]>arr[i+1])
            dp[i]=max(dp[i],dp[i+1]+1);
      }
     for(i=0;i<n;i++)
     {
         ans=ans+dp[i];
     }
    cout<<ans<<endl;
    return 0;
}

Answer 2

Let's say We have

1, 5, 2, 10, 10 3, 8, 9 , 1 , 1, 2 as ratings of 11 students S1 to S11

Let us say we make a graph rating vs student where rating is plotted on y axis, then

1. Local minimas will always get one candy, so student S1 , S3, S6, S9 and S10 will be local minimas and will get one candy. We can argue by saying there is a minimum solution (So) which deviate from what we say, then we can create one more solution (So1) where all the students get same candy and local minima which deviates gets one candy, then So1 will be minimum, so therefore there can be no minimum solution where local minimas get candies more than 1.

2. Once you have got values of local minimas, you can transverse left and right of the minima to calculate candies of other students.

3. For local maxima , it will be greater of value for its adjacent nodes +1. Working code is below, time complexity is O(n) and space complexity is O(n)

   public static int candy(ArrayList<Integer> a) {
       int size = a.size();
       int[] cand = new int[size];
   
       // give all children candies equal to 1
       // local minimas will get 1
       for(int i = 0; i < size; i++)
       {
           cand[i] = 1;
       }     
       // increase count on the right of local minimas
       for(int i = 1; i < size; i++)
       {
           if(a.get(i) > a.get(i-1))
           {
               cand[i] = cand[i-1]+1;
           }
       }
       // increase count on the left of local minimas
       // local maximas should be max of left and right
       for(int i = size-2; i >= 0; i--)
       {
           if(a.get(i) > a.get(i+1))
           {
               cand[i] = Math.max(cand[i], cand[i+1]+1);
           }
   
       }
   
       // get the sum
       int count = 0;
       for(int i = 0; i < size; i++)
       {
           count = count + cand[i];
       }
       return count;
   }
   

You can test with test cases at HackerEarth Problem : https://www.hackerrank.com/challenges/candies

Leetcode : https://leetcode.com/problems/candy/

You can find more detailed explanation of why this works @ http://stackandqueue.com/?p=108

Answer 3

I don't think this is a very difficult problem. If you think of it carefully, you will get you own answer.

#include <iostream>
#include <queue>

using namespace std;

#define CALC(n) (n)+(n)*((n)-1)/2

struct PAIR {
int n;int up;//up=0,1,2; 0是升，1是平，2是降
public:
PAIR(int _n,int _u){
    n=_n;up=_u;
}
};

int N;

queue<PAIR> q;

int calc(int up,int p){
    if(up==1)
        return p;
    else {
        return p+p*(p-1)/2;
    }
}

int getType(int lc,int c){
    int up=-1;
    if(c>lc)
    up=0;
    else if(c==lc)
    up=1;
else
    up=2;
return up;
}

int main(int argc, const char * argv[])
{
scanf("%d",&N);
int lastChild,child,n=2;
long long result=0;
scanf("%d%d",&lastChild,&child);N-=2;
int up=getType(lastChild, child);
lastChild=child;
while (N--) {
    scanf("%d",&child);
    int tu=getType(lastChild, child);
    if(tu==up)
        n++;
    else {
        q.push(PAIR(n,up));
        n=2;
        up=tu;
    }
    lastChild=child;
}
q.push(PAIR(n,up));
q.push(PAIR(1,1));
/*其实主要就是看转折点是属于上一段还是当前段。
 如果是正V的话，转折点属于后一段。前一段的和-1.
 如果是倒V的话，转折点属于长的一段。
 然后是平的和别的有搭配的话，转折点属于别的
 */
PAIR lastp=q.front();q.pop();
while(q.size()){
    PAIR pir=q.front();q.pop();
    if(pir.up==1){
        result+=calc(lastp.up,lastp.n);//如果下一段是平的，就把转折点分到上一段
        pir.n-=1;
    }
    else if(lastp.up==1){
        result+=calc(lastp.up,lastp.n-1);//如果上一段是平的，就把转折点分到下一段
    } else if((lastp.up==0)&&(pir.up==2)){//如果是倒V型的，转折点属于长的
        if(lastp.n>pir.n){
            result+=calc(lastp.up,lastp.n);
            pir.n-=1;
        } else {
            result+=calc(lastp.up,lastp.n-1);
        }
    } else if((lastp.up==2)&&(pir.up==0)){//如果是正V型的，转折点属于后一个
        result+=calc(lastp.up,lastp.n)-1;
    } else {
        printf("WRONG!");
    }
    lastp=pir;
}
printf("%lld\n",result);
return 0;
}

Answer 4

I used two queues to store increasing and decreasing sequences of unassigned indices and enumerate all possible situations of the adjacent ratings and assign the candies when rating hit a plateau or bottom(i.e. when current rating is local minimum or same as previous).

Here is my solution:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <deque>

void assigncandies(std::deque<int>& incr, std::deque<int>& decr, unsigned int& total) {
  int incrlen = incr.size();
  int decrlen = decr.size();
  if (incrlen >= decrlen) {
    int num=incrlen;
    int last = incr.back();
    while(!incr.empty()) { 
      int idx = incr.back();
      total += num;
      incr.pop_back();
      num --;
    }
    if (!decr.empty()) {
      if (last == decr.front()) decr.pop_front(); 
      num=1;
      while(!decr.empty()) {
       int idx = decr.back();
        //candies[idx]=num;
        total += num;
        decr.pop_back();
          num ++;
      }
    }
  } else {
    int num=decrlen;
    int last = decr.front();
    while (!decr.empty()) {
      int idx = decr.front();
      //candies[idx]=num;
      total += num;
      decr.pop_front();
      num --;
    }
    if (!incr.empty()) {
      if (last == incr.back()) incr.pop_back();
      num=1;
      while(!incr.empty()) {
        int idx = incr.front();
        //candies[idx]=num;
        total += num;
        incr.pop_front();
          num ++;
      }
    }
  }
}

int main () {
  int N;
  unsigned int total=0;
  int PrevR, CurR, NextR;
  std::cin >> N;
  std::deque<int> incr;
  std::deque<int> decr;
  for (int i = 0; i<N;i++) {
    if (i==0) {
      std::cin>>CurR;
      std::cin >> NextR;
    } else if (i != N-1) std::cin >> NextR;

    if (i==0) {
      if (CurR>NextR) decr.push_back(0);
      else if (CurR<NextR) incr.push_back(0);
      else total=1;
    } else if (i==N-1) {
      if (PrevR<CurR) {
        incr.push_back(i);
      }
      if (PrevR>CurR) {
        decr.push_back(i);
      }
      if (PrevR==CurR) {
        total += 1;
      }
      assigncandies(incr,decr,total);
    } else {
      if (PrevR == CurR && CurR == NextR) {
        assigncandies(incr,decr,total);
        total += 1;
      }
      if (PrevR == CurR && CurR < NextR) {
        assigncandies(incr,decr,total);
        incr.push_back(i);
      }
      if (PrevR == CurR && CurR > NextR) {
        assigncandies(incr,decr,total);
        decr.push_back(i);
      }
      if (PrevR < CurR) {
        incr.push_back(i);
        if (CurR > NextR) decr.push_back(i);
      }
      if (PrevR > CurR && CurR >= NextR) {
        decr.push_back(i);
      }
      if (PrevR > CurR && CurR < NextR) {
        decr.push_back(i);
        assigncandies(incr,decr,total);
        total -= 1;
        incr.push_back(i);
      }
    }
    PrevR = CurR;
    CurR = NextR;
  }

  std::cout<<total<<std::endl;
  return 0;
}

It passes the testcases and 3/10 cases correct but I got segmentation fault for the rest.
I am wondering whether anyone can point out what is wrong with my code.
Thank you very much!

Answer 5

Simple working code with an array as input, in Java language. Time Complexity: O(n).

import java.util.Arrays;
public class MyClass {
    public static void main(String[] args) {
        int []childrenRating = {9, 8, 7, 10, 11, 12, 14, 1, 5};
        int []expectedDistribution = {3, 2, 1,  2,  3,  4,  5, 1, 2};
        int []resultingDistribution = new int[childrenRating.length];
        int v = 1;
        int k, j = 0;
        while(j < childrenRating.length){
            k = j;
            if(k >0 && childrenRating[k] == childrenRating[k-1]) { v=1; } 
            resultingDistribution[k] = v;
            while(j+1 < childrenRating.length && childrenRating[j+1] < childrenRating[j]){
                j++;
            }
            v = 1;
            for(int i = j; i > k; i--){
                resultingDistribution[i] = v++; 
            }
            resultingDistribution[k] = Math.max(resultingDistribution[k], v);
            j++;
            v = resultingDistribution[j-1]+1;
        }
        if(Arrays.equals(expectedDistribution, resultingDistribution)) {
            System.out.println("Correct Distribution");
        }
        else {
            System.out.println("Wrong Distribution!");
        }
    }
}

Answer 6

You can do this in two passes. Start with everyone having one candy.

First loop i from 1 to n-1 (zero based), if rating[i] > rating[i-1] then candies[i] = candies[i-1]+1

Then loop i from n-2 to 0; if rating[i] > rating[i+1] then candies[i] = max(candies[i], candies[i+1]+1)

It's pretty easy to show this gives you a valid distribution of candies, since the second loop can't break anything fixed by the first, and all possible rating discrepancies must be caught by one of the two loops. It's not as obvious that this will use the minimum number of candies, but if you examine each assignment closely you can show that the conditions prove a lower bound on the number of candies required (by a particular individual) at each step.