We can, in O(2^n * n), if n is the number of digits, brute force every possible sequence of deletions, and then check if the string we have got left is a square or not.

Обожаю русскоговорящее сообщество, за что хоть минусы ? картинка не понравилась ?

Решение с этой логикой

JFYI пока это решение с наименьшим потреблением памяти и временем работы. Еще раз спасибо за минуса :).

No, it means that if you have three points A < B < C then it's allowed (not necessarly) to connect A and B with a cable without connecting C with them (but you can connect if you want A-B and A-C)

Thank you. It's helpful for me.

Consider a back-edge (u, v) and the corresponding cycle u, p₁, ..., p_k, v. Let's suppose that this is the first back-edge we process. Following the code from the editorial, after processing this cycle we see that leader(p_i) = leader(p_j) = v for all i, j. Note that we exclude u. This is done to exclude situations like articulation points that belong to more than one simple cycle.

Let's now take into account this part of the code:

vector<int> sizes(k);
for (int i =  0; i < k; i++)
    sizes[leader(i)]++;

And the statement you do not understand:

Now, it is sufficient to the answer to take such paths plus the corresponding reverse edge that do not intersect with others (that is, the size of the DSU component is 1)

Let's consider again our cycle u, p₁, ..., p_k, v. If our graph had only this back-edge then we see that all the edges from the cycle belong to exactly one simple cycle, as another back-edge would be needed to have at least one additional cycle. However, imagine these two following cases:

1. There was another back-edge (t, v). This means that, in the previous piece of code, the statement sizes[leader(v)]++ will be executed twice. With this we know that at least the edge (v, par(v)) belongs to more than one cycle, which implies that all the other edges from the cycle (plus some other ones) also belong to more than one cycle.
2. There was another back-edge (t, p_i). This means the same as the previous point, because we know that leader(v) = leader(p_i), so sizes[leader(v)] will be again at least two. In fact, this is the same as case 1, but I wanted to illustrate it better. At least the edge (p_i, par(p_i)) belongs to more than one cycle, which implies that the other ones will do, too.

Note that you do not need to care about vertices that do not form part of any simple cycle, as they will not appear (if they did, this means that you have reached them by iterating the endpoint of some back-edge, which means that they belong to a cycle, which is a contradiction).

With this criteria you can safely take all the edges obtained by iterating some lower endpoint of a back-edge (u, v) such that sizes(leader(v)) = 1

We don't have any red or blue vertices before the first purple city and after the last purple city so we just have to calculate how to connect cities between that pair of purple cities. Using the first method we can have roads (-12P, -9B, 2B, 8B, 15P) and (-12P, -2R, -1R, 15P) and that way we have connected both red cities with purple cities and blue cities with purple cities but the total lentgh is basically twice the distance between purple cities which is 2*(15-(-12))=54

just connect all the 'b' and 'p' linearly(cost = 27) and similarly all the 'r' and 'p' (cost = (15 — (-12)) i.e. 27. So, 54.

Go through this article : https://arxiv.org/pdf/1603.00580.pdf

I know it's been a while, but did you figure out what carcass meant?

Yes, you are right.

The correct claim is: Find any fundamental set of cycles. Any edges belongs to exactly one simple cycle if and only if it belongs to a fundamental cycle that does not intersect any other fundamental cycle. Somehow the editorial wrote a totally wrong statement and still followed the correct way.