I was solving https://codeforces.net/problemset/problem/1265/E, but I misunderstood the problem and could not solve it. When I jumped to the editorial, I realized my mistake, and I quickly returned back to the problem, read the statement carefully, and pieced together the solution.
But I am still not able to solve my "misunderstood" problem. I pose that to you:
There are $$$n$$$ coins that turn up head with probabilities $$$p_1$$$, $$$p_2$$$, $$$p_3$$$ ... $$$p_n$$$ respectively. A person starts cyclicly tossing coins – in the order 1, 2, 3 .... n, 1, 2, ... , i.e. after coin $$$n$$$, they toss coin $$$1$$$ again. They will stop when they have a streak of $$$n$$$ heads.
What is the expected number of coin tosses?
Constraint: $$$n <= 200,000$$$.
The Markov chain(s) that I am constructing to solve problem have $$$O(n^{2})$$$ edges – which is too large for the constraints. Can we do better?
I typically use the recurrence relation that is mentioned in the link below. It talks about how to generalize waiting for a pattern and also has some rudimentary proof for the same. Not sure if this can apply here though.
http://prob140.org/sp17/textbook/ch13/Waiting_Till_a_Pattern_Appears.html
The Markov chains are too big – we will have too many (or too long) equations, I think.