Statistics

Problem Statement for "Pikachu"

Problem Statement

Pikachu is a well-known character in the Pokemon anime series. Pikachu can speak, but only 3 syllables: "pi", "ka", and "chu". Therefore Pikachu can only pronounce strings that can be created as a concatenation of one or more syllables he can pronounce. For example, he can pronounce the words "pikapi" and "pikachu".


We need to teach our Pikachu to use N different words, conveniently numbered 0 through N-1. To do this, we need to encode the words into N distinct strings Pikachu will be able to pronounce. For example, we may encode "electric" as "pikapi" and "mouse" as "pikachu". As Pikachu sometimes omits pauses between the words he says, the encoding we will use must be prefix-free. More formally, we need to choose strings code[0], code[1], ..., code[N-1] such that:
  1. For any i, code[i] must be a string that is generated by concatenating one or more copies of the strings "pi", "ka" and "chu".
  2. For any distinct i and j, code[i] is not a prefix of code[j].
Of course, there are infinitely many such codes. We want you to find all the most efficient codes. The N words we need to encode may have distinct frequencies. You are given the relative frequences of all words as a int[] freq. (I.e., the actual frequency of the i-th word is freq[i]/S, where S is the sum of all elements of freq.) For a given code, its total cost can be computed as the sum of (freq[i]*length(code[i])) over all i.


Let A be the minimal total cost that can be achieved, and let B be the number of distinct codes that have the total cost equal to A. Your method must return a int[] with two elements: element 0 should be the value A, and element 1 should be the value (B modulo 1,000,000,009).

Definition

Class:
Pikachu
Method:
bestEncoding
Parameters:
int[]
Returns:
int[]
Method signature:
int[] bestEncoding(int[] freq)
(be sure your method is public)

Constraints

  • freq will contain between 2 and 30 elements, inclusive.
  • Each element of freq will be between 1 and 1000, inclusive.

Examples

  1. {1,1}

    Returns: {4, 2 }

    We have two words with the same frequency. One of the two optimal codes is ("pi", "ka"), i.e., word 0 is encoded as "pi" and word 1 is encoded as "ka". The total cost of this code is 1*length("pi") + 1*length("ka") = 1*2 + 1*2 = 4. The other optimal code is ("ka", "pi").

  2. {1,1,2}

    Returns: {9, 4 }

    There are 4 solutions: ("chu", "ka", "pi"), ("ka", "chu", "pi"), ("pi", "chu", "ka") and ("chu", "pi", "ka"). Note that solutions that encode word 2 as "chu" are not optimal.

  3. {1,1,1,1}

    Returns: {13, 48 }

    One of the 48 optimal codes is ("pi", "chu", "kapi", "kaka").

  4. {2,3,5,7,11,13,17,19}

    Returns: {309, 96 }

  5. {533,533,533,353,335,335}

    Returns: {10290, 288 }

  6. {1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: {72, 362124467 }

    Don't forget to use modular arithmetics when computing B.

  7. {353,783,226,713,517,706,160,149,639,83,783,918,860,856,385,148}

    Returns: {45248, 829440 }

  8. {122,428,386,905,257,311,71}

    Returns: {8942, 24 }

  9. {318,19,421,249,588,194}

    Returns: {6198, 8 }

  10. {348,922,183,380,346,248,342,490}

    Returns: {13664, 96 }

  11. {390,96,13,375,173,422}

    Returns: {4969, 8 }

  12. {574,574,125}

    Returns: {2671, 2 }

  13. {15,976,518,794,389,176}

    Returns: {9299, 8 }

  14. {729,775,3,3,612,734,672,566,705,811,734,743,997,330}

    Returns: {44230, 138240 }

  15. {238,238,903,581,238,267,267,84,550,521,318,81,559,769,903,624,546}

    Returns: {42989, 14929920 }

  16. {7,7,817,775,318,640,767,339,411,459,114,640,118,967,963,421,45,114,582,3}

    Returns: {47210, 13271040 }

  17. {925,142,961,440,630,630,693,681,961,925,617,856,639,961,222,962,305,460}

    Returns: {70512, 418037760 }

  18. {491,491,620,620,338,393,393,393,507,393,997,252,393,615,410,791,620,874,105}

    Returns: {57886, 352831721 }

  19. {853,109,313,397,58,866,63,58,849,286,205,286}

    Returns: {19737, 1152 }

  20. {86,86,453,86,750,574,86}

    Returns: {7098, 96 }

  21. {189,867,658,833,371,178,299,178,42,156,867}

    Returns: {20736, 1152 }

  22. {219,219,353,83}

    Returns: {2571, 8 }

  23. {601,996,723,107,461,107,461,601,881,461,881,107,658,461}

    Returns: {39168, 1658880 }

  24. {765,366,802,366,609,946,609,104,395,395,395,889,180,325}

    Returns: {37598, 138240 }

  25. {536,190,536,242}

    Returns: {4304, 4 }

  26. {626,931,552,343,359}

    Returns: {9099, 4 }

  27. {388,388,347,7,948,673,600,810,388,388,747}

    Returns: {27052, 20736 }

  28. {815,2,913,780,780,977,780,780,780,55,2,780,2,913,780,780,294,55}

    Returns: {56737, 114767351 }

  29. {994,847,233,156,459,432,847,507,117,952,117,732,432}

    Returns: {33949, 27648 }

  30. {815,67,67,258,496,5,342,258,102}

    Returns: {9152, 48 }

  31. {654,654,654,128,330,545,654,654,318,330,654,464,505,806,705,318,654,330,167,654}

    Returns: {62173, 329061500 }

  32. {562,562,562,562,951,562,388,562,438,951}

    Returns: {29424, 103680 }

  33. {125,125,125,26,125,125,26,629}

    Returns: {4549, 480 }

  34. {162,162,162,355,355,162}

    Returns: {5177, 192 }

  35. {239,239,239,239,225,239,239,223,239,239,816,283,239,239,239,225,223}

    Returns: {26849, 160063829 }

  36. {258,258,258,218,258,258,258,929,258,258,342}

    Returns: {17220, 483840 }

  37. {996,887,887,287,996,996,887,287,304,887,269,962,887,434,434,996,61}

    Returns: {65120, 92897280 }

  38. {969,290,969,290,983,290,290,844,969,290,983,969,290,969,969,290,969,727,40}

    Returns: {72876, 773252511 }

  39. {609,872}

    Returns: {2962, 2 }

  40. {716,716,716,716,716,523}

    Returns: {16219, 240 }

  41. {817,817,146,817,146,146,817,817,817,817,817,423,201,483}

    Returns: {42747, 11612160 }

  42. {599,599,633,599,599,599,599,272,633,217,103}

    Returns: {26675, 17280 }

  43. {783,783,996,783,783,783,996,783,990,339,996,783,783,783,783}

    Returns: {69030, 135283173 }

  44. {292,292,380,292,292,292,275,292,513,275,513,292,513,513,544}

    Returns: {31122, 20321280 }

  45. {95,95,95,95,95,95,711,453,711,710,95}

    Returns: {13999, 483840 }

  46. {966,966,966}

    Returns: {6762, 6 }

  47. {733,733,464,733,464}

    Returns: {10773, 48 }

  48. {873,986,419,873,873,973,986,873,873,419,660,973,973,973,419,873}

    Returns: {75453, 254113271 }

  49. {92,92,92,92}

    Returns: {1196, 48 }

  50. {457,457,457,457,457,457,457,457,457,457,457,457,224,725,843,457}

    Returns: {45054, 690987136 }

  51. {269,269,808,808,269,808,269,808,808,808,269,808,269,808,269}

    Returns: {46037, 438553582 }

  52. {567,567,567,567,567,567,567,567,567,567,567,567,567,567,567,567,567,567,567}

    Returns: {67473, 256104427 }

  53. {236,236,236,236,236,236,236,236,236}

    Returns: {9912, 362880 }

  54. {932,932,932,932}

    Returns: {12116, 48 }

  55. {855,855,855,855,855,21,855,855,855,855,855,855,855,855,855}

    Returns: {68547, 139484986 }

  56. {67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67}

    Returns: {7437, 592426554 }

  57. {517,517,728,140,728,728,140,728,517,728,140,140,140,140,517,517,728,728,316,517,532,517,517,728,728,140}

    Returns: {81900, 147142071 }

  58. {225,438,611,582,396,186,302,641,347,955,870,920,917,463,682,218,977,856,478,852,288,440,664,659,335,389,270,915}

    Returns: {107059, 868434557 }

  59. {400,400,400,400,400,400,400,160,746,400,829,400,400,639,400,776,400,405,536,400,400,400,400,588,400}

    Returns: {76394, 659610581 }

  60. {857,191,623,887,403,686,191,60,250,753,271,94,812,928,341,84,187,320,321,424,579,871,694,137,840,29,427,666,233,630}

    Returns: {91870, 295056642 }

  61. {43,43,447,43,529,357,43,357,80,636,921,357,825,756,357,636,227,756,357,153,285}

    Returns: {47697, 573836755 }

  62. {886,299,177,383,363,881,346,44,429,807,882,4,199,2,952,553,783,114,119,807,991,509,961,541,805,986,339,387,527}

    Returns: {98780, 234972539 }

  63. {416,476,128,476,481,455,660,242,364,660,615,242,258,449,242,615,242,242,896,606,549,242,844}

    Returns: {65882, 617486274 }

  64. {142,461,360,67,9,720,70,929,490,906,753,387,693,885,937,370,781,196,427,474,618,279,10,256,966}

    Returns: {75864, 493592250 }

  65. {405,460,901,287,974,407,836,231,393,442,240,22,319,976,593,800,96,64,737,827,278,724,8,694,240,770,794,331,219}

    Returns: {92671, 409835225 }

  66. {262,646,110,640,510,118,106,63,554,611,214,4,514,206,332,639,487,455,258,529,403}

    Returns: {45632, 836075520 }

  67. {128,128,785,265,112,666,495,760,612,573,67,643,612,484,950,523,127,616,395,362,858,285,729}

    Returns: {69423, 493592250 }

  68. {821,136,566,505,117,881,787,450,495,79,190,206,437,765,458,905,491,967,42,31,835,694,134}

    Returns: {66570, 16453075 }

  69. {182,412,257,317,322,976,721,640,976,274,274,138,316,262,706,334,844,512,756,8,651,525,425,720}

    Returns: {72856, 935922464 }

  70. {715,587,731,851,384,109,702,858,162,247,688,472,145,472,973,53,549,613,54,653,882}

    Returns: {65087, 836075520 }

  71. {452,660,683,108,657,486,452,932,20,475,284,413,149,932,265,660,803,648,273,132,269,47,774,657}

    Returns: {69978, 480776741 }

  72. {370,85,927,381,803,799,145,342,713,501,836,710,442,580,810,962,139,576,49,370,513,859,59,92,244,942,981}

    Returns: {92026, 846994515 }

  73. {25,230,230,363,774,924,25,230,485,973,924,2,25,2,804,230,487,181,25,695,736,861,25,230,25,25,2,55,55}

    Returns: {56806, 234972539 }

  74. {881,199,923,49,688,685,983,532,584,907,173,188,313,651,584,779,17,512,578,480,924,148}

    Returns: {71402, 16453075 }

  75. {627,647,699,627,703,650,164,883,927,570,663,932,884,375,214,627,329,818,359,327,574,117,782,937,234,675,1000,585,433}

    Returns: {118264, 622811522 }

  76. {698,90,44,678,190,737,3,806,815,555,286,938,908,338,493,418,283,67,717,476,618,692}

    Returns: {65244, 672151031 }

  77. {991,94,76,658,991,912,844,658,868,298,59,84,787,191,673,804,426,273,818,591,474,437,187,422,982}

    Returns: {85860, 961553482 }

  78. {965,649,165,121,160,521,374,823,700,228,953,484,918,840,504,963,11,219,509,218,671,756,193,765,776,216,541,507,980}

    Returns: {104972, 459011332 }

  79. {430,430,430,430,430,430,430,726,842,430,953,430,45,430,953,974,927,430,528,114,231,45}

    Returns: {68108, 99043620 }

  80. {421,213,84,730,442,3,596,877,8,464,761,149,743,928,566,10,780,973,443,897,439,690,976,59,719,581,728,244,244}

    Returns: {96511, 234972539 }

  81. {391,274,315,782,317,389,554,479,651,643,553,964,891,855,300,810,7,905,13,521,720,902,210,963}

    Returns: {84533, 606860964 }

  82. {126,412,654,927,660,160,260,462,432,45,823,163,342,524,454,997,486,348,21,607,211,456,120,328,919,20,707,276,383,467}

    Returns: {85099, 316924134 }

  83. {338,723,352,370,656,844,895,282,70,994,844,895,882,25,379,389,393,389,901,328,70,49,320,772}

    Returns: {75535, 974368991 }

  84. {759,577,58,290,985,470,64,779,776,3,65,11,455,55,235,410,657,15,267,473,648,570,321,125,453}

    Returns: {57465, 32906150 }

  85. {324,788,107,562,712,197,401,954,801,616,781,13,336,112,333,339,14,973,622,283,426,338,749,1,312}

    Returns: {68761, 493592250 }

  86. {343,184,196,563,750,315,292,858,330,391,140,451,211,662,852,465,405,159,590,305,370,735,169,295,625,675,93}

    Returns: {75145, 409835225 }

  87. {191,556,144,203,716,203,479,144,472,455,152,83,472,164,152,479,274,479,144,57,63,479,445,924,101,463,657,213,766,279}

    Returns: {69390, 590113284 }

  88. {395,184,15,87,161,758,173,485,735,648,566,471,132,891,555,132,39,268,668,980,947,647,19,707,398,411,620,284,723}

    Returns: {85551, 81967045 }

  89. {731,731,731,141,221,731,386,731,731,731,584,584,221,221,782,731,669,731,296,425,731,486,731,141,691,731,731}

    Returns: {103098, 111684321 }

  90. {362,346,588,458,467,67,90,214,947,756,251,316,658,859,164,643,230,527,653,729,987,958,149,154,272,518,655,792,294}

    Returns: {94172, 491761070 }

  91. {661,661,274,661,661,661,661,168,661,968,490,409,661,17,661,793,657,968,793,17,631,355,661,661}

    Returns: {88410, 264116320 }

  92. {96,293,122,76,217,514,394,474,213,852,223,44,265,264,245,74,20,549,744,699,38,316,325,348,938,292,258,200,47}

    Returns: {58792, 852458813 }

  93. {232,232,232,232,828,5,545,967,967,45,545,233,233,545,929,967,45,967,232,967,18,232,168,232,946,5,545,45}

    Returns: {75542, 409835225 }

  94. {332,118,234,179,94,52,778,522,54,201,147,148,394,864,707,435,471,422,260,915,791}

    Returns: {47267, 139345920 }

  95. {284,706,706,334,336,334,839,284,334,334,334,706,821,334,334,497,451,977,334,112,367,269,763,367,334,334,213,218,659,334}

    Returns: {91387, 940085267 }

  96. {780,723,365,386,608,909,36,364,93,400,965,73,623,205,386,512,876,246,831,713,659,925,291,467,484,782}

    Returns: {88812, 617486274 }

  97. {181,572,606,646,212,470,212,212,633,300,3,754,346,247,3,989,499,774,336,749,515,677,384,535,978,606,12,806,677,564}

    Returns: {97345, 98352214 }

  98. {909,181,583,629,873,193,303,474,592,685,936,987,425,298,534,540,17,332,708,307,843,390,57,15,789,417,322,628,40,145}

    Returns: {94059, 98352214 }

  99. {702,702,702,18,702,702,281,672,919,43,67,677,439,43,702,518,503,816,706,164,43,67,832,905}

    Returns: {72901, 131624600 }

  100. {425,181,704,240,396,752,83,499,310,482,171,399,451,427,532,380,224,234,735,966,932,927,406,668,470,139,992,334,498,771}

    Returns: {100409, 98249214 }

  101. {288,288,117,288,288,288,288,309,288,309,288,288,419,972,288,288,907,568,288,288,205,288,309,288}

    Returns: {54567, 620687147 }

  102. {882,499,332,65,479,160,262,755,784,235,366,374,125,441,725,843,325,148,825,376,982,496,646}

    Returns: {69135, 740388375 }

  103. {445,555,171,445,445,446,445,445,212,599,418,445,599,228,599,11,445,65,542,11,445,445,171,445,171,445,256,445}

    Returns: {69447, 403706725 }

  104. {533,335,692,519,855,49,73,285,416,353,476,704,393,85,147,847,810,976,687,452,932,999,399,512}

    Returns: {78831, 606860964 }

  105. {610,610,672,672,610,610,911,911,911,911,34,181,34,567,621,610,175,21,241,175,610,610}

    Returns: {68157, 460686100 }

  106. {945,945,945,945,945,945,945,945,945,945,945,945,945,945,945,945,945,945,945,945,945,945,945}

    Returns: {144585, 312336197 }

  107. {808, 250, 74, 659, 931, 273, 545, 879, 924, 710, 441, 166, 493, 43, 988, 504, 328, 730, 841, 613, 304, 170, 710, 158, 561, 934, 100, 279, 817, 336 }

    Returns: {104688, 98249214 }

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: