Statistics

Problem Statement for "StringWeightDiv2"

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

You are given a int L. Consider all strings of length L. Compute the weight of each of these strings. The strings with the minimum weight among all of them are called light. Your task is to count the number of light strings of length L. Since this count may be very large, return it modulo 1,000,000,009.

Definition

Class:
StringWeightDiv2
Method:
countMinimums
Parameters:
int
Returns:
int
Method signature:
int countMinimums(int L)
(be sure your method is public)

Constraints

  • L will be between 1 and 1000, inclusive.

Examples

  1. 1

    Returns: 26

    Any string of length 1 has weight equal to 0.

  2. 2

    Returns: 650

    We can divide strings of length 2 into two classes: the strings with distinct first and second letter, and the strings with two equal letters. The strings composed of two equal letters have weight 1. All the other strings have weight 0. Thus, the number of strings of minimum weight is 26*26-26=650.

  3. 50

    Returns: 488801539

  4. 3

    Returns: 15600

  5. 4

    Returns: 358800

  6. 13

    Returns: 949597241

  7. 20

    Returns: 608487724

  8. 26

    Returns: 111157338

  9. 27

    Returns: 890090770

  10. 35

    Returns: 939243459

  11. 49

    Returns: 116964018

  12. 81

    Returns: 903534367

  13. 100

    Returns: 997628957

  14. 256

    Returns: 905751828

  15. 512

    Returns: 958139959

  16. 666

    Returns: 995360682

  17. 782

    Returns: 222116359

  18. 981

    Returns: 725153921

  19. 998

    Returns: 293776719

  20. 999

    Returns: 849115283

  21. 1000

    Returns: 227172651

  22. 117

    Returns: 941935388

  23. 550

    Returns: 511641044

  24. 260

    Returns: 56914315

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: