Editorial for WC '18 Finals J1 - Conditional Contracts


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let's ignore the requirement that the two film widths must be distinct (as using the same film width twice cannot result in employing more actors anyway). Then, each chosen film width might as well be equal to at least one actor's required film width (as it cannot be better to choose a film width required by no actors). This gives us at most N distinct film widths worth considering (W_1, \dots, W_N). We can consider all N^2 pairs of these widths, count how many actors may be employed for each such pair (by iterating over all N actors and counting ones whose requirements have been satisfied), and output the largest of these employment counts.

The time complexity of the above approach is \mathcal O(N^3), which is fast enough given the constraint that N \le 100. It's also possible to solve this problem more efficiently (in as little as \mathcal O(N) time, by using a hash map to tally up the number of actors requiring each film width and then adding together the largest two such actor counts).


Comments

There are no comments at the moment.