Editorial for CTU Open Contest 2018 - Numbers Generator - Olympiads Online Judge

Editorial for CTU Open Contest 2018 - Numbers Generator

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Keep track of current state with Finite automaton.
We can use Aho-Corasick algorithm to achieve this.
We create matrix $A$ ~A~ with probabilities of transitions.
We can achieve this by giving each edge in Aho-Corasick $\frac 1 2$ ~\frac 1 2~ probability of traversal, and creating edges with probability $1$ ~1~ from all final states to one common final state.
Now find the expected number of steps before ending in absorbing state.
After solving $(E-A)x = 1$ ~(E-A)x = 1~, the answer can be found in $x_0$ ~x_0~.
To solve this equation, we can use Gaussian Elimination.
Complexity $\mathcal O((WB)^3)$ ~\mathcal O((WB)^3)~

Comments

There are no comments at the moment.