Connection Status:
Competition Arena > RollMe

RollMe

SRM 797 · 2021-01-08 · by misof

SRM 797 · 2021-01-08 · by misof · Advanced Math, Dynamic Programming
Class Name: RollMe
Return Type: int
Method Name: solve
Arg Types: (vector<int>, string)
Problem Statement

Problem Statement

You have a biased die with N faces, labeled 0 to N-1. You are given the int[] die with the relative probabilities of rolling each value. I.e., on this die you will roll the value x with probability die[x] / sum(die).


You are given the String goal. You are going to repeatedly roll your die and write down the result until the last length(goal) characters match goal exactly.


The expected number of rolls in the above process can be written as a reduced fraction P/Q. Return P*Q^(-1) modulo (10^9 + 7).

Notes

  • The exact answer is always a rational number. If we write it as a simplified fraction P/Q, the value Q will always be relatively prime to 10^9 + 7. Hence, Q has a multiplicative inverse: a value Q^(-1) such that (Q*Q^(-1)) mod (10^9 + 7) = 1.

Constraints

  • N will be between 2 and 10, inclusive.
  • die will have N elements.
  • Each element of die will be between 1 and 10, inclusive.
  • goal will have between 1 and 5000 characters, inclusive.
  • Each character of goal will be one of the N smallest digits ('0', '1', ...).
Examples
0)
{7, 7}
"01"
Returns: 4

A fair coin. We are waiting until we see a head ('0') followed by a tail ('1'). This takes four flips on average.

1)
{1, 1}
"00"
Returns: 6

Another fair coin, but now we are waiting for two heads in a row. Perhaps surprisingly, that requires 6 coin flips on average: more than another pattern of the same length.

2)
{2, 1}
"1011"
Returns: 500000047

On average we'll need to make 43.5 = 87/2 coin flips with this biased coin until "1011" appears. We have P=87 and Q=2. The multiplicative inverse to this Q is Q^(-1) = 500,000,004, and thus the correct return value is (87 * 500000004) mod 1000000007 = 500,000,047.

3)
{1, 1, 1, 1, 1}
"0123401"
Returns: 78150
4)
{1, 2, 3, 4}
"3132313"
Returns: 958336629

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

Coding Area

Language: C++17 · define a public class RollMe with a public method int solve(vector<int> die, string goal) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous