PrefixFreeCode
Pilot 2 · 2009-09-29 · by Nickolas
Pilot 2 · 2009-09-29 · by Nickolas · Greedy, Simulation
Problem Statement
Problem Statement
A prefix-free code of size N which uses K characters is a set of N distinct strings such that
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.
- 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.
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.
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)
2
{1,4}
Returns: 5
The cheapest code of size 2 which can be constructed from characters '0' (cost 1) and '1' (cost 4) is simply {"0", "1"}.
1)
3
{1,4}
Returns: 11
The cheapest code of size 3 is {"00","01","1"}.
2)
6
{1,4}
Returns: 35
3)
3
{1,3,5}
Returns: 9
Here exist two cheapest codes - {"0","1","2"} and {"00","01","1"}.
4)
500
{100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100}
Returns: 96000
5)
500
{ 1, 3, 5, 7, 9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99}
Returns: 6780
max character number (#6 too)
7)
500
{96,78,24,94,19,43,53,79,56,55,25,63,76,58,69,96,51,18,34,3,39,90,71}
Returns: 26160
the cases which break greedy (#7 - #11, #13 etc)
79)
500
{100,100}
Returns: 448800
max return value
Submissions are judged against all 93 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PrefixFreeCode with a public method int minCost(int N, vector<int> characterCosts) · 93 test cases · 2 s / 256 MB per case