Statistics

Problem Statement for "StringWeight"

Problem Statement

In this problem, all strings consist of uppercase English letters only. That is, there are 26 distinct letters.

The weight of a string S can be computed as follows: for each letter that occurs at least once in S, its leftmost and rightmost occurrences L and R are found and the weight is increased by R-L.

For example, if S="ABCACAZ", the weight of S is (5-0) + (1-1) + (4-2) + (6-6) = 7. (The leftmost occurrence of 'A' is at the index L=0, the rightmost one is at R=5, so 'A' contributes 5-0 = 5 to the weight of S. The only 'B' contributes 0, the pair of 'C's adds 2, and the only 'Z' adds 0.)

A string is S called light if no other string of the same length has a smaller weight.

You are given a int[] L. Manao is going to choose some light strings. The elements of L specify the lengths of these strings. For example, if L = { 3, 42, 1 }, Manao will first choose a light string of length 3, then a light string of length 42, and finally a light string of length 1.

Then, Manao is going to concatenate all of the chosen strings, in the given order. Compute and return the smallest possible weight of a string Manao may obtain at the end.

Definition

Class:
StringWeight
Method:
getMinimum
Parameters:
int[]
Returns:
int
Method signature:
int getMinimum(int[] L)
(be sure your method is public)

Constraints

  • L will contain between 1 and 50 elements, inclusive.
  • Each element of L will be between 1 and 100, inclusive.

Examples

  1. {1}

    Returns: 0

    Every string of length 1 has weight 0.

  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}

    Returns: 1

    Manao is going to concatenate 27 strings of length 1. If Manao takes 25 distinct strings and 2 equal strings and places the equal strings side by side, the weight of the resulting string will be 1.

  3. {26, 2, 2}

    Returns: 8

    One possible concatenation of minimum weight is "ABC...XYZ"+"YZ"+"YZ".

  4. {25, 25, 25, 25}

    Returns: 1826

  5. {14, 6, 30, 2, 5, 61}

    Returns: 1229

  6. {100}

    Returns: 74

  7. {2,39,98}

    Returns: 778

  8. {2,14,47,43}

    Returns: 1187

  9. {84,58,25,20,46}

    Returns: 3432

  10. {20,25,49,24,40}

    Returns: 2914

  11. {8,38,62,17,31,46,85,60,91}

    Returns: 8727

  12. {46,9,50,21,2,48,14,12,9}

    Returns: 3557

  13. {1,87,64,88,8,36,56,57,83,18,25}

    Returns: 11272

  14. {16,20,1,7,1,23,41,31,13,5,28,5,4}

    Returns: 3711

  15. {87,70,31,93,65,89,70,95,81,86,31,14,13,56,17,89}

    Returns: 21886

  16. {43,18,16,20,15,18,2,47,45,48,46,48,45,47}

    Returns: 10282

  17. {90,81,73,37,57,36,61,74,53,82,8,46,36,85,26,70,83}

    Returns: 22247

  18. {28,11,41,48,31,11,15,11,40,33,34,48,34,45,47,1,19,42,36}

    Returns: 13974

  19. {9,5,23,78,68,24,41,54,15,12,48,73,8,57,56,21,1,84,53,3}

    Returns: 17229

  20. {5,32,48,33,1,41,45,42,21,21,40,13,24,16,44,30,18,50,39,8,7}

    Returns: 13610

  21. {48,34,13,31,26,82,54,22,39,95,97,99,37,16,19,45,96,2,12,79,10,14,51,73,37}

    Returns: 27905

  22. {40,6,15,40,15,16,3,33,12,26,6,40,2,29,6,41,17,47,7,22,23,2,36,43}

    Returns: 12251

  23. {26,2,39,97,70,95,94,4,22,21,83,23,50,32,3,28,1,40,85,63,37,11,56,6,99,60}

    Returns: 28296

  24. {35,25,12,13,48,17,2,45,31,42,11,4,39,26,7,33,17,35,25,21,21,48,27,45,49,6,7,42}

    Returns: 17757

  25. {40,69,47,51,30,84,45,10,61,53,92,99,39,50,39,80,49,41,84,70,33,95,92,50,97,3,11,10,47,60}

    Returns: 40530

  26. {9,45,16,30,15,19,1,22,21,2,17,17,31,43,43,12,9,42,35,1,16,8,20,30,21,24,8,11,30,47}

    Returns: 15093

  27. {78,78,62,8,92,51,39,72,75,78,46,36,19,35,70,35,32,60,43,80,94,51,60,11,22,48,42,80,23,21,71,12,72,99}

    Returns: 42869

  28. {12,32,14,9,38,22,43,19,37,23,49,23,29,11,10,38,34,43,33,20,30,22,9,4,29,18,28,50,4,45,33,39}

    Returns: 20847

  29. {95,21,57,49,33,96,89,93,7,20,2,43,21,28,41,79,12,12,40,37,14,16,27,17,11,13,25,78,30,90,63,4,78,46,28,89,56}

    Returns: 37409

  30. {5,15,12,33,9,8,16,32,48,31,49,23,39,6,6,23,35,3,38,30,2,18,29,25,10,7,37,4,11,34,14,25,25,39,47}

    Returns: 18808

  31. {39,59,65,88,3,49,69,81,27,96,89,93,60,21,93,26,77,27,41,33,72,7,36,56,89,78,65,88,82,100,72,39,90,70,95,13,62,67,92}

    Returns: 59983

  32. {46,4,43,4,35,19,30,43,3,47,16,12,43,46,28,32,12,3,9,33,1,20,37,31,50,18,20,47,36,29,13,48,38,26,35,47,13,17,10,26}

    Returns: 26644

  33. {67,43,99,33,15,30,42,57,32,9,84,53,74,3,99,52,38,69,41,3,42,9,74,14,31,95,33,51,57,97,5,91,84,83,68,92,38,70,67,77,42,20,45}

    Returns: 55752

  34. {47,2,43,37,38,19,35,10,49,38,13,45,42,45,19,16,6,37,26,12,12,45,8,33,16,6,18,41,41,42,5,4,48,20,31,17,12,18,30,1,33,39,13}

    Returns: 27373

  35. {9,19,4,1,18,20,23,20,19,1,24,8,23,17,15,14,8,3,23,10,3,26,15,19,2,20,13,2,20,14,3,20,20,23,20,18,1,22,1,24,4,16,26,24,18}

    Returns: 15058

  36. {11,13,21,12,10,20,12,5,1,17,25,26,14,14,3,4,22,5,25,18,11,8,16,21,4,16,14,3,12,2,17,1,14,11,20,8,5,24,20,11,23,23,14,25,25,8,21,10,21,1}

    Returns: 15559

  37. {5,5,15,9,3,3,2,9,16,20,22,3,16,14,13,16,4,9,22,7,24,25,8,17,22,23,6,7,6,3,5,4,10,9,21,21,21,6,25,9,12,17,6,18,15,24,4,9,20,7}

    Returns: 12914

  38. {25,21,3,8,8,18,6,20,17,10,22,12,5,14,17,1,18,17,10,24,8,6,4,4,2,17,2,4,13,20,21,2,6,9,7,4,16,15,20,23,5,3,1,20,22,18,13,9,5,13}

    Returns: 12385

  39. {5,5,22,22,26,12,9,15,16,14,7,19,13,12,11,21,26,3,24,14,22,7,7,6,12,4,20,8,15,3,1,13,12,18,3,14,5,13,8,22,20,3,24,4,6,2}

    Returns: 12856

  40. {7,19,4,1,16,25,7,21,5,24,17,15,10,5,21,15,5,4,18,8,22,11,16,15,24,13,23,6,13,5,18,6,4,9,25,26,26,22,23,5,19,15,8,2,20,14,16}

    Returns: 14630

  41. {5,20,9,7,9,12,9,14,15,9,12,23,12,15,22,12,3,15,10,16,20,8,23,10,2,18,18,7,16,25,14,19,18,18,26,9,24,1,25,20,13,21,14,20,17,7}

    Returns: 14072

  42. {26,7,14,5,19,11,15,16,22,5,2,2,21,11,20,2,4,18,23,23,2,4,1,15,6,1,22,14,20,24,15,1,24,23,25,22,24,17,11,10,24,12,12,8,7,1,23}

    Returns: 14966

  43. {20,20,6,13,20,9,4,2,21,26,12,3,25,6,10,20,8,9,6,25,5,6,23,12,12,20,13,12,15,13,3,26,18,26,24,17,10,6,6,22,25,14,22,8,9,24}

    Returns: 15447

  44. {4,18,3,7,13,2,1,3,21,16,13,19,25,12,7,12,26,13,8,5,16,23,14,15,4,21,18,16,14,13,26,2,14,14,4,26,3,25,20,7,22,24,5,2,26,11}

    Returns: 14232

  45. {84,23,75,2,3,36,43,47,96,29,21,89,16,26,40,63,75,43,1,74,65,47,64,30,7,53,74,10,39,94,93,79,96,36,96,47,63,49,37,42,13,72,35,72,49,65,100,14,27}

    Returns: 61653

  46. {1,13,91,15,11,81,24,63,73,18,36,40,66,19,40,90,74,13,60,89,94,6,50,40,37,3,19,45,44,1,92,91,47,78,50,67,67,81,36,27,76,28,53,13,22,35,4}

    Returns: 53197

  47. {24,82,75,100,54,62,10,58,39,28,66,26,98,29,87,66,90,74,3,73,19,63,99,77,1,57,76,45,99,5,72,2,74,22,95,15,17,47,81,66,71,7,58,1,90,20,84,94,12,27}

    Returns: 67779

  48. {74,71,8,94,67,27,30,77,81,24,13,11,17,64,63,36,28,11,83,79,41,29,99,69,65,81,93,23,69,35,74,96,62,27,35,88,8,60,66,1,64,53,44,86,36,53,2,80,78,89}

    Returns: 65813

  49. {18,39,47,66,71,10,13,81,29,6,45,75,46,77,89,17,17,19,10,6,82,44,32,11,99,8,67,21,48,67,41,100,8,63,91,10,65,51,83,60,71,10,46,49,40,42,100,23,93,9}

    Returns: 57974

  50. {51,73,8,85,97,53,23,61,45,85,97,46,37,73,56,85,26,23,66,44,17,35,80,42,44,31,8,89,86,40,84,30,34,10,44,26,33,40,18,10,14,85,41,34,71}

    Returns: 54254

  51. {18,58,86,65,71,31,25,23,30,33,19,62,37,62,93,44,76,72,17,96,22,98,93,59,23,25,86,27,25,84,32,93,53,10,43,58,15,11,64,88,43,52,59,16,2,2,2,46,99,20}

    Returns: 59934

  52. {16,100,35,16,51,14,94,59,47,48,42,40,4,31,17,70,38,2,55,47,76,38,9,18,3,12,1,82,44,30,66,3,70,63,47,58,63,6,49,29,25,22,62,58,16}

    Returns: 44120

  53. {47,10,56,36,44,87,10,76,78,74,58,72,21,82,24,14,42,63,32,78,39,59,42,61,53,58,9,35,81,67,9,31,10,62,59,94,87,79,87,81,94,24,73,51,69,21,24,95,80,3}

    Returns: 66154

  54. {80,40,45,45,27,20,80,52,40,6,78,22,4,30,85,80,20,77,10,8,91,83,96,54,91,8,6,14,70,94,12,10,79,74,50,77,1,53,25,82,74,38,53,55,35,40,36}

    Returns: 56224

  55. {62,73,97,45,47,37,89,99,50,90,78,26,80,93,100,70,95,56,71,71,32,33,78,93,97,34,74,89,52,29,40,52,61,65,55,46,32,90,40,100,76,97,58,76,83,29,74,87,33}

    Returns: 82333

  56. {97,41,46,99,38,67,61,76,81,34,43,78,83,44,95,50,41,49,64,37,61,84,37,61,56,44,46,71,93,46,77,82,96,100,37,86,92,86,63,60,47,47,70,48,91,39,74}

    Returns: 74817

  57. {26,34,55,82,64,54,44,92,86,99,95,63,71,34,75,83,62,97,79,48,71,73,38,28,27,41,40,46,29,65,73,65,70,69,94,62,89,57,30,42,46,51,66,60,35,67}

    Returns: 70501

  58. {48,59,47,48,88,30,87,94,67,55,85,89,84,35,79,72,68,68,59,69,28,55,39,85,79,65,50,26,56,99,59,30,40,53,48,77,53,85,43,33,64,55,66,73,35,29,100,83,100,40}

    Returns: 78478

  59. {62,96,45,95,62,68,50,33,76,97,85,37,82,70,61,67,56,73,32,38,27,72,70,39,49,61,97,53,68,51,59,33,87,96,99,56,37,29,72,78,90,53,68,74,49,66,92}

    Returns: 75034

  60. {59,62,45,28,95,26,58,75,99,93,64,91,36,74,59,39,67,60,86,76,95,84,98,46,79,68,100,94,86,91,31,79,31,74,39,48,63,78,81,50,29,66,59,31,74,70}

    Returns: 76335

  61. {61,65,58,56,37,77,51,40,45,40,62,49,61,75,52,73,79,96,62,27,74,62,45,67,57,54,30,55,79,100,73,57,54,68,47,79,93,83,26,48,33,58,81,32,51,64,31,43,36,62}

    Returns: 73157

  62. {45,54,68,80,35,81,83,57,100,86,87,70,83,99,33,45,31,37,27,94,73,96,46,52,68,32,48,26,86,73,66,78,97,38,69,89,46,70,67,86,37,87,78,52,31,72}

    Returns: 74607

  63. {94,71,40,29,45,49,86,31,99,26,39,72,95,35,37,38,36,42,91,86,62,89,29,73,89,75,37,72,92,98,72,81,95,91,48,85,98,92,94,83,36,56,73,45,68,59,95,88,100}

    Returns: 81990

  64. {83,82,47,67,50,66,36,100,92,75,62,67,54,52,36,83,33,45,58,44,41,38,90,61,90,31,94,64,66,80,75,40,100,96,76,26,68,100,92,54,84,98,46,66,66}

    Returns: 74223

  65. {14, 62, 30, 32, 5, 21, 1, 2, 3, 4, 5 }

    Returns: 2903

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: