CDX1605 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Puneet Gupta
Editorial: Puneet Gupta

DIFFICULTY:

EASY

PREREQUISITES:

GREEDY, IMPLEMENTATION

PROBLEM:

Our task is to take largest amount of toys Riku doesn’t have such that the sum of their costs doesn’t exceed M.

EXPLANATION:

To do this, one can perform greedy algorithm: let’s buy the cheapest toy that Riku doesn’t have at every step, while the amount of money left is sufficient to do that.

A boolean array can be used as a handle, storing true values, in indices equal to the type of toys which Riku already has.

So we just need to iterate over our handle and check if corresponding value for a given index is equal to false, we should buy it, otherwise we can’t.

The solution complexity is O(n + \sqrt{m}).

One can use the <> data structure (C++ \texttt{std::set}, for example), for storing the types Riku has at the moment. In this case the complexity is O(n + \sqrt{m} log(n)).

AUTHOR’S SOLUTION:

Author’s solution can be found here.