Candies Distribution Problem

This is a C++ Program that Solves Alice Kindergarden Candies Problem using Dynamic Programming method.

Problem Description

Alice is a kindergarden teacher. She wants to give some candies to the children in her class.
All the children sit in a line ( their positions are fixed), and each of them has a rating score according to his or her performance in the class.
Alice wants to give at least 1 candy to each child. If two children sit next to each other, then the one with the higher rating must get more candies.
Alice wants to save money, so she needs to minimize the total number of candies given to the children.

Problem Solution

In this problem, every child should be given atleast one candy. For two adjacent children, one with the higher rating should be given more candies.

Expected Input and Output

Case-1:

number of children, n=3
ratings of children, r[]=1, 2, 2
 
Minimum number of candies alice must buy=4

Program/Source Code

Here is source code of the C++ Program to solve Alice Kindergarden Candies Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
int findSolution(vector<int> &ratings)
```
```
{
```
```
    int size = ratings.size();
```
```
    if(size==0)
```
```
        return 0;
```
```
 
```
```
    vector<int> leftToRight(size);
```
```
    vector<int> rightToLeft(size);
```
```
    int sum;
```
```
 
```
```
    leftToRight[0] = 1;
```
```
    for(int i=1;i<size;i++)
```
```
    {
```
```
        if(ratings[i]>ratings[i-1])
```

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

```
 
```
```
        else
```
```
            leftToRight[i] = 1;
```
```
    }
```
```
 
```
```
    sum=leftToRight[size-1];
```
```
    rightToLeft[size-1] = 1;
```
```
 
```
```
    for(int i=size-2;i>=0;i--)
```
```
    {
```
```
        if(ratings[i]>ratings[i+1])
```

            rightToLeft[i] = rightToLeft[i+1]+1;

```
 
```
```
        else
```
```
            rightToLeft[i] = 1;
```
```
 
```

        sum+=(leftToRight[i]>rightToLeft[i]?leftToRight[i]:rightToLeft[i]);

```
    }
```
```
 
```
```
    return sum;
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int n,i;
```

    cout<<"Enter the number of children ";

```
    cin>>n;
```
```
 
```
```
    vector<int> a(n);
```

    cout<<"Enter the rating of each child"<<endl;

```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>a[i];
```
```
    }
```
```
 
```

    cout<<"The Minimum number of candies Alice must buy is "<<endl;

```
    cout<<findSolution(a)<<endl;
```
```
 
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we take input for number of children and ratings of each child. These values are passed as arguments to the function findSolution. The final solution is returned by this function and displayed on the standard output.

Runtime Test Cases

 
Case-1:
<pre lang="text" cssfile="hk1_style">
$ g++ alice.cpp 
$ ./a.out
Enter the number of children 3
Enter the rating of each child
1 2 2
The Minimum number of candies Alice must buy is 
4

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

Free 30-Day Java Certification Bootcamp is Live. Join Now!

« Prev - Triangle Problem using Dynamic Programming

» Next - Double Helix Problem – Dynamic Programming Solutions

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Practice Computer Science MCQs
Practice Programming MCQs
Check Programming Books
Apply for Computer Science Internship

Recommended Articles: