Problem 3 We have p houseplants in planters of various sizes $1, 52,..., Sp. The plants...

 

Transcribed Image Text:

Problem 3 We have p houseplants in planters of various sizes $1, 52,..., Sp. The plants are getting too big and each plant has to be replanted to a larger planter than the one it currently has. The good news is that we have r extra planters of sizes t₁, t₂,..., tr. Is it possible to replant the plants, one at a time, always putting the plant to a larger currently empty planter? Let n = p+r. Design an O(n log n) algorithm which decides whether such replanting is possible. 2 For example, for p = 4 and r = 2 and planters $₁,..., 84 = 1, 4, 3, 2 and t₁, t2 = 5,1 we can first move the plant in the planter of size 4 to the empty planter of size 5, then move the plant in the planter of size 3 to the now-empty planter of size 4, then move the plant in the planter of size 2 to the now-empty planter of size 3, and finally move the plant in the planter of size 1 to the now-empty planter of size 2. (We will be left with two empty planters of size 1 each.) Thus, for the input, the answer is YES. On the other hand, for input p = 3 and r = 1 and planters 81, 82, 83 = 2, 2, 2 and t₁ = 3 the answer is NO. Problem 3 We have p houseplants in planters of various sizes $1, 52,..., Sp. The plants are getting too big and each plant has to be replanted to a larger planter than the one it currently has. The good news is that we have r extra planters of sizes t₁, t₂,..., tr. Is it possible to replant the plants, one at a time, always putting the plant to a larger currently empty planter? Let n = p+r. Design an O(n log n) algorithm which decides whether such replanting is possible. 2 For example, for p = 4 and r = 2 and planters $₁,..., 84 = 1, 4, 3, 2 and t₁, t2 = 5,1 we can first move the plant in the planter of size 4 to the empty planter of size 5, then move the plant in the planter of size 3 to the now-empty planter of size 4, then move the plant in the planter of size 2 to the now-empty planter of size 3, and finally move the plant in the planter of size 1 to the now-empty planter of size 2. (We will be left with two empty planters of size 1 each.) Thus, for the input, the answer is YES. On the other hand, for input p = 3 and r = 1 and planters 81, 82, 83 = 2, 2, 2 and t₁ = 3 the answer is NO.

Answer rating: 100% (QA)

Given p plants and r extra planters the problem is equivalent to finding the smallest size of plante... View the full answer