Satya is in charge of establishing a new testing center for the Standardized AwesomenessTest (SAT), and found an old conference hall that is perfect. The conference hall has nrooms of various sizes along a single long hallway, numbered in order from 1 through n.Satya knows exactly how many students fit into each room, and he wants to use a subsetof the rooms to host as many students as possible for testing.Unfortunately, there have been several incidents of students cheating at other testingcenters by tapping secret codes through walls. To prevent this type of cheating, Satya canuse two adjacent rooms only if he demolishes the wall between them. The city’s chiefarchitect has determined that demolishing the walls on both sides of the same room wouldthreaten the building’s structural integrity. For this reason, Satya can never host studentsin three consecutive rooms.Describe an efficient algorithm that computes the largest number of students that Satyacan host for testing without using three consecutive rooms. The input to your algorithm isan array S[1 .. n], where each S[i] is the (non-negative integer) number of students thatcan fit in room i
Question
Satya is in charge of establishing a new testing center for the Standardized AwesomenessTest (SAT), and found an old conference hall that is perfect. The conference hall has nrooms of various sizes along a single long hallway, numbered in order from 1 through n.Satya knows exactly how many students fit into each room, and he wants to use a subsetof the rooms to host as many students as possible for testing.Unfortunately, there have been several incidents of students cheating at other testingcenters by tapping secret codes through walls. To prevent this type of cheating, Satya canuse two adjacent rooms only if he demolishes the wall between them. The city’s chiefarchitect has determined that demolishing the walls on both sides of the same room wouldthreaten the building’s structural integrity. For this reason, Satya can never host studentsin three consecutive rooms.Describe an efficient algorithm that computes the largest number of students that Satyacan host for testing without using three consecutive rooms. The input to your algorithm isan array S[1 .. n], where each S[i] is the (non-negative integer) number of students thatcan fit in room i
Solution
The problem can be solved using dynamic programming. Here is a step-by-step description of the algorithm:
-
Initialize an array dp[0 .. n] where dp[i] is the maximum number of students that can be hosted in the first i rooms. Set dp[0] = 0, dp[1] = S[1], and dp[2] = max(S[1], S[2]).
-
For each i from 3 to n, compute dp[i] as the maximum of dp[i-1] (which represents not using room i) and dp[i-2] + S[i] (which represents using room i and therefore not using room i-1).
-
The maximum number of students that can be hosted is then dp[n].
This algorithm runs in O(n) time and uses O(n) space. It ensures that no three consecutive rooms are used by considering for each room whether it is better to use it (and therefore not use the previous room) or not use it (and therefore potentially use the previous room).
Similar Questions
Jamal's introductory psychology class is held in Room A. For the final exam, the students in Jamal's class are divided among Rooms A, B, and C. Jamal's memory for the material is likely to be best if he takes the test in which room?A.Room AB.the largest of the three roomsC.the smallest of the three roomsD.the room most different from Room AE.Where Jamal takes the test is not relevant to his ability to remember the material.
All of the following are examples of cheating EXCEPT:Giving a peer answers to the test questionsGiving your feedback to a peerLyingTaking or receiving copies of solutions from someone elseI don't know
There are two examination rooms, A and B. If 10 students are sent from A to B, then the number of students in each room is the same. If 20 candidates are sent from B to A, then the number of students in A is double the number of students in B. The number of students in room A is
If a VIP, for example, always wants the same room, what is the command (checkbox) that allows him to be assigned and guaranteed this room?
There are two examinations rooms C and D. If 10 students are sent from C to D, then the number of students in each room is the same. If 20 candidates are sent from D to C, then the number of students in C is thrice the number of students in D. The number of students in room C is:Question 20Answera.70b.60c.100d.50
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.