17.md (9485B)
1 Source: https://codeforces.com/blog/entry/451 2 3 [Contest discussion](https://codeforces.com/blog/entry/447) 4 **Problem A. Noldbach problem**To solve this problem you were to find prime numbers in range [2..*N*]. The constraints were pretty small, so you could do that in any way - using the Sieve of Eratosthenes or simply looping over all possible divisors of a number. 5 Take every pair of neighboring prime numbers and check if their sum increased by 1 is a prime number too. Count the number of these pairs, compare it to *K* and output the result. 6 7 **Problem B. Hierarchy** 8 9 Note that if employee, except one, has exactly one supervisor, then our hierarchy will be tree-like for sure. 10 For each employee consider all applications in which he appears as a subordinate. If for more than one employee there are no such applications at all, it's obvious that - 1 is the answer. In other case, for each employee find such an application with minimal cost and add these costs to get the answer. 11 Alternatively, you could use Kruskal's algorithm finding a minimum spanning tree for a graph. But you should be careful so that you don't assign the second supervisor to some employee. 12 And yes, the employees' qualifications weren't actually needed to solve this problem :) 13 14 **Problem C. Balance** 15 Consider the input string *A* of length *n*. Let's perform some operations from the problem statement on this string; suppose we obtained some string *B*. Let *compression* of string *X* be a string *X*' obtained from *X* by replacing all consecutive equal letters with one such letter. For example, if *S* = "*aabcccbbaa*", then its compression *S*' = "*abcba*". 16 Now, consider compressions of strings *A* and *B* - *A*' and *B*'. It can be proven that if *B* can be obtained from some string *A* using some number of operations from the problem statement, then *B*' is a subsequence of *A*', and vice versa - if for any strings *A* and *B* of equal length *B*' is a subsequence of *A*', then string *B* can be obtained from string *A* using some number of operations. 17 Intuitively you can understand it in this manner: suppose we use some letter *a* from position *i* of *A* in order to put letter *a* at positions *j*..*k* of *B* (again, using problem statement operations). Then we can't use letters at positions 1..*i* - 1 of string *A* in order to influence positions *k* + 1..*n* of string *B* in any way; also, we can't use letters at positions *i* + 1..*n* of string *A* in order to influence positions 1..*j* - 1 of string *B*. 18 19 Now we have some basis for our solution, which will use dynamic programming. We'll form string *B* letter by letter, considering the fact that *B*' should still be a subsequence of *A*' (that is, we'll search for *B*' in *A*' while forming *B*). For this matter we'll keep some position *i* in string *A*' denoting where we stopped searching *B*' in *A*' at the moment, and three variables *kA*, *kB*, *kC*, denoting the frequences of characters *a*, *b*, *c* respectively in string *B*. Here are the transitions of our DP: 20 1) The next character of string *B* is *a*. Then we may go from the state (*i*, *kA*, *kB*, *kC*) to the state (*next**i*, '*a*', *kA* + 1, *kB*, *kC*). 21 2) The next character of string *B* is *b*. Then we may go from the state (*i*, *kA*, *kB*, *kC*) to the state (*next**i*, '*b*', *kA*, *kB* + 1, *kC*). 22 3) The next character of string *B* is *c*. Then we may go from the state (*i*, *kA*, *kB*, *kC*) to the state (*next**i*, '*c*', *kA*, *kB*, *kC* + 1). 23 Where *next**i*, *x* is equal to minimal *j* such that *j* ≥ *i* and *A*'*j* = *x* (that is, the nearest occurrence of character *x* in *A*', starting from position *i*). Clearly, if in some case *next**i*, *x* is undefined, then the corresponding transition is impossible. 24 Having calculated *f*(*i*, *kA*, *kB*, *kC*), it's easy to find the answer:  for all triples *kA*, *kB*, *kC* for which the balance condition is fulfilled. 25 26 Such a solution exceeds time and memory limits. Note that if string *B* is going to be balanced, then *kA*, *kB*, *kC* ≤ (*n* + 2) / 3, so the number of states can be reduced up to 27 times. But it's also possible to decrease memory usage much storing matrix *f* by layers, where each layer is given by some value of *kA* (or *kB* or *kC*). It's possible since the value of *kA* is increased either by 0 or by 1 in each transition. 27 28 The overall complexity is *O*(*N*4) with a quite small constant. 29 **Problem D. Notepad** 30 31 The answer to the problem is *b**n* - 1 * (*b* - 1) mod *c*. The main thing you should be able to do in this problem - count the value of *A**B* mod *C* for some long numbers *A* and *B* and a short number *C*. Simple exponentiation by squaring exceeds time limit since to converse of *B* to binary you need about *O*(|*B*|2) operations, where |*B*| is the number of digits in decimal representation of number *B*. 32 The first thing to do is to transform *A* to *A* mod *C*. It isn't difficult to understand that this transformation doesn't change the answer. 33 Let's represent *C* as *C* = *p*1*k*1*p*2*k*2...*p**m**k**m*, where *p**i* are different prime numbers. 34 Calculate *t**i* = *A**B* mod *p**i**k**i* for all *i* in the following way. There are two possible cases: 35 1) *A* is not divisible by *p**i*: then *A* and *p**i* are coprime, and you can use [Euler's theorem](https://en.wikipedia.org/wiki/Euler%27s_theorem): *A**B*' = *A**B* (mod *C*), where *B*' = *B* mod φ(*C*) and φ(*C*) is Euler's totient function; 36 2) *A* is divisible by *p**i*: then if *B* ≥ *k**i* then *t**i* = *A**B* mod *p**i**k**i* = 0, and if *B* < *k**i* then you can calculate *t**i* in any way since B is very small. 37 Since all *p**i**k**i* are pairwise coprime you may use [chinese remainder theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) to obtain the answer. 38 39 You can also use Euler's theorem directly. Note that if for some *B*1, *B*2 ≥ 29 you know that |*B*1 - *B*2| mod φ(*C*) = 0, then all *t**i* for them will be the same (29 is the maximal possible value of *k**i*). Using that you may reduce *B* so that it becomes relatively small and obtain the answer using exponentiation by squaring. 40 41 There is another solution used by many contestants. Represent *B* as *B* = *d*0 + 10*d*1 + 102*d*2 + ... + 10*m**d**m*, where 0 ≤ *d**i* ≤ 9 (in fact *d**i* is the *i*-th digit of *B* counting from the last). Since *a**x* + *y* = *a**x*· *a**y*, you know that *A**B* = *A**d*0· *A*10*d*1· ...· *A*10*m**d**m*. The values of *u**i* = *A*10*i* can be obtained by successive exponentiation (that is, *u**i* = *u**i* - 110); if you have *A*10*i*, it's easy to get *A*10*i**d**i* = *u**i**d**i*. The answer is the product above (modulo *C*, of course). 42 43 **Problem E. Palisection** 44 The first thing to do is to find all subpalindromes in the given string. For this you may use a beautiful algorithm described for example [here](http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/). In short, this algorithm find the maximal length of a subpalindrome with its center either at position *i* of the string or between positions *i* and *i* + 1 for each possible placement of the center. 45 For example, suppose that the maximal subpalindrome length with center at position *i* is 5; it means that there are three subpalindromes with center at *i*, with lengths 1 (*i*..*i*), 3 (*i* - 1..*i* + 1) and 5 (*i* - 2..*i* + 2). In general, all starting and finishing positions of subpalindromes with a fixed center lie on some interval of positions, which is pretty easy to find. 46 Let's find for each position *i* the value of *start**i*, which is equal to the number of subpalindromes starting at position *i*. All these values can be found in linear time. Let's create an auxiliary array *a**i*. If after processing a position in the string some new pack of subpalindromes was found and they start at positions *i*..*j*, then increase the value of *a**i* by 1, and decrease the value of *a**j* + 1 by 1. Now . Proving this fact is left as an exercise to the reader :) 47 In a similar way it's possible to calculate *finish**i*, which is equal to the number of subpalindromes finishing at position *i*. 48 Since it's easy to count the total number of subpalindromes, let's find the number of **non**-intersecting pairs of subpalindromes and subtract this number from the total number of pairs to obtain the answer. Note that if two subpalindromes don't intersect then one of them lies strictly to the left of the other one in the string. Then, the number of non-intersecting pairs of subpalindromes is equal to:  49 This can be calculated in linear time if the value of  is recalculated by addition of *finish**i* before moving from position *i* to position *i* + 1. 50 The overall complexity of the algorithm is *O*(*N*).