515.md (13010B)
1 Source: https://codeforces.com/blog/entry/16468 2 3 Thanks to [johnathan79717](/profile/johnathan79717 "Master johnathan79717") fo polish my words. 4 5 #### [515-A Drazil and Date](//codeforces.com/problemset/problem/515/A) 6 7 If Drazil chooses the shortest path from (0,0) to (a,b), it takes |*a*| + |*b*| steps. 8 9 So we know that all numbers less than |*a*| + |*b*| are impossible to be the number of steps that Drazil took. 10 11 Now consider when the number of steps is not less than |*a*| + |*b*|. 12 13 When Drazil arrives at (*a*, *b*), he can take two more steps such as (*a*, *b*) -> (*a*, *b* + 1) -> (*a*, *b*) to remain at the same position. 14 15 So we know that for all *s* such that *s* ≥ |*a*| + |*b*| and (*s* - (|*a*| + |*b*|))%2 = 0, there exists a way for Drazil to get to (*a*, *b*) in exactly *s* steps. 16 17 The last part we should prove is that it's impossible for Drazil to arrive at (a,b) in exactly *s* steps when (*s* - (|*a*| + |*b*|))%2 = 1. 18 19 We can color all positions (*x*, *y*) where (*x* + *y*)%2 = 0 as white and color other points as black. 20 21 After each step, the color of the position you're at always changes. 22 23 So we know that it's impossible for Drazil to get to (*a*, *b*) in odd/even steps if the color of (*a*, *b*) is white/black. 24 25 Conclusion: If *s* ≥ |*a*| + |*b*| and (*s* - (|*a*| + |*b*|))%2 = 0 print "Yes", Otherwise print "No". 26 27 Time Complexity: *O*(1). 28 29 [author's code](//codeforces.com/contest/515/submission/9906268) 30 31 #### [515-B Drazil and His Happy Friends](//codeforces.com/problemset/problem/515/B) 32 33 You may notice that Drazil invites his friends periodically, and the period of invitation patterns is at most *n* * *m* (because there are only *n* * *m* possible pairs of boys and girls). 34 35 So if no one changes from unhappy to happy in consecutive *n* * *m* days, there won't be any changes anymore since then. 36 37 We can simulate the process of having dinner until there are no status changes in consecutive *n* * *m* days. 38 39 Because there are only n+m people, it's easy to prove the simulation requires O((*n* + *m*) * *n* * *m*) days. 40 41 But in fact, the simulation takes only O(*n* * *m*) days.(More accurately, the bound is (*min*(*n*, *m*) + 1) * (*max*(*n*, *m*) - 1) ) 42 43 What happens? You can do some experiments by yourself. =) (you can suppose that only one person is happy in the beginning.) 44 45 In fact, this problem can be solved in *O*(*n* + *m*). 46 47 Let *g* be the greatest common divisor of *n* and *m*. If the *i*-th person is happy, then all people with number *x* satisfying  will become happy some day because of this person. 48 49 So for each 0 ≤ *i* ≤ *g* - 1, we only need to check if there exists at least one person whose number mod *g* is *i* and is happy. 50 51 If it exists for all *i*, the answer is 'Yes', otherwise the answer is 'No'. 52 53 [author's code](//codeforces.com/contest/515/submission/9906294) 54 55 #### [515-C Drazil and Factorial](//codeforces.com/problemset/problem/515/C) 56 57 Conclusion first: 58 59 First, we transform each digit of the original number as follows: 60 61 0, 1 -> empty 62 63 2 -> 2 64 65 3 -> 3 66 67 4 -> 322 68 69 5 -> 5 70 71 6 -> 53 72 73 7 -> 7 74 75 8 -> 7222 76 77 9 -> 7332 78 79 Then, sort all digits in decreasing order as a new number, then it will be the answer. 80 81 Proof: 82 83 We can observe that our answer won't contain digits 4,6,8,9, because we can always transform digits 4,6,8,9 to more digits as in the conclusion, and it makes the number larger. 84 85 Then, how can we make sure that the result is the largest after this transformation? 86 87 We can prove the following lemma: 88 89 For any positive integer *x*, if it can be written as the form (2!)*c*2 * (3!)*c*3 * (5!)*c*5 * (7!)*c*7, there will be only one unique way. 90 91 Suppose that there exists two ways to write down x in this form, we can assume that the two ways are (2!)*a*2 * (3!)*a*3 * (5!)*a*5 * (7!)*a*7 and (2!)*b*2 * (3!)*b*3 * (5!)*b*5 * (7!)*b*7. 92 93 We find the largest *i* such that *a**i* ≠ *b**i*, Then we know there exists at least one prime number whose factor is different in the two ways. 94 95 But according to the Fundamental Theorem of Arithmetic, there is only one prime factorization of each integer. So we get a contradiction. 96 97 After getting the result, we don't need to worry about other numbers being larger than ours. 98 99 Time Complexity: *O*(*n*). 100 101 [author's code](//codeforces.com/contest/515/submission/9906310) 102 103 #### [515-D Drazil and Tiles](//codeforces.com/problemset/problem/515/D) 104 105 Again we give conclusion first: 106 107 First, view each cell as a vertex and connect two adjacent cells by an edge. 108 109 Then, build a queue and push all vertices of degree 1 in it. 110 111 Finally, in each iteration, we pop a vertex from the queue until the queue is empty. If the vertex is used, go to the next iteration. Otherwise, we put a tile on the vertex and its adjacent vertex, and erase these two vertices from the graph. If it yields a new vertex with degree 1, push it into the queue. 112 113 When the queue is empty, if there are still some cells not covered by any tiles, the answer will be "Not unique." 114 115 It's easy to understand that if we can put tiles on all cells by the above steps, the result is correct. But how about the remaining cases? 116 117 We will prove that when the degrees of all vertices are at least two, the solution is never unique. 118 119 Suppose there is at least one solution. 120 121 According to this solution, we can color those edges covered by tiles as black and color other edges as white. 122 123 We can always find a cycle without any adjacent edges having the same colors. (I'll leave it as an exercise. You should notice that the graph is a bipartite graph first.) 124 125 Then we can move the tiles from black edges to white edges. 126 127 So if there is at least one solution, there are in fact at least two solutions. 128 129 Time Complexity: *O*(*nm*) 130 131 [author's code](//codeforces.com/contest/515/submission/9906349) 132 133 #### [515-E Drazil and Park](//codeforces.com/problemset/problem/515/E) 134 135 There are many methods for this problem. I'll only explain the one that I used. 136 137 Let's split a circle at some point (for example between 1 and n) and draw a picture twice (i. e. 1 2 3 ... n 1 2 3 ... n), thus changing the problem from a circle to a line. 138 139 Remember that if two trees Drazil chooses are x and y, the energy he consumes is *d**x* + *d**x* + 1 + ... + *d**y* - 1 + 2 * (*h**x* + *h**y*). 140 141 Now rewrite this formula to (*d*1 + *d*2 + ... + *d**y* - 1 + 2 * *h**y*) + (2 * *h**x* - (*d*1 + *d*2 + ... + *d**x* - 1)) 142 143 Denote (*d*1 + *d*2 + ... + *d**k* - 1 + 2 * *h**k*) as *R**k* and denote (2 * *h**k* - (*d*1 + *d*2 + ... + *d**k* - 1)) as *L**k* 144 145 When a query about range [*a*, *b*] comes (The range [*a*, *b*] is where Drazil can choose, but not the range where the children are playing), it's equivalent to querying the maximum value of *L**u* + *R**v*, where *u* and *v* are in [*a*, *b*] and *u* < *v*. 146 147 Another important thing is that *L**u* + *R**v* always bigger than *L**v* + *R**u* when *u* < *v*. 148 149 So we can almost solve the problem just by finding the maximum value of *L**u* and *R**v* by RMQ separately and sum them up. 150 151 However, there is a special case: *u* = *v*, but we can handle it by making RMQ find the two maximum values. 152 153 Time Complexity: *O*(*n* + *m*). 154 155 [author's code](//codeforces.com/contest/515/submission/9906364) (implement with ) 156 157 More information about RMQ: [editorial](http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Sparse_Table_%28ST%29_algorithm) from Topcoder 158 159 #### [516-D Drazil and Morning Exercise](//codeforces.com/problemset/problem/516/D) 160 161 We can use dfs twice to get the farthest distance from each node to any leaves (detail omitted here), and denote the longest distance from the *i*-th node to any leaves as *d**i*. 162 163 Then we choose a node with minimum value of *d**i* as the root. We will find that for any node *x*, *d**x* isn't greater than *d**y* for any node *y* in the subtree of node *x*. 164 165 Next, we solve the problem when there's only one query of *L*. In all valid groups of nodes, where node *x* is the nearest to the root, obviously we can choose all nodes with *d**i* ≤ *d**x* + *L* into the group. Now we want to enumerate all nodes as the nearest node to the root. We denote the group of nodes generated from node *i* as *G**i*. 166 167 We can do it in  using dfs only once. (if the length of every edge is 1, we can do it in *O*(*n*)) 168 169 Imagine that *G**i* will almost be as same as the union of all *G**j* where node *j* is a child of node *i*, but some nodes which are too far from node *i* are kicked out. Each node will be kicked out from the groups we considered at most once in the whole process. Now we want to know when it happens. We solve it as follows: When we do dfs, we reserve a stack to record which nodes we have visited and still need to come back to. Yes, it's just like the implementation of recursive functions. Then we can just use binary search to find the node in the stack that when we go back to it, the current node will be kicked out (the closest node with |*d**x* - *d**i*| ≥ *L*). 170 171 So the time complexity of the above algorithm is  172 173 Now we provide another algorithm with O(*qn*α(*n*) + *nlog*(*n*)) by union find. (Thanks [Shik](/profile/Shik "Grandmaster Shik") for providing this method.) 174 175 First, sort all nodes by *d**i*. 176 177 Then for each query, consider each node one by one from larger *d**i*'s to smaller *d**i*'s. 178 179 At the beginning, set each node as a group of its own. We also need to record how many nodes each group contains. 180 181 When handling a node *x*, union all groups of itself and its children. At the same time, for each node *j* with *d**j* > *d**x* + *L*, we minus 1 from the record of how many nodes *j*'s group has. 182 183 By doing these, we can get the number of nodes *j* in *x*'s subtree with *d**j* < = *d**x* + *L*. That's exactly what we want to know in the last algorithm. 184 185 [author's code](//codeforces.com/contest/516/submission/9906402) (implement with O(*qn*α(*n*) + *nlog*(*n*)))) 186 187 #### [516-E Drazil and His Happy Friends](//codeforces.com/problemset/problem/516/E) 188 189 Simplifying this question, suppose that *n* and *m* are coprime. If *n* and *m* are not coprime and the gcd of *n* and *m* is *g*, then we can divide all people into *g* groups by the values of their id mod *g* and find the maximum answer between them. Obviously, If there is at least one group of friends which are all unhappy in the beginning, the answer is -1. 190 191 Now we determine the last one becoming happy, for boys and girls separately. 192 193 In fact, there's an easy way to explain this problem — finding the shortest path! View all friends as points, and add another point as the source. For all friends, we will view the distance from the source as the time becoming happy. And define two types of edges. 194 195 (1) 196 197 There is a fact: If a girl *x* become happy in time *t*, then the girl (*x* + *n*)%*m* will become happy in time *t* + *n*. So we can build a directed edge from point *x* to (*x* + *n*)%*m* with length *n*. Similar for boys. 198 199 (2) 200 201 If the *i*-th boy/girlfriend is happy originally, we can connect it to the source with an edge of length *i*. At the same time, we also connect the source to *i*%*n*-th boy(*i*%*m* for girl) with an edge of length *i*. You can imagine that the same gender of friends form a cycle. (eg. the (*i* * *m*)%*n*-th boy is connected to the ((*i* + 1) * *m*)%*n*)-th boy for *i* from 0 to *n* - 1) 202 203 With these two types of edges, we can find that if a friend is unhappy originally, he/she will become happy at the time value which is the length of the shortest path from the source. 204 205 The only question is that there are too many points and edges! 206 207 We can solve this problem by considering only some "important" points. 208 209 1. Points connected by the second type of edges. 210 2. Points connected to important points in 1., by the first type of edges. 211 212 And we can combine some consecutive edges of the first type to a new edge. The group of edges is the maximal edges that contain deleted points.(These deleted points always form a line). 213 214 Finally we find the maximum value of the shortest path from the source to these friends which is unhappy originally in the reduced graph. 215 216 Time complexity:  217 218 [author's code](//codeforces.com/contest/516/submission/9972091)