Statistics

Problem Statement for "PrefixFreeCode"

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

  1. 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"}.

  2. 3

    {1,4}

    Returns: 11

    The cheapest code of size 3 is {"00","01","1"}.

  3. 6

    {1,4}

    Returns: 35

  4. 3

    {1,3,5}

    Returns: 9

    Here exist two cheapest codes - {"0","1","2"} and {"00","01","1"}.

  5. 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

  6. 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

    { 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

  8. 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)

  9. 499

    {9,54,40,27,38,53,86,84,65,10,5,85,100,90,63,2,26,70,78,75,75,43,6,87,66,83,34,9,7,100,61,5,56,88,74,79,82,50,14,73,51,52,89,71,59,13,83,77,15}

    Returns: 8368

  10. 456

    {56,1,1,93,22,65,4,89,67,22,15,64,10,21,65,74,7,46,59,11,10,41,1,93,19,52,94,27,31,65,76,56,90,42,12,35,54,7,36,93,84,64,53,95,58,19,42,65,25,91}

    Returns: 2586

  11. 194

    {42,17,82,55,22,72,34,86,50,100,94,36,29,8,3,10,46,64,23,22,44,24,73,29,99}

    Returns: 5553

  12. 383

    {91,91,100,92,64,83,74,31,57,61,74,21,90,16,89,81,98,41,31,55,35,62,53,55,8,48,54,60,15,51,14,51,84,83,22,47,19,44,85,51,76,91,42,66}

    Returns: 17945

  13. 270

    {11,50,99,75,69,8,98,94,37,89,98,78,2,21,1,29}

    Returns: 3105

  14. 135

    {27,24,32,79,76,69,100,90,72,19,21,41,24,21,22,56,83}

    Returns: 7727

  15. 98

    {93,19,38,88,96,65,35,45,57,7,44,79,17,57,53,98,27}

    Returns: 4868

  16. 459

    {82,5,89,71,50,8,59,89,27,91,82,88,83,62,25,18,91,50,98,63,50}

    Returns: 21755

  17. 221

    {46,15,10,35,28,20,28,27,52,3,56,62,50,97,16,81,27,73,93,79,12,55,97,45,94,9,31,39}

    Returns: 6063

  18. 64

    {33,3,14,64,94,66,52,59,70,13,57,16,46,9,12,58,76,68,15,84,100,44,14,71,63,12,54,14,64,84}

    Returns: 1288

  19. 78

    {56,80,56,27,10,17,13,66,100,49,26,16,20,4,93,90}

    Returns: 2183

  20. 159

    {97,97,96,99,56,31,23,91,91,27,13,15,2,11,23,85,84,44,48,3,79,93,90,71,31,47,25,4,45}

    Returns: 2122

  21. 135

    {92,81,95,38,89,16,99,59,89,23,11,81,2,79,5,84,18,74,1,68,27,2,49,38,54,45,26}

    Returns: 962

  22. 302

    {36,5,73,66,75,70,58,41,52,100,11,49,39,74,13,67,3,70,15,19,67,68,2,78,50,41,25}

    Returns: 4851

  23. 165

    {52,43,90,50,76,71,44,55,26,91,9,6,21,44,46,60,37,28,16,13,45,49}

    Returns: 5985

  24. 152

    {84,93,100,39,1,34,75,4,65,59,61,19,61,55,85,62,48,50,23,69,43,82,61,68,31,87}

    Returns: 2412

  25. 273

    {30,77}

    Returns: 110791

  26. 180

    {74,89,21,34,26,27,8,21,22,83,36,60,92,46,50,30,95,54,77,13,41,36,14,85,64,53,72,40,22,48,16,56,68,47,57,81,3,64,91,87,85,34,76,99,30,87,7}

    Returns: 4296

  27. 490

    {96,77,93,19,42,57,90,93,71,28,84,8,66,60,16,81,63,75,77,20,94,48,1,1,77,25,53,26,11,92,9,66,43}

    Returns: 4383

  28. 128

    {41,62,82,66,80,53}

    Returns: 21906

  29. 148

    {76,26,8,70,34,8,64,35,53}

    Returns: 7499

  30. 225

    {26,55,43,47,15}

    Returns: 25045

  31. 187

    {41,23,1,36,81,30,36,14,12,63,8,54,97,17,2,49,83,19,61,59,100,81,79,80,14,28,49,9,57,63,57,99,30}

    Returns: 2008

  32. 254

    {23,1,42,59,38,80,92,26,70,79,94,99,78,79,30,41,35,43,61,33}

    Returns: 11555

  33. 420

    {70,58,58,29,23,40,50,70,11,7,59,69,67,90,35,86,1,72,7,94,86,66,14,90,2,98,29,9,97,12,20,49,12,6,15,85}

    Returns: 4837

  34. 370

    {92,42,47,58,8,23,74,77,60,30,66,89,38,73,25,68,48,17,69,1,40,97,99,6,80,42,82,62,8,34}

    Returns: 6947

  35. 328

    {45,98,90,14,39,24,9,25,94,88,63,33,50,5,27,63,97,64,26,97,9,29}

    Returns: 11540

  36. 270

    {62,6,8,69,76,39,4,7,88,26,35,28,64,51}

    Returns: 6653

  37. 138

    {9,67,4,73,1}

    Returns: 2038

  38. 199

    {5,33,67,5,10}

    Returns: 6118

  39. 18

    {42,89,48,51,14,52,99,18}

    Returns: 952

  40. 272

    {22,13,10,31,67,42,6,2,32,13,29}

    Returns: 6482

  41. 250

    {36,25,78,19,37,66,77,20,4,42,1,78,91,24,77,95,73,15}

    Returns: 4326

  42. 205

    {25,79,63,6,47,13,83,16,8,79}

    Returns: 7753

  43. 463

    {75,64,88,44,51,5,44,77,87,28,13,49,76,63,94,58,25,73,14,21,20,34,80,48,39,100,96,36,37,60,16,79,43,83,77,51,94,14,74,61,94,87,21,17,26,85,59,20}

    Returns: 17650

  44. 294

    {9,43,35,35}

    Returns: 31706

  45. 280

    {14,29,90,61,87,9,13,48,59,8,9,9,80,53,68,13,11,87,90,61,99,11,74,58,48,42,15,67,38,74,4,39,16,42,35,47}

    Returns: 6396

  46. 385

    {49,57,28,17,78,77,65,46,8,20,11,77,39}

    Returns: 21008

  47. 458

    {30,89,19,95,69,59,50}

    Returns: 68152

  48. 470

    {41,90,45,65,74,9,90,32}

    Returns: 54158

  49. 420

    {43,1,6,40,75,17,57,4,54,91,20,75,50,24,27}

    Returns: 6864

  50. 2

    {99,93,67,3,95,24,13,52,37,32,51,3,42,68,9,81,31,13,69,68,55,52,97,84,42,77,89,24,83,61,9,3,60,97,91,53,88,64,79,10,50,71,39,21,31}

    Returns: 6

  51. 423

    {73,65,9,65,45,82,8,8,1,30,83,67,76,86,70,37,92,1,16,45,3,75,49,61,79,39,10,22,48,33,99,75,5,42,100,48,70,83}

    Returns: 3299

  52. 122

    {56,100,41,74,45,16,50,89,89,16,53,82,37,45,48,46,3,94,33,15,94,47,80,62,15,82,89,97,15,47,31,39,54,14,80,34,9,91,37,84,12,87}

    Returns: 3017

  53. 309

    {43,80,72,56,14,18,49,15,33,100,60,44,57,21,5,49,20,56,55,75,56,18,23,90,42,90,16}

    Returns: 12066

  54. 279

    {4,6,23,13,34,10,55,63,63}

    Returns: 8337

  55. 177

    {47,94,76,33,12,43,39,63,60,64,88,56,67,2,22,15,29,25,14,74,52}

    Returns: 5452

  56. 14

    {16,74,22,96,52,87,29,9,3,50,56,79,51,7,84,11,92,49,18,38,27,58,44,93,68,86,76}

    Returns: 184

  57. 137

    {61,4,84,31,59,59,12,91,78,1,14,77,31,46,65,55,28,92,1,43,37,33,58,3,44,35,77,70}

    Returns: 850

  58. 202

    {33,33,83,19,93,41,36,63,82,59,80}

    Returns: 20147

  59. 500

    {40,9}

    Returns: 93856

  60. 469

    {84,9,99,86}

    Returns: 104451

  61. 270

    {59,43,9,60,46,9,28,98,98,1,66,30,81,36,37,41,45,40,17,25,70,52,76,46,54,83,44,43,22}

    Returns: 6306

  62. 225

    {20,7,1,9,99,35,90,11,4,89,80,3,33,94,13,40,13,85,68,32,61,44,81,32,36,56,31,15,70,55,78,5,32,57,53,6,5,73,78,38,84,64,23,15,14,13,20,25,34,95}

    Returns: 2242

  63. 159

    {91,48,63,77,12,55,22,58,54,12,46,7,3,85,30,49,74,80,27,63,70,31,57,11,11,44,50,57,46,51,48,44,40,40,65,2,42,41,41}

    Returns: 2432

  64. 279

    {51,56,31,66,3,40,21,21,92,21,51,34,31,58,6,17,2,86,59,34,97}

    Returns: 4749

  65. 417

    {52,66,52,92,30,35,19,47,40,86,60,98,57,51,71,51,83,93,70,100,48,98,79,29,76,91,9,81,18,73,25,85,87}

    Returns: 26587

  66. 385

    {23,19,58,64,9,34,39,3,47,80,73,56,6,85,19,12,98,87,37,50,8,19,28,94,24,54,55,12,64,96,36,2,22,19,96,97,38,65,56,88,15}

    Returns: 6376

  67. 311

    {6,27,1,50,83,20,33,85,50,18,68,11,45,86,1,16,59,29,81,45,33,81,12,3,81,95,29,56,51,89,21,60,74,97,59,55,41,67,100,77,28,3,25,53,58,51}

    Returns: 2172

  68. 57

    {66,52,62,15}

    Returns: 7122

  69. 427

    {58,12,59,88}

    Returns: 80144

  70. 379

    {71,64,75,21,73,52,53,38,5,37,30,28,80,71,29,55,30}

    Returns: 23920

  71. 402

    {73,75,39,21,15,2,45,91,5,26,57,65,18,81,10,72,25,37,7,1,90,16,87,65,33,12,86,7,92,71,6,64,67,96,78,15,37,67,51,75,12,29,4}

    Returns: 4087

  72. 370

    {71,95,14,52,21,17,95,53,93,20,35,84,21,56,90,5,33,52,19,57,61,59,40,65,71,9,100,8,43,2,46,27,7,53,67,30,72,17,29,37,69,69,26}

    Returns: 7234

  73. 384

    {13,42,35,59,44,54,90,37,88,13,40,41}

    Returns: 30770

  74. 32

    {49,73,43,67,90,38,20,1,63,83,21,70,52,68,34,91,33}

    Returns: 871

  75. 406

    {44,49,14,53,16,58,37,25,60,1}

    Returns: 14772

  76. 128

    {85,4,6,7,54,69,79,38,79,100,18,3,74,97,97,19,87,31,7,78,90,44,54,89,55,69,80}

    Returns: 1982

  77. 90

    {44,33,83,52,84,96,58,42,41,27,17,64,36,80,85,77}

    Returns: 6659

  78. 500

    {1,2,3,4,5,6,7,8,9,10}

    Returns: 4732

  79. 2

    {1,100}

    Returns: 101

  80. 500

    {100,100}

    Returns: 448800

    max return value

  81. 500

    {1, 1, 3, 5, 8, 13, 21, 34, 55, 89}

    Returns: 3993

  82. 500

    {91, 91, 91, 91, 92, 93, 93, 93, 94, 94, 95}

    Returns: 130321

  83. 500

    {2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 961

  84. 500

    {99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99, 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: 95275

  85. 500

    {100,100,100,100,100,100,100, 99,99,99,99,99,99,99, 98,98,98,98,98,98,98, 97,97,97,97,97,97,97, 96,96,96,96,96,96,96, 95,95,95,95,95,95,95, 94,94,94,94,94,94,94}

    Returns: 91894

  86. 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, 95, 98, 100 }

    Returns: 9464

  87. 500

    {10, 2, 3, 4, 5, 6, 7, 8, 9, 1 }

    Returns: 4732

  88. 3

    {1, 1, 100 }

    Returns: 5

  89. 4

    {1, 1, 100 }

    Returns: 8

  90. 500

    {11, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

    Returns: 6801

  91. 500

    {100, 99, 98, 97, 96, 1, 2, 3, 4, 5, 100, 99, 98, 97, 96, 1, 2, 3, 4, 5, 100, 99, 98, 97, 96, 1, 2, 3, 4, 5, 100, 99, 98, 97, 96, 1, 2, 3, 4, 5, 100, 99, 98, 97, 96, 1, 2, 3, 4, 5 }

    Returns: 1855

  92. 5

    {100, 100, 1, 1 }

    Returns: 12

  93. 500

    {1, 100 }

    Returns: 101996

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: