TopCoder problem "Collector" used in TCHS SRM 23 (Division I Level Three)



Problem Statement

    

Victor travels around the world collecting coins. He is now in Surria and he would like to obtain at least one of each kind of Surrian coin. He is at a cash machine, and he only has time to make a single withdrawal before he has to leave. It is unknown how the machine determines which coins to return, so Victor must withdraw an amount that guarantees his goal.

You are given a int[] coins containing the values of each kind of Surrian coin. Note that multiple kinds of coins might actually have the same value, in which case, he still needs to get one of each kind (see example 3). Return the minimal sum that Victor must withdraw from the cash machine to receive at least one of each kind, or -1 if it is impossible. Assume that the machine carries an infinite supply of each kind of coin.

 

Definition

    
Class:Collector
Method:minimalSum
Parameters:int[]
Returns:int
Method signature:int minimalSum(int[] coins)
(be sure your method is public)
    
 

Constraints

-coins will contain between 1 and 50 elements, inclusive.
-Each element of coins will be between 1 and 10000, inclusive.
 

Examples

0)
    
{1,2}
Returns: -1
It is impossible to guarantee that he will receive a "2" coin. Any sum can be achieved using only "1" coins.
1)
    
{1}
Returns: 1
2)
    
{5781,5744,8980,5092,5396,6938,1674,4260}
Returns: 43865
3)
    
{1,1}
Returns: -1
The cash machine might give only the first type of "1" coin.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6734

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10075&pm=6734

Writer:

VitalyGoldstein

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming