proofbycontradiction's blog

By proofbycontradiction, history, 3 years ago, In English

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?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    The Markov chains are too big – we will have too many (or too long) equations, I think.