I was solving https://mirror.codeforces.com/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?

Could we have a tag for interactive problems? That way we could search for interactive problems of a certain difficulty, like *2400 + interactive.

This is a problem that I've been thinking of for quite a while.

You start with the empty string. There will be $$$q$$$ queries. Each query will append a character to the string. You have to answer if the new string is a palindrome.

• "" — add A ----> "A" = True
• "A" — add B ---> "AB" = False
• "AB — add A ---> "ABA" = True
• .... and so on for $$$q$$$ steps.

Is there an efficient (better than $$$O(q^2)$$$) online solution for this problem?

Exactly what the title says: How to search for all the previous Interactive Problems On Codeforces?

I'm very fired up after the question in the previous contest.

Hi all,

Consider n lattice points in a 2D grid {(x₁, y₁)....(x_n, y_n)}. A point (x₁, y₁) is said to dominate another point (x₂, y₂) if and only if x₁ > x₂ and y₁ > y₂. Obviously this dominance relation defines a DAG: G has an edge if point u dominates point v. Let us call this the dominance graph.

My question is this, is it possible to efficiently (say in time O(nlog(n))) compute the dominance graph?

Obviously, the dominance graph could have O(n²) edges. For example, if every point lies on the x = y line, then each point would dominate all points below it, giving us ⁿC₂ edges. But I would be happy with a graph that would INDUCE the dominator graph by transitivity.

So, in the example above, instead of ⁿC₂ edges, it is sufficient to keep n - 1 edges.

This is not from any contest. It's just something that I'm curious about and haven't been able to make progress on. I don't even know if this graph is going to be sparse enough to be explicitly computed.

I was solving this interesting number-theory + trees problem. And I came up with an solution where n ≤ 200000.

My idea is that the answer for every node will either be a factor of the root or be a factor of the number itself, and only these about values need to be tested.

However, this submission am getting TLE with this idea. The solution in the editorial is a slight optimization of my idea -
(a) either the answer is a factor of the root (because root is NOT marked as 0)
(b) or it's the GCD of all the ancestors except the root (because the root IS marked as 0).

This has the complexity of O(n * k) where k =  number of factors of the root value, and . Thus the editorial solution and my solution have the same (theoretical) complexity.

Could you suggest was that are C++ implementation optimizations that I could use to improve my solution and avoid the TLE even though I am testing out both factors of root and factors of the node? I did try to cache the values of the root and the node, but that leads to a stack overflow.

I am not looking for the obvious optimizations of implementing the editorial solution.

In programming contests, I see that many of the codes that require an implementation of a balanced BST actually use a splay tree. Why do you use them over other trees that offer stronger guarantees such as AVL trees and Red Black?

For example, see this solution by tourist.

Are they that much faster than other trees (like quicksort or binary search trees)? Or do they have some interesting non-trivial properties that are especially useful? What I mean to ask is if there are questions where using a Splay Tree gives a much better result than using other kinds of trees.

I am trying to solve Problem M: Counting Marbles. I am writing an editorial in case somebody might need it after me, and I am also trying to ask for help in spotting the error in my code.

Editorial:
We are essentially trying to write the smallest base-365 number with the marbles. So we must minimize the earlier digits as much as possible.

Use a priority queue with the tops of the stack, and whenever you use a marble, remove it from the priority queue and put the next element in the queue instead. Please see my solution for one such implementation.

Help: My solution is able to run on the sample test cases, but I'm getting WA (could somebody take a look at this)?

My solution: https://www.ideone.com/VnKScW
Problem Statement: http://mirror.codeforces.com/gym/101889/attachments/download/7471/statements-2017-latam-regional.pdf

EDIT: This editorial is incorrect.

Hi codeforces,

I was attempting to solve the KMP problem below, but I'm failing on testcase 3.When I run the testcase locally, I am getting the correct answer on my machine. Could somebody help spot the bug that is probably causing undefined behaviour?

Problem: http://mirror.codeforces.com/contest/471/problem/D Solution: http://mirror.codeforces.com/contest/471/submission/31585259

I have been trying to solve the problem Nudist Beach, here at http://mirror.codeforces.com/contest/553/problem/D. However, I find that when I submit I get a different output as that from ideone, or my local compiler. Even more strangely I get different results depending on whether I submit the file, or whether I copy-paste the code into the editor.

When I submit by file, I get a response of WA on the first testcase. When I submit by copy-paste, I get time limit exceeded. When I run the same code in ideone, or my local compiler, for the first testcase, I get the correct output instantaneously.

Please find attached the following code-links. Ideone link. http://ideone.com/INKqhS. WA submission link. http://mirror.codeforces.com/contest/553/submission/19136417 TLE submission link. http://mirror.codeforces.com/contest/553/submission/19136401

Is this an error in the compiler/judge, or is it at my end? Thanks for taking a look at this.