As my english is not very good, please if you see any mistake write me a private message about it.

443A - Anton and Letters

In this task you are to count the number of different letters in the set. In my opinion the easiest way to do this looks like this. You just iterate over all small latin letters and check if the string contains it (with built-in functions).

443B - Kolya and Tandem Repeat

Let's add k question marks to the string. Than we can check all possible starting and ending positions of tandem repeat in a new string. We can check each of them in time O(n + k). We only need to check that some symbols are equal (in our task question mark is equal to every symbol).

442A - Borya and Hanabi

It's obvious that the order of hints doesn't metter. There are 10 types of hints, so we can try all 2¹⁰ vartiants of what other players should do. Now we need to check if Boris can describe all of his cards. He can do it iff he can distinguish all pairs of different cards. He can do it if somebody told at least one distinction. It can be a hint about color of one of cards (if they don't have same one) or it can be hint about value of some card.

442B - Andrey and Problem

Let's sort all friends in such a way that p_i ≤ p_j iff i ≤ j. If there is p_i = 1 Andrey should ask only this friend. Now we can assume that all probabilities are less then 1. What should we maximize?

Let , . Assume we already have some group of people we would ask a help. Let's look what will happen with the probability of success if we add a friend with probability p_i to this group:

It means adding a new people to group will increase a probability of success only if S < 1. Now let's look at another question. We have some group of people with S < 1. And we want to add only one friend to this group. Which one is better? Let the probability of the first friend is p_i and the second friend is p_j. It's better to add first one if

Δ_i - Δ_j = P·p_i·(1 - S) - P·p_j·(1 - S) = P·(1 - S)·(p_i - p_j) > 0. As S < 1 we get p_i > p_j.

But it's only a local criteria of optimality. But, we can prove that globally you should use only a group of people with the biggest probabilities. We can use proof by contradiction. Let's look at the optimal answer with biggest used suffix (in the begining of editorial we sort all friends). Of all such answers we use one with minimum number of people in it. Where are two friends i and j (p_i < p_j) and i-th friend is in answer and j-th isn't. Let's look at the answer if we exclude i-th friend. It should be smaller because we used optimal answer with minimum numer of people in it. So adding a new people to this group will increase success probability. But we know that adding j-th is better than i-th. So we have found a better answer.

So we have a very easy solution of this problem. After sorting probabilities we should you some suffix of it. Because of sorting time complexity is O(nlogn).

442C - Artem and Array

It's obvious that we should never delete the first and last elements of array. Let's look at the minimum number. Let it be x and there are n elements in the array. We can subtract x from all elements and the answer for the problem will decrease on (n - 2)·x, becouse we will do n - 2 delitions of middle elements and each of this delitions will not give Artem exectly x more points.

If minimal element was the first or the last one, we can not to count it now (it equals to 0 now, so it will not affect the answer now). If it locates in the middle of array, we can prove that there is exist an optimal solution when Artem deletes this element on first move. We can prove it by contradaction. Let's look at the optimal answer where the minimal element is deleted on the minimal possible move (but not on first one). We can prove that we can delete it earlier. If move which is exactly before deleting minimum uses element of array which isn't a neighbour of minimual one we can swap this two delitions and it will not affect the answer. If those elements are neighbours we can write down the number of points which we obtain in both cases and understand that to delete minimum first is the best choice.

So, in this task we need to maintain a set of all not deleted elements and to find a smallest alive element. All of it we can do with built-in data structures in time O(nlogn).

442D - Adam and Tree

First, let's solve the task with already built tree. We can do it with easy dymanic programming. We will count the answer for subtree with an edge to the parent. If we can count it for all vertices we can calculate the answer for the whole tree as maximum of answers for children of root. How to calculate it for one vertex? Suppose we already know answers for children of this vertex. We should color the edge to the parent in the same color as edge to the child with maximum answer. Let two maximum answers for child be max₁ and max₂ then the answer for this vertex would be max(max₁, max₂ + 1) if max₁ ≥ max₂.

What changes when we can add new vertices? Nothing. We can calculate the value of dynamic programming for new vertex (it always would be 1) and recalculate value for its parent. If it doesn't change we should stop this process, in another case we continue recalculations of dynamic programming values: go to its parent and recalculate answer for it and so on. If we maintain two maximums for each vertex in O(1) the asymptotic of the algorithm would be O(nlogn).

To prove it we can use some facts about Heavy-light decomposion. We can use the way Heavy-light decomposion splits edges of tree as our decomposition. We know that answer for such decomposition will be less than logarithm of the number of vertices. So each value of dynamic programming will be increased not more than O(logn) times.

442E - Gena and Second Distance

To solve this problem we can use a binary search. How do we check that answer if not less than R? It means that we can draw a circle with such radius which center locates in the rectangle and there are no more than one point inside this circle. How could we check it? We always can shift this circle in such a way that at least one point would be on its border. We can try all points as one which is on border. Than we should draw a circle with center in it and intersect it with n - 1 circles built on other points. If there is a point on this circle which is covered with no more than one other circle, than answer is greater or equal R. Finding such point is almost a typical problem which can be solved in O(klogk) where k — number of intersections points of circles.

We described a solution which works in O(logAnswer·n²·logn). But we can make it faster. Let's try all vertices as centers of circles and inside this loop make a binary search. We can make one optimize: if we can't find a point on circle with radius which is equal to the best now known than we shouldn't do a binary search in this point (because we can't increase the answer). It can be proved that this solution in avarage case works in O(logAnswer·nlog²n + n²logn) if we shuffle points. It's true because a binary search will be used in avarage only logn times. To prove this fact let's look at probability of binary search to be used in i-th step. If all values are different and shuffled it is . It is known that sum of first n elements of this sirie is bounded by logn.

In this task there are some technical issues you need to know about. For example, we would do a binary search only O(logn) times if we find a stricly incresing subseqence of answers. That's why before using a binary search we should check that we can obtain not current answer but current answer plus some small value. Also we need to understand what "small value" is (it should be something like eps·curAnswer, where eps = 10^- 9, in another case you will probably have some problems with accuracy).

Also one interesting fact about this problem. If you write a solution with time compexity equal to O(logAnswer·n²·logn), it will work very fast on random tests becaue there are will be a very small number of circle intersections.