CareerCup

a simple approach, sort the list with o(NlnN), then pick up alternatively elements from the two ends of the sorted list, you will have:
{highest, lowest, sec highest, sec lowest, third highest, third lowest,.....}
That is it!

This can be solved by topological sort. Build a graph by scanning the rating array from left to right:
g[i][j] = true => c[i] must be less to c[j].

Then we can assign the candies according to the topological order.

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

const int MAXN = 100000;
int g[MAXN][3];
int indeg[MAXN];
int val[MAXN];
int c[MAXN];
int n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> val[i];
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    for (int i = 0; i < n - 1; i++) {
        if (val[i] < val[i + 1]) {
            g[i][++g[i][0]] = i + 1;
            indeg[i + 1]++;
        } else if(val[i] > val[i + 1]) {
            g[i + 1][++g[i + 1][0]] = i;
            indeg[i]++;
        }
    }
    stack<int> sta;
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0) {
            c[i] = 1;
            sta.push(i);
        }
    }
    
    while (!sta.empty()) {
        int r = sta.top();
        sta.pop();
        for (int j = 1; j <= g[r][0]; j++) {
            c[g[r][j]] = max(c[g[r][j]], c[r] + 1);
            indeg[g[r][j]]--;
            if (indeg[g[r][j]] == 0) sta.push(g[r][j]);
        }
    }
    
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += c[i];
    }
    
    cout << ans << endl;
    return 0;
}

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <iostream>
#include <stack>
using namespace std;


const int MAXN = 100000;
int g[MAXN][3];
int indeg[MAXN];
int val[MAXN];
int c[MAXN];
int n;



int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> val[i];
if (n == 1) {
cout << 1 << endl;
return 0;
}
for (int i = 0; i < n - 1; i++) {
if (val[i] < val[i + 1]) {
g[i][++g[i][0]] = i + 1;
indeg[i + 1]++;
} else if(val[i] > val[i + 1]) {
g[i + 1][++g[i + 1][0]] = i;
indeg[i]++;
}
}
stack<int> sta;
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) {
c[i] = 1;
sta.push(i);
}
}

while (!sta.empty()) {
int r = sta.top();
sta.pop();
for (int j = 1; j <= g[r][0]; j++) {
c[g[r][j]] = max(c[g[r][j]], c[r] + 1);
indeg[g[r][j]]--;
if (indeg[g[r][j]] == 0) sta.push(g[r][j]);
}
}

long long ans = 0;
for (int i = 0; i < n; i++) {
ans += c[i];
}

cout << ans << endl;
return 0;
}

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.

Ouput

Output a single line containing the minimum number of candies Alice must give.

Sample Input

3
1
2
2

Sample Ouput

4

Explanation

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

Constraints:

N and the rating of each child are no larger than 10^5.

I think you just sort N kids from lowest to highest score and start giving the candies from 1 and 1+N.

This is an ongoing challenge on InterviewStreet.

//
we have to consider how many kids are in a decreasing rank continuously
on that basis we can scan each kid and allocate no of candy to each student
order goes to o(n2) if all students sit in a sorted order

#include<stdio.h>
#include<conio.h>
int main()
{
    int N,sum=0;;
    printf("enter N : ");
    scanf("%d",&N);
    int a[N];
    int i;
    for(i=0;i<N;i++)
     scanf("%d",&a[i]);
    int prev=0;int preval=0;
    for(i=0;i<N;i++)
     {
          int res=0;          
          int j=i;
         int count=1,flag=0;           
         while(a[j]<=a[j+1] && j!=N-1)
           {if(a[j]==a[j+1]){j++;continue;}else {count++;j++;flag++;}}
           if(flag==0)
           {count=1;res=count;}
          if(a[i]<preval && count<=prev)
           res=prev+1;
          else if(a[i]==preval)
          res=prev;  
           else
            res=count;
           preval=a[i];
           a[i]=res;
           prev=res;  
      } 
      for(int i=0;i<N;i++)
       { printf(" %d ",a[i]);
        sum=sum+a[i];}
       printf("\nMin candy is %d",sum);
       getch();
       return 0;
       }

Assuming the placement of the kids in the line, I would use an iterative method that starts out with every kid receiving one candy, and then looking at the constraints one by one and adjusting until all the constraints are satisfied. This should yield the optimal solution:

vector<int> distribute_candies(const vector<int>& priorities) {
  vector<int> candies(priorities.size());
  fill(candies.begin(), candies.end(), 1);

  vector<int> consistencyChecks;
  for (int i = 0; i < priorities.size()-1; i++) consistencyChecks.push(i);

  while (!consistencyChecks.empty()) {
    int i = consistencyChecks.back();
    consistencyChecks.erase(consistencyChecks.end()-1);
    if (sign(priorities[i]-priorities[i+1]) != sign(candies[i]-candies[i+1]) {
      if (priorities[i] < priorities[i+1]) candies[i]++;
      else candies[i+1]++;

      consistencyChecks.push_back(i);
      if (i+1 < priorities.size()-1) consistencyChecks.push(i+1);
      if (i-1 > 0) consistencyChecks.push(i-1);
    }   
  }
}

If we can arrange the order of the kids, then I would sort the priority list, merging the first half of the list and the second half of the list so that we get a [lo, hi, lo, hi, lo, hi] order, and then distribute the candies as such: [1, 2, 1, 2, 1, 2, ...].

@All : Guys I don't think that sorting and then distributing will give correct answer. Consider following example.

4,3,4 - requires 5 (2+1+2) candies.
As you have said after sorting
3,4,4 - It requires 4 (1+2+1) candies.

The correct answer is 5.

I think this problem can only be solved by using recursion or dynamic programming.

hi all.i have solved alredy this problem from interviewstreet.
my algorithm has greedy approach.
here is my C++ code


/* Enter your code here. Read input from STDIN. Print output to STDOUT */


#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <stdlib.h>

#include <utility>



#include <vector>

#include <deque>

#include <list>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <bitset>



#include <cmath>

#include <complex>

#include <algorithm>



#include <ctime>

#define gtime clock()



using namespace std;



#define REP(i, n) for(int i = 0; i < (n); i++)

#define FOR(i, lo, hi) for(int i = (lo); i <= (hi); i++)

#define FORD(i, hi, lo) for(int i = (hi); i >= (lo); i--)

#define FE(it, cont) for(typeof((cont).begin()) it = (cont).begin(); it != (cont).end(); it++)

#define ALL(cont) (cont).begin(), (cont).end()

#define SZ(cont) (int)((cont).size())

#define PB push_back

#define MP make_pair



template<class T> vector<T> split(const string &s){stringstream ss(s);vector<T> a;T t;while(ss >> t)a.PB(t);return a;}

template<class T> T parse(const string &s){stringstream ss(s);T e;ss >> e;return e;}

template<class T> string toString(const T &e){stringstream ss();ss << e;return ss.str();}



typedef long long int64;

typedef pair<int, int> ii;

typedef vector<int> vi;

typedef vector<ii> vii;

typedef vector<vi> vvi;

typedef vector<string> vs;



const int64 oo = (1ll << 30);

const int MAXN = (int)1e5 + 1;

const int mod = (int)1e9;

const double eps = 1e-9;

const double pi = acos(-1);



int n;

int64 val[MAXN], ans[MAXN];



void update_left(int64 pos)

{

ans[pos--] = 1;

while(pos >= 0 && val[pos] > val[pos + 1])

{

ans[pos] = max(ans[pos], ans[pos + 1] + 1);

pos--;

}

}

void update_right(int64 pos)

{

ans[pos++] = 1;

while(pos < n && val[pos - 1] < val[pos])

{

ans[pos] = max(ans[pos - 1] + 1, ans[pos]);

pos++;

}

}

int main()

{

// freopen ("in.txt", "rt", stdin);

// freopen ("out.txt", "wt", stdout);

cin >> n;

REP(i, n)

cin >> val[i];



bool up = false;

bool down = false;

REP(i, n)

{

if(i + 1 < n && val[i] < val[i + 1] && !up)

{

update_left(i);

update_right(i);

up = true;

down = false;

}

if(i + 1 < n && val[i] > val[i + 1])

{

up = false;

down = true;

}

if(i + 1 < n && val[i] == val[i + 1])

{

if(down)

update_left(i);

up = false;

down = false;

}

}

if(!up)

{

update_left(n - 1);

}

int64 total = 0;

REP(i, n)

{

if(!ans[i])

ans[i] = 1;

total += ans[i];

}

//REP(i, n)cout << ans[i] << ' ';cout << endl;

cout << total << endl;

//system("pause");

return 0;

}

This can be solved in O(n) time. I think my solution in principle matches with the topological sorting idea.

The idea is to observe that the exact ranking of a student does not matter, but with respect to his next neighbors (whose candies in turn are decided by their next neighbors, and so on). So, it is sufficient to give the number of candies to a student, equal to maximum of the lengths of ever decreasing contiguous subsequence (of rankings) on his/her left and to his/her right, counted starting from him. Here "strictly increasing" or "strictly decreasing" is very import ant to minimize the candies.

Example: for students lined-up according to the rankings 1, 3, 3, 4, 5, 4, 3, 1
the third student has no other students on his left with ever decreasing rankings (starting from him) and no students on his right, so he receives max(0, 0) + 1(minimal candy) = 1 candies, and so on.

The algorithm does exactly the same:
1. let fromLeft[i] and fromRight[i] be the arrays holding lengths of ever decreasing contiguous subset including i'th element on left and right,
2. traverse the rankings from left to right and fill up fromLeft, with the formula

fromLeft[i] = fromLeft[i-1] + 1;

whenever ranking[i-1] < ranking[i]
3. traverse the rankings from right to left to similarly setup fromRight
4. The candies to a student at position i is

candies[i] = max{fromLeft[i] , fromRight[i]} + 1;    // 1 for the minimal candy

5. output the sum in candies

Step 4 and 5 can be combined (as done in the code below). One does not need to save number of candies to each person, if only the minimal is required, saving O(n) space

// Calculate minimal number of candies required
int getMinimalCandies(const std::vector<double>& rankings, std::vector<int>& candies){
    
    // number of students
    int numStudents = (int) rankings.size();
    
    // ever decreasing contiguous subsequence
    // from every position to its right (left)
    std::vector<int> onLeft(numStudents, 0), onRight(numStudents, 0);
    
    // for each position, determine ever decreasing
    // seq. on the left and on right
    for (int i = 0; i < numStudents; i++) {
        
        // if the ranking on immediate left was
        // higher than this one
        if (i &&                           // don't do it for i = 0
            rankings[i-1] < rankings[i]) {
            // length of subsequence at this
            // position is one more than the previous one
            onLeft[i] = onLeft[i-1] + 1;
        }
        // similarly for decreasing ranking seq. on right
        if ( (((numStudents - 1) - i) < numStudents - 1) &&
            rankings[((numStudents - 1) - i) + 1] < rankings[(numStudents - 1) - i]) {
            onRight[(numStudents - 1) - i] = onRight[((numStudents - 1) - i) + 1] + 1;
        }
        
        //
        
    }
    
    // candies to be given to every child is
    // max-length(increasing seq. on left, decreasing seq. on right)
    int totalCandies(0);
    for (int i = 0; i < numStudents; i++){
        candies[i] = std::max(onLeft[i], onRight[i]) + 1;
        totalCandies += candies[i];
    }
        
    // return total number of candies to be distributed
    return totalCandies;
}

// API, from main
std::cout << "The total number of minimal candies required are " << getMinimalCandies(rankings, candies) << std::endl;
    
    // print individual candies (optional)
    std::cout << "Distribute as ";
    for (int i= 0; i < n; i++)
        std::cout << candies[i] << "\t";
    std::cout << std::endl;

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;
}

int score[]={2,4,2,6,1,7,8,9,2,1};
	int chocs[]=new int[score.length];
        chocs[0]=1;
        
        for(int i=1;i<score.length;i++){
        	if(score[i]>score[i-1]){
        		chocs[i]=chocs[i-1]+1;
        	}
        	else if(chocs[i-1]==1){
        		chocs[i]=1;
        		for(int j=i-1;j>=0;j--){
        			if( score[j] > score[j+1] )
                        chocs[j] = Math.max(chocs[j+1] + 1,chocs[j] );
                    else
                        break;
        		}
        	}
        	else{
        		chocs[i]=1;
        	}
        }
		
        int sum=0;
        for(int i=0;i<chocs.length;i++){
        	sum+=chocs[i];
        }
        System.out.println(sum);

int score[]={2,4,2,6,1,7,8,9,2,1};
		int chocs[]=new int[score.length];
        chocs[0]=1;
        
        for(int i=1;i<score.length;i++){
        	if(score[i]>score[i-1]){
        		chocs[i]=chocs[i-1]+1;
        	}
        	else if(chocs[i-1]==1){
        		chocs[i]=1;
        		for(int j=i-1;j>=0;j--){
        			if( score[j] > score[j+1] )
                        chocs[j] = Math.max(chocs[j+1] + 1,chocs[j] );
                    else
                        break;
        		}
        	}
        	else{
        		chocs[i]=1;
        	}
        }
		
        int sum=0;
        for(int i=0;i<chocs.length;i++){
        	sum+=chocs[i];
        }
        System.out.println(sum);

A simple DP solution

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    if(n==1)
        return 1;
    int arr[n],dp[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
        dp[i]=1;
    }
    int sum=0;{
        for(int i=1;i<n;i++){
            if(arr[i]>arr[i-1]){
                    dp[i]+=dp[i-1];
            }
            else{
                if(dp[i-1]==1)
                for(int j=i-1;j>=0;j--){
                    if(arr[j]>arr[j+1])
                    dp[j]=max(dp[j+1]+1,dp[j]);
                    else
                        break;
                }
            }
        }
        for(int i=0;i<n;i++){
            sum+=dp[i];
            //cout<<dp[i]<<" ";
        }
        cout<<sum;
    }    
    return 0;
}

A Simple DP Solution

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    if(n==1)
        return 1;
    int arr[n],dp[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
        dp[i]=1;
    }
    int sum=0;{
        for(int i=1;i<n;i++){
            if(arr[i]>arr[i-1]){
                    dp[i]+=dp[i-1];
            }
            else{
                if(dp[i-1]==1)
                for(int j=i-1;j>=0;j--){
                    if(arr[j]>arr[j+1])
                    dp[j]=max(dp[j+1]+1,dp[j]);
                    else
                        break;
                }
            }
        }
        for(int i=0;i<n;i++){
            sum+=dp[i];
            //cout<<dp[i]<<" ";
        }
        cout<<sum;
    }    
    return 0;
}

hi

zsklg'lkaen'g;a
va arw r
gtaesrgesrdf