Connection Status:
Competition Arena > LinenCenterEasy

LinenCenterEasy

SRM 692 · 2016-06-04 · by Xellos0

SRM 692 · 2016-06-04 · by Xellos0 · Dynamic Programming, String Parsing
Class Name: LinenCenterEasy
Return Type: int
Method Name: countStrings
Arg Types: (string, int, int)
Problem Statement

Problem Statement

A few days ago, you won a tour of a textile factory. (Chocolate factory tours were deemed too risky to children and therefore banned). As everyone knows, textile is made of strings, so it's time to solve a string problem!


You are given a String S of length L. For any string T, we can now define its covering number c(T) as the maximum number of non-overlapping occurrences of S in T. Each occurrence must be a contiguous substring of T, and they may not share any letters.


Examples:
If S="ab", we have c("xyz")=0 and c("ababxab")=3.
If S="aaa", we have c("aa")=0 and c("aaaaaa")=2.


In addition to S, you are given two ints N and K.


Consider all strings with the following properties:

  • Each character of the string is a lowercase English letter ('a'-'z').
  • The length of the string is between L*K and L*K+N, inclusive.
  • The covering number of the string is exactly K.

Let X be the number of strings with the above properties. Since X may be large, compute and return the value (X modulo 1,000,000,009).

Constraints

  • N will be between 0 and 50, inclusive.
  • K will be between 0 and 50, inclusive.
  • L will be between 1 and 50, inclusive.
  • S will contain exactly L characters.
  • S will contain only lowercase English letters.
Examples
0)
"aaaa"
1
4
Returns: 127
1)
"abcd"
0
3
Returns: 1
2)
"abcab"
15
0
Returns: 743760874
3)
"x"
20
5
Returns: 732797485
4)
"abcdefghabcdefgh"
1
15
Returns: 417
39)
"xy"
2
1
Returns: 2079

There are 2027 strings of length 4, 52 strings of length 3 and one string of length 2 containing "xy" as a substring. One of them, "xyxy", has covering number 2, so we don't count it.

40)
"q"
2
1
Returns: 1926

We're counting strings containing exactly one character 'q' and at most two other characters. There's one such string of length 1 ("q"), 2*25=50 of length 2 and 3*25^2=1875 of length 3.

41)
"ababab"
5
4
Returns: 527166180

Watch out for integer overflows and make sure you are using the correct modulus!

Submissions are judged against all 50 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LinenCenterEasy with a public method int countStrings(string S, int N, int K) · 50 test cases · 2 s / 256 MB per case

Submitting as anonymous