23.md (4983B)
1 Source: https://codeforces.com/blog/entry/530 2 3 ### A. [You're given a string...](../../../contest/23/problem/A) 4 5 6 Iterate over all substrings, starting with the longest ones, and for each one count the number of appearances. The complexity is *O*(*L*4) with a small multiplicative constant. 7 8 9 ### B. [Party](../../../contest/23/problem/B) 10 11 12 It's clear that at least one person (the one with the least number of friends) will have to leave. We claim that at least two persons will leave. Indeed, suppose that only one person left, and he had *d* friends. Then all other people had more than *d* friends before he left, and after that they had less than *d* + 1 friends, i.e. not more than *d*. So, his leaving influenced the number of friends for every other person, which means that he was friends with everyone: *d* = *N* - 1. But he has fewer friends than everyone — a contradiction. 13 14 So, the answer is not more than *N* - 2. We'll prove that it's possible for *N* - 2 people to stay (of course, if *N* > 1). The graph of friendship will be the following: take a complete graph on *N* vertices and delete one edge. Then the degrees of two vertices equal *N* - 2, and other degrees equal *N* - 1. After the first two vertices are removed, we have a complete graph on *N* - 2 vertices, and all degrees equal *N* - 3, which means that no one else will leave. 15 16 17 ### C. [Oranges and Apples](../../../contest/23/problem/C) 18 19 20 Sort the boxes in increasing number of oranges. Count the total number of apples in boxes with odd and even numbers. If the boxes with odd numbers contain at least half of all apples, choose them (there are exactly *N* boxes with odd numbers). If the boxes with even numbers contain at least half of all apples, take them and the last box (which contains the largest number of oranges). It's easy to see that in both cases the conditions of the task are fulfilled. 21 22 23 ### D. [Tetragon](../../../contest/23/problem/D) 24 25 26 Let ABCD be the quadrangle that we're looking for, and K, L, and M be the middle points of equal sides AB, BC and CD, correspondingly. Let M' be the point symmetric to M with respect to L. Triangles BLM' and CLM are equal by two sides and angle, so BM' = CM = BL = BK, i. e. B is the circumcenter of the triangle KLM'. 27  28 Knowing B, we can reconstruct the whole quadrangle, using the symmetries with respect to the points K, L, and M, and then check whether it satisfies all conditions. 29 Note that we don't know which of the given points is L, so we need to check all 3 cases. 30 31 32 ### E. [Tree](../../../contest/23/problem/E) 33 34 35 **Lemma**. In one of optimal solutions there are no simple paths of length 3. 36 **Proof**. We can remove the middle edge from such a path. The connected component will split into two components of sizes *a* and *b*, where *a* ≥ 2, *b* ≥ 2, and therefore *ab* ≥ *a* + *b*. 37 38 We'll root the tree and calculate recursively the numbers *h**v* = the solution of the problem for the subtree with the root *v*, and *f**v* = the product of *h**u* for all children of *v*. If *v* is a leaf, then *h**v* = *f**v* = 1. 39 40 We show how to calculate *h**v*, given the solution for all subtrees of *v*. Consider the connected component of *v* in an optimal solution. It follows from the lemma that the component has one of the following types: 41 1. The single vertex *v*. 42 2. The vertex *v* and several children of *v*. 43 3. The vertex *v*, one child of *v* — *w*, and several children of *w*. 44 45 In the first case the result of the game is *f**v*. 46 47 In the second case it equals *Πf**i* · *Πh**j* · *k* = *Π*(*f**i* / *h**i*) · *f**v* · *k*, where *i* iterates over children belonging to the connected component, *j* iterates over the rest children, and *k* is the size of the component. Since we want to maximize the result, we're interested in children with the largest value of *f**i* / *h**i*. Therefore, the largest possible result in this case equals the maximum value of *Π**i* ≤ *s* (*f**i* / *h**i*) · *f**v* · (*s* + 1), where it's supposed that the children are sorted in descending order of *f**i* / *h**i*. 48 49 In the third case we can use a similar reasoning for every child *w*. The best result will be the maximum of the expression *f**v* · (*f**w* / *h**w*) · *Π**i* ≤ *s* (*f**i* / *h**i*) · (*s* + 2) as *w* iterates over children of *v*, and *s* iterates from 1 to the number of children of *w*; note that the children of *w* have already been sorted in the previous step. 50 51 Therefore, the number of operations necessary to calculate *f**v* is proportional to the total number of children and grandchildren of *v*, which is less than *n*. The complexity of the algorithm, then, is *O*(*n*2) (ignoring operations with long numbers).