PROBLEM LINK
Author: Dmytro Berezin
Tester: Sergey Kulik
Editorialist: Florin Chirica
DIFFICULTY:
medium
PREREQUISITES:
matrix multiplication; basic probability theory
PROBLEM
You’re given an initial word S. You do K claps: each clap a character from S turns into another character with some given probability. You’re also given a list of final words. What’s the probability the word S will be one from the final list after those K claps?
QUICK EXPLANATION
A word S can transform in other word s[i] if and only if their length are equal. Probability the word S to transform in s[i] is prob(S[1], s[1]) * prob(S[2], s[2]) * …, where prob(a, b) is probability the character a will transform in the character b after K claps.
We can calculate dp[k][a][b] = probability character a will turn into character b after k claps. We find the recurrence dp[k][a][b] = sum of dp[1][a][a’] * dp[k - 1][a’][b]. This recurrence can be improved by using matrix multiplication, since it is a linear recurrence.
Explanation
We need to compute probability that word S will become one of the words from s list. When is it possible the initial word S to become one of words s[i]? If the words S and s[i] have the same length, there’s some probability (possibly 0) that word S will become word s[i]. If word S and word s[i] have different lengths, then we know for sure it’s not possible, since we can’t replace a letter by SPACE character.
Let’s consider all words s[i] from s list. We’ll see what’s the probability word S will transform in word s[i] using exactly K claps. The answer of the problem is the sum of those probabilities.
So suppose we want to transform word A in word B using exactly K claps. This means A[1] needs to become B[1], A[2] needs to become B[2] and so on. Denote by P(char1, char2) = probability that character char1 will become char2 after exactly K claps. All the events P(A[1], B[1]) P(A[2], B[2]) and so on need to happen. We know from probability theory that the probability for some independent events to all happen (each of event needs to happen) is the product of each probability. So, in this case, probability word A will become word B is P(A[1], B[1]) * P(A[2], B[2]) * … * P(A[n], B[n]) where by n I noted length of A array.
The problem is reduced to: calculate P(a, b) = probability that character a will transform in character b after K claps. Calculating this in the current form seems difficult, so let’s try to add one more parameter.
Let P(a, b, x) = probability that character a will transform to character b after exactly x steps. For x = 1, the answers are given in the input.
We’ll next try to do dynamic programming. Suppose we calculated P(something1, something2, x - 1) for each something1 and something2, let’s try to calculate P(a, b, x) for each a and b. We focus now to calculate it for two fixed values of a and b. Then, we can iterate each two values a and b and whole P will be calculated for given parameter x.
Suppose we do one step. Let’s imagine character a becomes a’ after 1 clap. We need to do x - 1 claps which must transform character a’ into b. Suppose we fixed a’ now. What’s the probability a will turn into b, given that after one clap it will become a’? It is P(a, a’, 1) * P(a’, b, x - 1). Why? First, character a transforms in a’ using a clap with probabilty P(a, a’, 1). Then, a’ transfors in b after x - 1 steps with probability P(a’, b, x-1). The probability that both independent events to happen is P(a, a’, 1) * P(a’, b, x - 1).
Let’s solve for general case calculation of P(a, b, x). After one step, a character a will turn into some character a’. If we iterate all characters a’ possible, then all cases are covered. We need to calculate the sum of P(1, a, a’) * P(x-1, a’, b). Why do we need the sum? All events are independent, and exactly one event from the list needs to happen (since the character after 1st clap is always different between any two events, they’re independent). Probability that one event will happen is sum of probabilities of all events.
So we get that P(x, a, b) = sum of all P(1, a, a’) * P(x-1, a’, b).
This is how we get an O(K * 26^3) solution. This should time out. However, using some more math theory we can reduce the complexity.
Let’s recall how matrix multiplication is done: suppose you’re given two matrixes A and B and want to calculate C = A * B. We know that C[a][b] = sum of all A[a][a’] * B[a’][b]. This recurrence matches with the one from above to calculate P(x, a, b).
If we note C[a][b] = P(x, a, b), A[a][b] = P(1, a, b) and B[a][b] = P(x-1, a, b), we’re reduced our task to matrix multiplication.
The final observation to solve the task is: suppose A[a][b] is probability character a will turn to character b after exactly 1 clap. Let’s determine probability that character a will turn into character b after x claps. It’s enough to raise matrix A to power x-1, then print element from (A^(x-1))[a][b].
Since matrix multiplication is associative, it can be done by exponentiation by squaring. Hence, our total runtime is reduced to O(26^3 * (log(K)).
AUTHOR’S AND TESTER’S SOLUTIONS:
To be updated soon
To be updated soon
Remind myself to never assume anything not given in the problem…