DengklekMessage | Topcoder Archive

Problem Statement

Mr. Dengklek is going to compose a long binary string called message. He is given a String[] pieces. He will construct the message as a concatenation of exactly K strings called parts. Each part will be an element of pieces chosen uniformly at random. Each element of pieces can be used multiple times. Each part is generated independently of the others. For example, if pieces = {"0", "10", "110"} and K = 5, then one possible message he can construct is "01100100".

Mr. Dengklek has a string he would like to see in the message. You are given this string as a String[] goodSubstring. Concatenate all elements of goodSubstring to get the string he would like to see. The score is the number of (possibly overlapping) occurrences of goodSubstring as a contiguous substring within the message.

For example, if goodSubstring = {"0", "1"}, the string he would like to see is "01" and the score for the example message from the previous paragraph is 2.

You are given the String[] pieces, the String[] goodSubstring, and the long K. Return the expected value of the score of the message that Mr. Dengklek will compose.

Definition

Class:: DengklekMessage
Method:: theExpected
Parameters:: String[], String[], long
Returns:: double
Method signature:: double theExpected(String[] pieces, String[] goodSubstring, long K)
(be sure your method is public)

Notes

The returned value must be accurate to within a relative or absolute error of 1E-9.

Constraints

pieces will contain between 1 and 50 elements, inclusive.
Each element of pieces will contain between 1 and 50 characters, inclusive.
Each character in pieces will be '0' (zero) or '1' (one).
pieces will not contain duplicate elements.
goodSubstring will contain between 1 and 10 elements, inclusive.
Each element of goodSubstring will contain between 1 and 50 characters, inclusive.
Each character in goodSubstring will be '0' (zero) or '1' (one).
K will be between 1 and 1,000,000,000,000 (10^12), inclusive.

Examples

```
{"0"}
```
```
{"00"}
```
```
10
```
```
Returns: 9.0
```
He will compose the message "0000000000". It contains 9 occurrences of "00".
```
{"0"}
```
```
{"00"}
```
```
1
```
```
Returns: 0.0
```
This time the message is "0" and it scores nothing.
```
{"0", "1"}
```
```
{"00"}
```
```
3
```
```
Returns: 0.5
```
There are 8 possible messages that he can compose, each with the same probability: "000", "001", "010", "011", "100", "101", "110", "111". Of them, "000" scores 2, each of "001" and "100" scores 1 and other messages score nothing. The expected score is (2 + 1 + 1) / 8 = 0.5.

{"0", "10", "110"}

{"0", "1"}

Returns: 2.6666666666666665

The example from the problem statement.

{"0", "10"}

{"000101000101010100"}

Returns: 0.25146484375

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.