Amazon often gives free products to customers in return for their reviews. At this time there is a set P of different products to review. The person writing a review should be knowledgeable about the product. There is a finite set X of possible properties that products can have, for example, “tech gadget”, “fashion item” (a product can have more than one of these properties). The set of properties of product pi is Xi ⊆ X. In the pool C of “trusted” customers among which Amazon chooses its reviewers, each customer ck, k = 1, . . . , |C| is known to be competent about certain set Yk ⊆ X of these properties (say knows about fashion, or knows about gadgets, or even about both). Customer ck is eligible to review product pi if he/she is competent about at least one of its properties. Amazon determined some numbers r1, . . . , r|P| such that about product pi it wants ri reviews. Find an algorithm to assign products to customers, so that each customer reviews at most one product while all the requirements are met. If this is impossible then the algorithm should report so.

Answer rating: 100% (QA)

Since there is a finite set of products to review we can first create a count array of size P where ... View the full answer