This is a C++ Program that Solves Alice Kindergarden Candies Problem using Dynamic Programming method.
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.
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.
Case-1:
number of children, n=3 ratings of children, r[]=1, 2, 2 Minimum number of candies alice must buy=4
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;
}
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.
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.
- Practice Design & Analysis of Algorithms MCQ
- Apply for Data Structure Internship
- Practice Programming MCQs
- Apply for Information Technology Internship
- Practice Computer Science MCQs