557.md (6691B)
1 Source: https://codeforces.com/blog/entry/18943 2 3 ## [557A — Ilya and Diplomas](https://codeforces.com/problemset/problem/557/A) 4 5 This problem can be solved in the different ways. We consider one of them — parsing cases. 6 7 If *max*1 + *min*2 + *min*3 ≤ *n* then the optimal solution is (*n* - *min*2 - *min*3, *min*2, *min*3). 8 9 Else if *max*1 + *max*2 + *min*3 ≤ *n* then the optimal solution is (*max*1, *n* - *max*1 - *min*3, *min*3). 10 11 Else the optimal solution is (*max*1, *max*2, *n* - *max*1 - *max*2). 12 13 This solution is correct because of statement. It is guaranteed that *min*1 + *min*2 + *min*3 ≤ *n* ≤ *max*1 + *max*2 + *max*3. 14 15 Asymptotic behavior of this solution — O(1). 16 17 ## [557B — Pasha and Tea](https://codeforces.com/problemset/problem/557/B) 18 19 This problem can be solved in different ways too. We consider the simplest solution whici fits in the given restrictions. 20 21 At first we sort all cups in non-decreasing order of their volumes. Due to reasons of greedy it is correct thatsorted cups with numbers from 1 to *n* will be given to girls and cups with numbers from *n* + 1 to 2 * *n* will be given to boys. 22 23 Now we need to use binary search and iterate on volume of tea which will be poured for every girl. Let on current iteration (*lf* + *rg*) / 2 = *mid*. Then if for *i* from 1 to *n* it is correct that *mid* ≤ *a**i* and for *i* from *n* + 1 to 2 * *n* it is correct that 2 * *mid* ≤ *a**i* then we need to make *lf* = *mid*. Else we need to make *rg* = *mid*. 24 25 Asymptotic behavior of this solution — O(*n* * *log*(*n*)) where *n* — count of cups. 26 27 ## [557C — Arthur and Table](https://codeforces.com/problemset/problem/557/C) 28 29 This problem can be solved as follows. At first we need to sort all legs in non-descending order of their length. Also we need to use array *cnt*[]. 30 31 Let iterate on length of legs (which will stand table) from the least. Let this lenght is equals to *maxlen*. Count of units of energy which we need for this we will store in variable *cur*. 32 33 Obviously that we must unscrew all legs with lenght more than *maxlen*. For calculate count of units of energy for doing it we can use array with suffix sums, for exapmle. Then we add this value to *cur*. 34 35 If count of legs with length *maxlen* is not strictly greater than the number of the remaining legs then we need to unscrew some count of legs with length less than *maxlen*. For this we can use array *cnt*[]. In *cnt*[*i*] we will store count of legs with difficulty of unscrew equals to *i*. In this array will store information about legs which already viewed. 36 37 We will iterate on difficulty of unscrew from one and unscrew legs with this difficulties (and add this difficulties to variable *cur*) while count of legs with length *maxlen* will not be strictly greater than the number of the remaining legs. 38 39 When it happens we need to update answer with variable *cur*. 40 41 Asymptotic behavior of this solution — O(*n* * *d*), where *n* — count of legs and *d* — difference between maximal and minimal units of energy which needed to unscrew some legs. 42 43 ## [557D — Vitaliy and Cycle](https://codeforces.com/problemset/problem/557/D) 44 45 To solve this problem we can use dfs which will check every connected component of graph on bipartite. It is clearly that count of edges which we need to add in graph to get the odd cycle is no more than three. 46 47 Answer to this problem is three if count of edges in graph is zero. Then the number of ways to add three edges in graph to make odd cycle is equals to *n* * (*n* - 1) * (*n* - 2) / 6 where *n* — count of vertices in graph. 48 49 Answer to this problem is two if there is no connected component with number of vertices more than two. Then the number of ways to add two edges in graph to make odd cycle is equals to *m* * (*n* - 2) where *m* — number of edges in graph. 50 51 Now we have one case when there is at least one connected component with number of vertices more than two. Now we need to use dfs and try to split every component in two part. If for some component we can't do it that means that graph already has odd cycle and we need to print "0 1" and we can now finish our algorithm. 52 53 If all connected components in graph are bipartite then we need to iterate on them. Let *cnt*1 is the count of vertices in one part of current component and *cnt*2 — count of vertices in the other part. If number of vertices in this component more than two we need to add to answer *cnt*1 * (*cnt*1 - 1) / 2 and *cnt*2 * (*cnt*2 - 1) / 2. 54 55 Asymptotic behavior of this solution — O(*n* + *m*), where *n* — number of vertices in graph and *m* — number of edges. 56 57 ## [557E — Anya and Half-palindrome](https://codeforces.com/problemset/problem/557/E) 58 59 This problem can be solved with help of dynamic programming. 60 61 At first we calculate matrix *good*[][]. In *good*[*i*][*j*] we put *true*, if substring from position *i* to position *j* half-palindrome. Else we put in *good*[*i*][*j*]*false*. We can do it with iterating on "middle" of half-palindrome and expanding it to the left and to the right. There are 4 cases of "middle" but we omit it because they are simple enough. 62 63 Now we need to use Trie and we will put in it suffixes of given string. Also we will store array *cnt*[]. In *cnt*[*v*] we will store number of half-palindromes which ends in vertex *v* of our Trie. Let now we put in tree suffix which starts in position *i*, current symbol of string which we put is in position *j* and we go in vertex *v* of out Trie. Then if *good*[*i*][*j*] = *true* we add one to *cnt*[*v*]. 64 65 Now with help of dfs let calculate for every vertex *sum*[*v*] — sum of numbers which stored in array *cnt*[] for vertex *v* and for vertices in all subtrees of vertex *v*. 66 67 It is left only to restore answer. Start from root of our Trie. We will store answer in variable *ans*. In variable *k* store number of required substring. Let now we in vertex *v*, by letter '*a*' we can go in vertex *to**a* and by letter '*b*' — in vertex *to**b*. 68 69 Then if *sum*[*to**a*] ≤ *k* we make *ans* + = '*a*' and go in vertex *to**a* of our Trie. Else we need to make as follows: *k* — = *sum*[*to**a*], *ans* + = '*b*' and go in vertex *to**b* of our Trie. 70 71 When *k* will be ≤ 0 print resulting string *ans* and finish algorithm. 72 73 Asymptotic behavior of this solution — O(*szalph* * *n*2) where *szalph* — size of input alphabet (in this problem it equals to two) and *n* — length of given string.