Because most students find the instructor intimidating^{1}, he has resorted to all sorts of crazy tricks in an attempt at being more inclusive and making his office a more welcoming place. For instance, to make sure CSE majors feel at home, he keeps the lights off in his office ^{2} and plays soft folk or indie music ^{3}. Moreover, he often has candy stocked in the R2D2 and BB8 containers on his desk ^{4}.
Unfortunately, a problem has arisen: too many students are now showing up to his office and eating the candy. Because he wants to reward his favorites^{5}, he has decided to give each student a rating^{6} and distributes candies to each student based on this number.
As a big believer in the important of Data Structures, he has visiting students line up in a queue and distributes the candy to the students such that the following constraints are met:
Every student gets at least one candy.
Every student whose rating is greater than their neighbors in the queue should receive more candy.
For example, suppose the following students were in the office hours queue:
Zephan, Mike, Emory
The instructor may rate the students as:
1, 0, 2
To meet the constraints above, this means he must at least give Zephan
2
candies, Mike 1
candies, and Emory 2
candies, for a total of 5
candies.
After devising this candy distribution scheme, the instructor has become distracted with Clash Royale and asks you to write the code to determine what is the minimum number of candies he needs to distribute given a queue of students and their corresponding ratings.
You will be given a series of test inputs where each line consists of a
queue of n
students (where 1 <= n <= 1000
) and their
corresponding ratings (where 1 <= rating <= 20
).
You should read and process each line of input until the end of the file.
1 0 2
1 2 2
1 3 2 2 1
For each queue of students and their ratings, output the minimum number of candies you need to distribute to the students to ensure that you meant the constraints above in the following format:
{Student Queue #}. You need {Minimum # of candies} candies.
1. You need 5 candies.
2. You need 4 candies.
3. You need 7 candies.
This is based on the 135. Candy problem on LeetCode.
For each input test case, your solution should have the following targets:
Time Complexity | O(N) where N is the number of ratings. |
Space Complexity | O(N) where N is the number of ratings. |
Your solution may be below the targets, but it should not exceed them.
To submit your work, follow the same procedure you used for Reading 00:
$ cd path/to/cse-30872-fa22-assignments # Go to assignments repository
$ git checkout master # Make sure we are on master
$ git pull --rebase # Pull any changes from GitHub
$ git checkout -b challenge10 # Create and checkout challenge10 branch
$ $EDITOR challenge10/program.cpp # Edit your code
$ git add challenge10/program.cpp # Stage your changes
$ git commit -m "challenge10: done" # Commit your changes
$ git push -u origin challenge10 # Send changes to GitHub
To check your code, you can use the .scripts/check.py
script or curl:
$ .scripts/check.py
Checking challenge10 program.cpp ...
Result Success
Time 0.06
Score 6.00 / 6.00
$ curl -F source=@challenge10/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa22/challenge10
{"result": "Success", "score": 6, "time": 0.06372570991516113, "value": 6, "status": 0}
Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 05 TA List.