455.md (11030B)
1 Source: https://codeforces.com/blog/entry/13336 2 3 Warning: my English is very bad. 4 5 [456A - Laptops](/contest/456/problem/A "Codeforces Round 260 (Div. 2)") 6 7 Solution: [7407613](/contest/456/submission/7407613 "Submission 7407613 by netman"); 8 9 In this task you need to check the existense of such pair *i* and *j*, such that *i* ≠ *j*, *a*[*i*] < *a*[*j*], *b*[*i*] > *b*[*j*]. If such *i* and *j* exist, Alex is happy. 10 11 There is very simple solution. Let's check that for all *i* *a*[*i*] = *b*[*i*]. If this condition is true we should print "Poor Alex". We can easy prove it. Let's sort arrays *a* and *b* like pair of numbers in increasing order. We can see that Alex is happy if we have at least one inversion in array *b*, i.e there is such pair *i* and *j* that *b*[*i*] > *b*[*j*] и *i* < *j* (). i.e it means that array *b* is not sorted and it's means that *a* ≠ *b*. 12 13 [456B - Fedya and Maths](/contest/456/problem/B "Codeforces Round 260 (Div. 2)") 14 15 Solutions: [7407625](/contest/456/submission/7407625 "Submission 7407625 by netman"), [7407631](/contest/456/submission/7407631 "Submission 7407631 by netman"); 16 17 In this task you need to calculate formula that given in the statement, but it's hard to calculate it with the naive way. 18 19 But we can transform our formula to this: 20 21  22 23 This formula is right because 5 is prime number and it's coprime with 1, 2, 3, 4. 24 25 φ(5) = 4 26 27 To solve this task we should be able to calculate remainder of division *n* by 4 and calculate formula for small *n*. 28 29 Asymptotics — . 30 31 There is also another solution. It uses a fast exponentiation, but not binary exponentiation. The idea of this exponentiation is the same as that of the binary exponentiation. Let we want to fast calculate *x**n**modP*. Algorithm is very simple. Let process digits of n moving from end to begin. Let *Result* — current result and *K* — *x*(10*i*), *i* — number of the currently processed digit (digits are numbered from the end. Used 0-indexation). During processing of digits, we must update result: , *c*[*i*] — *i*-th digit of the number *n* (digits are numbered from the end). 32 33 Asymptotics — . 34 35 [456C - Boredom](/contest/456/problem/C "Codeforces Round 260 (Div. 2)") / [455A - Boredom](/contest/455/problem/A "Codeforces Round 260 (Div. 1)") 36 37 Solutions: [7407649](/contest/455/submission/7407649 "Submission 7407649 by netman"), [7407655](/contest/455/submission/7407655 "Submission 7407655 by netman"); 38 39 In this task we need to maximize the sum of numbers that we took. Let precalc array *cnt*. *cnt*[*x*] — number of integers *x* in array *a*. Now we can easily calculate the DP: 40 41 *f*(*i*) = *max*(*f*(*i* - 1), *f*(*i* - 2) + *cnt*[*i*]·*i*), 2 ≤ *i* ≤ *n*; 42 43 *f*(1) = *cnt*[1]; 44 45 *f*(0) = 0; 46 47 The answer is *f*(*n*). 48 49 Asymptotics — *O*(*n*). 50 51 [456D - A Lot of Games](/contest/456/problem/D "Codeforces Round 260 (Div. 2)") / [455B - A Lot of Games](/contest/455/problem/B "Codeforces Round 260 (Div. 1)") 52 53 Solutions: [7407663](/contest/455/submission/7407663 "Submission 7407663 by netman"), [7407670](/contest/455/submission/7407670 "Submission 7407670 by netman"); 54 55 To solve this problem we need the prefix tree(trie), which will have all the strings from the group. Next we will calculate the two DP: win[v] — Can player win if he makes a move now (players have word equal to prefix *v* in the prefix tree(trie)). lose[v] — Can player lose if he makes a move now (players have word equal to prefix *v* in the prefix tree(trie)). 56 57 if *v* is leaf of trie, then win[v] = false; lose[v] = true; 58 59 Else *win*[*v*] = (*win*[*v*] *or* (*not* *win*[*i*])); *lose*[*v*] = (*lose*[*v*] *or* (*not* *lose*[*i*])), such *i* — children of vertex *v*. 60 61 Let's look at a few cases: 62 63 If *win*[*v*] = *false*, then second player win (first player lose all games). 64 65 If *win*[*v*] = *true* и *lose*[*v*] = *true*, then first player win (he can change the state of the game in his favor). 66 67 If *win*[*v*] = *true* and *lose*[*v*] = *false*, then if , then first player win, else second player win. 68 69 Asymptotics — . 70 71 [456E - Civilization](/contest/456/problem/E "Codeforces Round 260 (Div. 2)") / [455C - Civilization](/contest/455/problem/C "Codeforces Round 260 (Div. 1)") 72 73 Solutions: [7407681](/contest/455/submission/7407681 "Submission 7407681 by netman"), [7407683](/contest/455/submission/7407683 "Submission 7407683 by netman"); 74 75 You can see that the road system is a forest. For efficient storage component we need to use DSU. First, we need to build the initial system of roads. For each component of the initial road system, we must find the diameter of component. This can be done using a DFS or BFS. Let *a* — any vertex of component. Let *b* — furthest vertex from vertex *a*. Let *c* — furthest vertex from vertex *b*. Diameter equal to distance from *b* to *c*. This algorithm for finding the diameter is correct only for tree. For each component in the DSU, we know its diameter. 76 77 Now it is very easy to answer the query of the $1$st type: To know the component which contains the vertex *x* and output diameter of this component. Query of the $2$nd type also very easy to process: Let *u* — of component in which lie the vertex *x*, *v* — of component in which lie the vertex *y*. If *u* ≠ *v*, then we can merge components: The diameter of the new component is computed as follows: 78 79  80 81 Asymptotics — *O*(*n*·*A*- 1(*n*)), где *A*- 1(*n*) — inverse Ackermann function. 82 83 [455D - Serega and Fun](/contest/455/problem/D "Codeforces Round 260 (Div. 1)") 84 85 Solutions: [7407693](/contest/455/submission/7407693 "Submission 7407693 by netman"), [7407699](/contest/455/submission/7407699 "Submission 7407699 by netman"), [7407703](/contest/455/submission/7407703 "Submission 7407703 by netman"); 86 87 Let's change the query type 1 to two more simple requests: 88 89 Erase a number from *r*-th position. Insert this number after (*l* - 1)-th position. 90 91 Now let's keep our array as  blocks. In each block will store the numbers themselves in such a manner as in the array *a* and will store an array *cnt*. *cnt*[*x*] — number of integers *x* in block. This requires *O*(*n* *sqrtn*) space. 92 93 Now we can fast process the queries of the 1st type. We can erase number from *r*-th position in  operations. And we can insert this number after (*l* - 1)-th position in  operations. Also we can fast recalc *cnt* after transformations. 94 95 Also we can fast process the queries of the 96 97 Unable to parse markup [type=CF_TEX] 98 99 O (\ sqrt n) $ numbers are in blocks, which are partly lie within the boundaries of the query. 100 101 To keep the size of the blocks close to , we need rebuild our structure after each -th query of the 1st type. We can rebuild structure in *O*(*n*) operations. 102 103 Asymptotics — . 104 105 [455E - Function](/contest/455/problem/E "Codeforces Round 260 (Div. 1)") 106 107 Solutions: [7407711](/contest/455/submission/7407711 "Submission 7407711 by netman"), [7452418](/contest/455/submission/7452418 "Submission 7452418 by netman"); 108 109 In this problem you should quickly be able to compute the function described in the statement. 110 111 You may notice that this task is equivalent to next task: 112 113 Go through the array *a*, starting from the position of *y*, making (*x* - 1) step. Step might be: step to the left or to stay in place. 114 115 Function is calculated as follows: , *k**i* — how many times we visited the *i* th element of the array *a*. 116 117 For a fixed *l* is clear, it is most optimally that a minimum on the interval [*l*, *y*] has been visited by (*x* - (*y* - *l*)) times, and all the other numbers once. 118 119 You may notice that optimally to *a*[*l*] was a minimum. 120 121 From all this we can conclude that for a fixed *l* answer is — *sum*[*y*] - *sum*[*l*] + *a*[*l*]·(*x* - (*y* - *l*)), where *sum* — an array of prefix sums of array *a*. 122 123 Above formula can be written as follows: 124 125 *sum*[*y*] - *sum*[*l*] + *a*[*l*]·(*x* - (*y* - *l*)) = *sum*[*y*] - *sum*[*l*] + *a*[*l*]·(*x* - *y* + *l*) = *sum*[*y*] - *sum*[*l*] + *a*[*l*]·*l* + *a*[*l*]·(*x* - *y*) = *sum*[*y*] + (*a*[*l*]·(*x* - *y*) + *a*[*l*]·*l* - *sum*[*l*]) 126 127 You may notice that in brackets something like the equation of the line — *K*·*X* + *B*. That's very similar to the equation of the line: *a*[*l*]·(*x* - *y*) + *a*[*l*]·*l* - *sum*[*l*], where *K* = *a*[*l*], *X* = (*x* - *y*), *B* = *a*[*l*]·*l* - *sum*[*l*]. 128 129 Now we must find minimum for all *l* and fixed *X* = (*x* - *y*). 130 131 We have *n* lines, i. e. for every element in array *a* one line (*K**i*, *B**i*). 132 133 Answer for query equal to: 134 135 , where (*K**i*, *B**i*) — *i*-th line. *K**i* = *a*[*i*], *B**i* = *a*[*i*]·*i* - *sum*[*i*]. 136 137 For fast answer calculation we must use Convex Hull Trick with segment tree. In every vertex of segment tree we keep all lines for segment of this vertex. This requires  space, because each line lies in  vertices. And we can answer query in  operations. Because we visit  vertices and each vertex need in  operations. You can learn the theory about Convex Hull Trick [here](http://wcipeg.com/wiki/Convex_hull_trick).