Minimum Candy Distribution Problem

Design and Analysis of Algorithms - Dynamic Programming

1. The Candy Distribution Problem
Dynamic programming
15Z403 -Design and Analysis of Algorithms

2. PROBLEM
STATEMENT
Alice is a kindergarten teacher. She wants to give some candies
to the children in her class. All the children sit in a line and
eachof themhas 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
minimize the total number of candies she must buy.
This above problem is to be solved using Dynamic Programming.
2

3. Design Technique Used
Dynamic Programming
Dynamic Programming is an algorithmic paradigm that solves a given complex
problem by breaking it into subproblemsand stores the results of subproblems to
avoid computing the same results again.
3

4. “
Dynamic programming is applicable to our problem as it has the following properties:
(Optimisation and Overlapping sub-problems)
•It can be partitioned into subproblems.
•Subproblems can be solved independently,
•Solutions (optimal) of the subproblems can be combined to (optimal) solutions of the
original problem.
•Subproblems have the same property (or are trivial).
4

5. How dynamic
programming is
used?
1. In Dynamic Programming questions, we are asked to calculate F[i] for some i. Here, F[i] is
the number of candies given to child i. (Then we sum the values.) The complexity is that the
value F[i] depends on other values, in this case for values of i both smaller and larger.
2. We are calculating candies[i] (number of candies given to child i) in an order such that the
“dependencies” (number of candies given to the child-i’s neighbours) for a given value i have
already been calculated. (Tabulation).
3. Problem is split into further subproblems whenever duplicates are found in consecutive
locations.
Example : ratings = [ 2 3 4 5 2 2 7 8 ]
It is divided into 2 sub problems as
•[ 2 3 4 5 2 ]
•[ 2 7 8 ]
And their optimal sub-solutions are combined to get optimal solution. (Minimumnumber of
candies).
5

6. N -Number of children.
ratings[1:N]-Array that contains ratings of N children.
candy_count-Contains the minimum number of candies.
is_min(ratings, j)-Checks if the element at position j is a local minimum.
is_max(ratings, j)-Checks if the element at position j is a local maximum.
find_next_min(ratings, i)-Finds the next local minimum after position i.
find_next_max(ratings, i)-Finds the next local maximum after position i.
Algorithm Candies :
6

7. Begin
1. Read N.
2. Set prev_repeat = 0, candy_count = 0.
3. Read ratings of n children one by one
2.1 If there are consecutive duplicates, at position i-1, i :
2.2.1 call num_candies(ratings[prev_repeat: i])
2.2.2 prev_repeat = i
4. candy_count = candy_count + num_candies(ratings[prev_repeat: n])
End
Algorithm Candies :
7

8. 1. If number of children = 1, then return 1.
2. Initialize candies[] to zero (all N values).
3. Find first min (next_min) and set candies to 1
4. If the first element is a max, (not a min)
4.1 Iterate from next_min to 0 in reverse
4.1.1 set candies[i] = candies[i+1] + 1
5. Set prev_min = next_min and find new next_min and next_max.
Algorithm num_candies(ratings):
8

9. 6. While there is still another min and another max
6.1 candies[next_min] = 1
6.2 Iterate from prev_min to next_max in steps of 1
6.2.1 candies[i] = candies[i -1] + 1
6.3 Iterate from next_min to next_max in steps of -1
6.3.1 candies[i] = candies[i + 1] + 1
6.4 candies[next_max] = max(candies[next_max -1], candies[next_max + 1]) + 1
6.5 Same as Step 5
7. If next_max is the last element
7.1 Iterate from prev_min to next_max in steps of -1
7.1.1 candies[i] = candies[i -1] + 1
7.1.2 candies[next_max] = candies[next_max -1] + 1
8. return sum of candies[]
Algorithm num_candies(ratings)
9

10. Ratings[i]35Ratings[i]5191078
Candies[i]00Candies[i]000000
By Step 310By Step 3010000
By Step 712By Step 4210000
By Step 6.1210010
By Step 6.2212010
By Step 6.4212310
By Step 7212312
Sum = 3 Sum = 11
Sum = 3+11 = 14
Tracing

11. defis_min(ratings,j):
# Checks if the element at position j is a local minimum
ifj ==0:
returnratings[0]<ratings[1]
elifj ==len(ratings)-1:
returnratings[j -1]>ratings[j]
else:
returnratings[j -1]>ratings[j]andratings[j]<ratings[j +1]
defis_max(ratings,j):
# Checks if the element at position j is a local maximum
ifj ==0:
returnratings[0]>ratings[1]
elifj ==len(ratings)-1:
returnratings[j -1]<ratings[j]
else:
returnratings[j -1]<ratings[j]andratings[j]>ratings[j +1]
Source Code -Implementation using Python 3
11

12. deffind_next_min(ratings,i):
# Finds the next local minimum after position i
ifi ==None:
returnNone
forj inrange(i +1,len(ratings)):
ifis_min(ratings,j):
returnj
returnNone
deffind_next_max(ratings,i):
# Finds the next local maximum after position i
ifi ==None:
returnNone
forj inrange(i +1,len(ratings)):
ifis_max(ratings,j):
returnj
returnNone
Source Code
12

13. defnum_candies(ratings):
iflen(ratings)==1:
return1
candies =[0]*len(ratings)
# Find first min and set candies to 1
next_min =find_next_min(ratings,-1)
candies[next_min]=1
# If the first element is a max, not a min
ifnext_min !=0:
fori inrange(next_min -1,-1,-1):
candies[i]=candies[i +1]+1
# Find next min and max
prev_min =next_min
next_max =find_next_max(ratings,prev_min)# next_max after prev_min
next_min =find_next_min(ratings,next_max)# next_min after next_max
Source Code
13

14. # While there is still another min and another max
whilenext_min andnext_max:
candies[next_min]=1
# Iterate inward from mins to max
fori inrange(prev_min +1,next_max):
candies[i]=candies[i -1]+1
fori inrange(next_min -1,next_max,-1):
candies[i]=candies[i +1]+1
# Set candies of max
candies[next_max]=max(candies[next_max -1],candies[next_max +1])+1
Source Code
14

15. # If next_max is the last element
ifnext_max:
fori inrange(prev_min +1,next_max):
candies[i]=candies[i -1]+1
candies[next_max]=candies[next_max -1]+1
returnsum(candies)
# Main Program
N = int(input())
ratings = [int(input())]
candy_count = 0
prev_repeat = 0
fori inrange(1, N):
ratings.append(int(input()))
ifratings[i] == ratings[i -1]:
candy_count += num_candies(ratings[prev_repeat: i])
prev_repeat = i
candy_count += num_candies(ratings[prev_repeat:])
print(candy_count)
Source Code
15

16. Output -Minimum number of Candies
16
Output -(i)
Output -(ii)

17. O(n)
Time Complexity
In the num_candies function, the each of the loops run not more than ntimes in the worst
case, (where n is the number of children) and hence the time taken is linear.
17

18. Thanks!
Presentation by
Preethi S V (17z231)
Sivakami N (17z245)
Varsha Devi K (17z256)
Samyuktha G (17z238)
Tejaswini Sivakumar (17z253)
18