Connection Status:
Competition Arena > DengklekMessage

DengklekMessage

SRM 526 · 2011-05-25 · by [[rng_58]]

SRM 526 · 2011-05-25 · by [[rng_58]] · Dynamic Programming, Simple Math, String Manipulation
Class Name: DengklekMessage
Return Type: double
Method Name: theExpected
Arg Types: (vector<string>, vector<string>, long long)
Problem Statement

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.

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)
{"0"}
{"00"}
10
Returns: 9.0

He will compose the message "0000000000". It contains 9 occurrences of "00".

1)
{"0"}
{"00"}
1
Returns: 0.0

This time the message is "0" and it scores nothing.

2)
{"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.

3)
{"0", "10", "110"}
{"0", "1"}
5
Returns: 2.6666666666666665

The example from the problem statement.

4)
{"0", "10"}
{"000101000101010100"}
526
Returns: 0.25146484375

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

Coding Area

Language: C++17 · define a public class DengklekMessage with a public method double theExpected(vector<string> pieces, vector<string> goodSubstring, long long K) · 100 test cases · 2 s / 256 MB per case

Submitting as anonymous