PROBLEM LINK:
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.