This is a friendly reminder on the class policy regarding the use of GenAI on programming assignments in this course. While you may use GenAI to do the equivalent of looking up known information on the web / in a manual, you may NOT use GenAI to generate the solution to any part of this programming assignment. The purpose of the assignment is to practice your problem solving and programming implementation skills on your own. If we find that you have copied significant code generated by AI for this programming assignment, this will be considered an honor violation.
You have been hired by Daycare Strategies and Associates (DSA), who are the experts in optimizing the costs and risks involved in daycare programs for young children around the country. Many of the DSAs clients want to renovate their facilities but are faced with a problem: Where will we put the children temporarily while we renovate classrooms and how much will that cost?
This is where you come in. When a daycare wants to renovate, you decide that the best strategy is to renovate one classroom at a time. The daycare has n rooms each with a capacity of Ci (given the index i of that room). We will assume for simplicity that the daycare is currently completely full (hence the need for a renovation). In addition, each classroom has its current capacity Ci (as previously mentioned) and once renovated, each classroom will have a new capacity Ni. Note that this new capacity might be larger, the same, or smaller compared to the pre-renovated room.
You plan to purchase a temporary trailer to house each classroom one at a time during the renovation process. The trailer company is called the Classroom Space Organizers (CSO… boo!). CSO charges a fixed amount per child capacity of the trailer. While one room is being renovated, you will move the students into the trailer temporary. Notice that if the classroom that was renovated now has a larger capacity, you can move some children from a different class into the renovated room so that fewer children need to stay in the trailer (see example below)
Write a program that does the following: Given the classrooms in the daycare and the starting / ending capacities of each, what is the smallest capacity trailer that you need to purchase in order to have enough extra space to renovate each classroom?
Let’s look at an example. Suppose the daycare has four rooms A, B, C, and D with capacities 6, 1, 3, and 3 (specifically, C={6,1,3,3}). The new capacities after renovating each room will become 6, 7, 5, and 5 respectively (N={6,7,5,5}). If you buy a trailer with a capacity of 1 child, you can move the one child from room B there and renovate that classroom; after the renovation, that room’s new capacity becomes 7. For the next renovation, you can keep that one child in the trailer, move 6 children into room B while you renovate room A. You can then continue to use room B as extra space while renovating rooms C and D. Notice that for this problem 1) children do NOT need to end up in the same room they started in after the renovation is finished and 2) you may no longer have enough space to hold all of the original children and the extra trailer may need to become permanent (we’ll call this case one of terrible planning on the daycare’s part).
The first line of the input will be the number of test cases in the file. THIS IS AN UPDATE
Each test case begins with a line containing one integer n (1≤n≤106), which is the number of rooms in your daycare. Following this are n lines, each describing a room as two integers Ci and Ni, the capacity of each room currently and the capacity of that room after remodeling.
For each test case, display the total extra capacity (in number of children) you must purchase for the trailer (print this value on a line by itself).
This input is available as example.in.
2
4
6 6
1 7
3 5
3 5
4
2 2
3 3
5 1
5 10
1
5
For this (and future) assignments, you will need to develop all of your code from scratch on your own.
The solution must be some kind of greedy algorithm. Make sure to create many test cases to test your different approaches as you develop them. It is possible that you will need multiple greedy strategies and switch between them as you progress. Think about the total amount of extra space you have in the daycare to work with…you want this to be as large as possible, right?
The submission system can handle four different programming languages. For each programming language, the name of the submitted file is listed below (you have to have it named that exact name, else it will not compile properly). If you want to program in a different language, email the course email at least three days before it is due (as we have to reconfigure the autograder).
You will submit your completed source code file to Gradescope. There will be a small set of acceptance tests that are NOT COMPREHENSIVE. These acceptance tests are the test cases in the example.in file. It’s up to you to comprehensively test your code. The acceptance tests just verify that you are reading the input correctly and providing the expected output.
Note that when you submit, Gradescope will report your grade as “-/10” or “0/10” – that’s a quirk of Gradescope, and is because the grading tests have not been run (and won’t be run until after all submissions are in). You can look at the results of the individual test cases to see how your program worked