Alice Kindergarten Candies Problem using Dynamic Programming

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


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.

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int findSolution(vector<int> &ratings)
  5. {
  6.     int size = ratings.size();
  7.     if(size==0)
  8.         return 0;
  10.     vector<int> leftToRight(size);
  11.     vector<int> rightToLeft(size);
  12.     int sum;
  14.     leftToRight[0] = 1;
  15.     for(int i=1;i<size;i++)
  16.     {
  17.         if(ratings[i]>ratings[i-1])
  18.             leftToRight[i] = leftToRight[i-1]+1;
  20.         else
  21.             leftToRight[i] = 1;
  22.     }
  24.     sum=leftToRight[size-1];
  25.     rightToLeft[size-1] = 1;
  27.     for(int i=size-2;i>=0;i--)
  28.     {
  29.         if(ratings[i]>ratings[i+1])
  30.             rightToLeft[i] = rightToLeft[i+1]+1;
  32.         else
  33.             rightToLeft[i] = 1;
  35.         sum+=(leftToRight[i]>rightToLeft[i]?leftToRight[i]:rightToLeft[i]);
  36.     }
  38.     return sum;
  39. }
  41. int main()
  42. {
  43.     int n,i;
  44.     cout<<"Enter the number of children ";
  45.     cin>>n;
  47.     vector<int> a(n);
  48.     cout<<"Enter the rating of each child"<<endl;
  49.     for(i=0;i<n;i++)
  50.     {
  51.         cin>>a[i];
  52.     }
  54.     cout<<"The Minimum number of candies Alice must buy is "<<endl;
  55.     cout<<findSolution(a)<<endl;
  57.     return 0;
  58. }
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
<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 

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

Note: Join free Sanfoundry classes at Telegram or Youtube

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.