TopCoder problem "PrefixFreeCode" used in Pilot 2 (Division I Level Three)



Problem Statement

    A prefix-free code of size N which uses K characters is a set of N distinct strings such that
  • each string of the set contains only characters '0','1', ..., ('0'+K-1)
  • no string of the set is a prefix of any other string of the set.
The cost of a prefix-free code can be calculated as sum of costs of characters used to write down all strings of the set.

You are given the size of the code N and the costs of using the characters characterCosts. Return the minimal possible cost of a prefix-free code of size N which uses these character costs.
 

Definition

    
Class:PrefixFreeCode
Method:minCost
Parameters:int, int[]
Returns:int
Method signature:int minCost(int N, int[] characterCosts)
(be sure your method is public)
    
 

Constraints

-N will be between 2 and 500, inclusive.
-characterCosts will contain between 2 and 50 elements, inclusive.
-Each element of characterCosts will be between 1 and 100, inclusive.
 

Examples

0)
    
3
{1,4}
Returns: 11
The cheapest code of size 3 is {"00","01","1"}.
1)
    
3
{1,3,5}
Returns: 9
Here exist two cheapest codes - {"0","1","2"} and {"00","01","1"}.
2)
    
500
{ 2, 4, 6, 8,10,12,14,16,18,20,
 22,24,26,28,30,32,34,36,38,40,
 42,44,46,48,50,52,54,56,58,60,
 62,64,66,68,70,72,74,76,78,80,
 82,84,86,88,90,92,94,96,98,100}
Returns: 9464
3)
    
500
{1,2,3,4,5,6,7,8,9,10}
Returns: 4732

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13952&pm=10419

Writer:

Nickolas

Testers:

Rustyoldman , timmac , it4.kp , StevieT , vexorian

Problem categories:

Greedy, Simulation