TSECJ03 - Editorial

easy
editorial
sets

#1

PROBLEM LINK:

Contest link

Editorialist: Kaustubh Khavnekar

DIFFICULTY:

Easy

PREREQUISITES:

Set theory

PROBLEM:

Matt’s factory has X types of chocolates manufactured, he wants to buy another factory such that types of chocolate (and not the quantity) manufactured by his company is maximised.

QUICK EXPLANATION:

Express types of chocolates manufactured as sets, and find union with maximum cardinality.

EXPLANATION:

The types of chocolate manufactured by a factory can be modelled as a set. For example, if list of machines in a factory is 4 2 2 3 , the set for that factory is {4,2,3}. Make a set of types of chocolate manufactured by Matt’s factory. Similarly make a set of types of chocolate manufactured by every other factory. Find union of each of these sets with Matt’s set, the required factory will be the one with maximum union set cardinality (number of elements of the set). If more than one factory has the same cardinality which is the maximum, choose the factory with lower identification number, as stated.

SOLUTION:

C++ solution
Java solution