750.md (27304B)
1 Source: https://codeforces.com/blog/entry/49412 2 3 You can download my codes to all problems [here](http://www.filedropper.com/codes_1). 4 5 I will write a full editorial in the next few days. Now you can read hints and short solutions. 6 7 [750B - New Year and North Pole](/contest/750/problem/B "Good Bye 2016") 8 9 **hint** 10 11 Create a variable that will denote your current distance from the North Pole. What are allowed values of this variable? When can't we go West or East? 12 13 [750C - New Year and Rating](/contest/750/problem/C "Good Bye 2016") 14 15 **hint1** 16 17 Let *x* denote the initial rating (or his final rating, whatever is easier for you to think about). The information that Limak is in some division in the *i*-th contest gives us some inequality for *x*. Can you see it? 18 19 **hint2** 20 21 For every contest we know that the current rating is *x* increased by some prefix sum of c_i (changes of rating). If Limak is in the division 1, we have inequality x+prefSum >= 1900 so we have x >= 1900-prefSum. If Limak is in the division 2, we have inequality x_prefSum <= 1899 so it is x <= 1899-prefSum. From this set of inequalities, your task is to find the biggest *x* satisfying all of them. 22 23 [750D - New Year and Fireworks](/contest/750/problem/D "Good Bye 2016") 24 25 **hint1** 26 27 Since constrains are quite low, the firework won't visit cells far away from the initial cell. There aren't that many cells that can be visited. How can we use this fact? 28 29 **hint2** 30 31 If the initial cell has coordinates (0, 0), we are interested only in cells with coordinates up to MAX_N * MAX_T that is equal to 30·5 = 150. So there are *O*(1502) interesting cells. Use backtrack with memoization. Think about possible states. 32 33 **solution** 34 35 As a state you should keep: x-coordinate, y-coordinate, the current direction of this part of firework, and the recursion level (it says how much time this part will live). You can keep everything in C++ set, or use a big boolean array to make your solution faster. 36 37 [750E - New Year and Old Subsequence](/contest/750/problem/E "Good Bye 2016") 38 39 **hint1** 40 41 The intended solution is also able to process queries of form "change the i-th digit to x". This is a big hint. 42 43 **hint2** 44 45 Build a segment tree to answer queries in . What should be stored in such a tree? 46 47 **hint3** 48 49 Imagine going from left to right over a substring, maybe removing some digits. What is important in every moment is: what prefix of "2017" we already got as a subsequence. How to apply it to segment that should be merge in the segment tree? 50 51 **hint4** 52 53 In the segment tree store matrices of size 5 x 5, where *t*[*i*][*j*] means: the minimum number of digits to remove so that if there it was already possible to get prefix of "2017" of length *i*, then with this segment of digits it will be possible to get prefix of "2017" of length *j* (*i* ≤ *j*). 54 55 [750F - New Year and Finding Roots](/contest/750/problem/F "Good Bye 2016") 56 57 **hint1** 58 59 The intended solution is deterministic (it doesn't use any randomization). 60 61 **hint2** 62 63 Start from some vertex and try to find a path to any leaf. Knowing such a path, do we know in which direction we should go to find the root? 64 65 **hint3** 66 67 It's actually more useful to find a path between two leaves. 68 69 **hint4** 70 71 If you slightly exceed the number of queries allowed, try to get rid of some unnecessary queries at the end. 72 73 Also, the solution description of this problem is split into parts hidden in ,,spoiler'' tags. At any moment you can stop reading and try to finish the solution on your own. 74 75 [750G - New Year and Binary Tree Paths](/contest/750/problem/G "Good Bye 2016") 76 77 **hint1** 78 79 A path consists of LCA and two sides. 80 81 We can iterate over the depth of LCA and the two ends of a path. The depth can be up to *O*(*log*(*S*)) ≈ 50. 82 83 Actually, it's enough to iterate over lengths of sides (the distance from LCA to each end of a path). 84 85 **hint2** 86 87 It turns out that knowing the value of *s* and the lengths of sides is enough to compute the exact value of LCA. Try to find a formula yourself. 88 89 Now we can subtract something from *s* and assume that we count paths with LCA equal to 1, still with the chosen length of the left side and the right side. 90 91 **hint3** 92 93 The sum of vertices from vertex 1 to vertex *x* is roughly equal to 2·*x*. What is the exact formula? 94 95 **hint4** 96 97 It is 2·*x* - *popcount*(*x*). Try to use it to solve the problem of counting paths with LCA equal to 1 and some fixed lengths of sides. 98 99 **hint5** 100 101 Dynamic programming on bits. 102 103 [750H - New Year and Snowy Grid](/contest/750/problem/H "Good Bye 2016") 104 105 **hint1** 106 107 Duality 108 109 **hint2** 110 111 For every query we must say if the top-right side is almost connected with the bottom-left side. Here, "almost connected" means that they would be connected after adding at most one more vertex (cell). With preprocessing, you should find CC's (connected components) in the dual problem. Remember that now from one cell you can go in 8 directions. Also find pairs of CC's that are almost connected. 112 113 # [750A - New Year and Hurry](/contest/750/problem/A "Good Bye 2016") 114 115 Do you see what is produced by the following piece of code? 116 117 ``` 118 int total = 0; 119 for(int i = 1; i <= n; ++i) { 120 total += 5 * i; 121 printf("%d\n", total); 122 } 123 ``` 124 125 We iterate over problems (a variable `i` denotes the index of problem) and in a variable `total` we store the total time needed to solve them. The code above would print numbers 5, 15, 30, 50, ... — the *i*-th of these numbers is the number of minutes the hero would spend to solve easiest *i* problems. 126 127 Inside the loop you should also check if there is enough time to make it to the party, i.e. check if `total + k <= 240`. 128 129 simple C++ code:[24067296](/contest/750/submission/24067296 "Submission 24067296 by Errichto") 130 shorter but harder C++ code: [24067301](/contest/750/submission/24067301 "Submission 24067301 by Errichto") 131 python: [24067479](/contest/750/submission/24067479 "Submission 24067479 by Errichto") 132 133 # [750B - New Year and North Pole](/contest/750/problem/B "Good Bye 2016") 134 135 Our goal is to simulate Limak's journey and to check if he doesn't make any forbidden moves. To track his position, it's enough to store one variable denoting his current distance from the North Pole. To solve this problem, you should implement checking three conditions given in the statement. 136 137 Updating `dist_from_north` variable is an easy part. Moving *t**i* kilometers to the North increases the distance from the North Pole by *t**i*, while moving South decreases that distance by *t**i*. Moving to the West or East doesn't affect the distance from Poles, though you should still check if it doesn't happen when Limak is on one of two Poles — you must print "NO" in this case. 138 139 Let's proceed to checking the three conditions. First, Limak can't move further to the North if he is already on the North Pole *"at any moment of time (before any of the instructions or while performing one of them)"*. So you should print "NO" if `direction == "North"` and either `dist_from_north == 0` or `dist_from_north < t[i]`. The latter case happens e.g. if Limak is 150 kilometers from the North Pole and is supposed to move 170 kilometers to the North — after 150 kilometers he would reach the North Pole and couldn't move further to the North. In the intended solution below you will see an alternative implementation: after updating the value of `dist_from_north` we can check if `dist_from_north < 0` — it would mean that Limak tried to move North from the North Pole. Also, you should print "NO" if `dist_from_north == 0` (i.e. Limak is on the North Pole) and the direction is West or East. 140 141 You should deal with the South Pole case in a similar way. Limak is on the South Pole when `dist_from_north == M`. 142 143 Finally, you must check if Limak finished on the North Pole, i.e. `dist_from_north == 0`. 144 145 There were two common doubts about this problem: 1) *"Limak is allowed to move 40 000 kilometers to the South from the North Pole and will be again on the North Pole."* 2) *"Moving West/East may change the latitude (equivalently: the distance from Poles) and this problem is hard 3d geometry problem."* Both doubts make sense because they come from misinterpreting a problem as: Limak looks in the direction represented by the given string (e.g. to the North) and just goes straight in that direction (maybe after some time he will start moving to the South but he doesn't care about it). What organizers meant is that Limak should be directed in the given direction at any moment of time, i.e. he should continuously move in that direction. It's a sad thing that many participants struggled with that. I should have written the statement better and I'm sorry about it. 146 147 C++ code: [24067685](/contest/750/submission/24067685 "Submission 24067685 by Errichto") 148 python code: [24067669](/contest/750/submission/24067669 "Submission 24067669 by Errichto") 149 150 # [750C - New Year and Rating](/contest/750/problem/C "Good Bye 2016") 151 152 We don't know the initial or final rating but we can use the given rating changes to draw a plot of function representing Limak's rating. For each contest we also know in which division Limak was. 153 154  155 156 Red and blue points denote contests in div1 and div2. Note that we still don't know exact rating at any moment. 157 158 Let's say that a *border* is a horizontal line at height 1900. Points above the border and exactly on it should be red, while points below should be blue. Fixing the placement of the border will give us the answer (because then we will know height of all points). Let's find the highest blue point and the lowest red point — the border can lie anywhere between them, i.e. anywhere between these two horizontal lines: 159 160  161 162 Small detail: the border can lie exactly on the upper line (because rating 1900 belongs to div1) but it can't lie exactly on the lower line (because 1900 doesn't belong to div2). 163 164 The last step is to decide where exactly it's best to put the border. The answer will be 1900 + *d* where *d* is the difference between the height of the border and the height of the last point (representing the last contest), so we should place the border as low as possible: just over the lower of two horizontal lines we found. It means that the highest blue point should be at height 1899. 165 166 There is an alternative explanation. If Limak never had rating exactly 1899, we could increase his rating at the beginning by 1 (thus moving up the whole plot of the function by 1) and everything would still be fine, while the answer increased. 167 168 To implement this solution, you should find prefix sums of rating changes (what represents the height of points on drawings above, for a moment assuming that the first point has height 0) and compute two values: the smallest prefix sum ending in a div1 contest and the greatest prefix sum ending in a div2 contest. If the first value is less than or equal to the second value, you should print "Impossible" — it means that the highest blue point isn't lower that the lowest red point. If all contests were in div1, we should print "Infinity" because there is no upper limit for Limak's rating at any time (and there is no upper limit for the placement of the border). Otherwise we say that the highest blue point (a div2 contest with the greatest prefix sum) is a contest when Limak had rating 1899 and we easily compute the final rating. 169 170 *O*(*n*) code in C++: [24069564](/contest/750/submission/24069564 "Submission 24069564 by Errichto") 171  code in C++, with binary search: [24069586](/contest/750/submission/24069586 "Submission 24069586 by Errichto") 172 173 # [750D - New Year and Fireworks](/contest/750/problem/D "Good Bye 2016") 174 175 A trivial *O*(2*n*) solution is to simulate the whole process and mark visited cells. Thanks to a low constraint for *t**i*, a backtrack with memoization has much better complexity. Let's understand the reason. 176 177 Parts of the firework move by *t**i* in the *i*-th level of recursion so they can't reach cells further than  from the starting cell. That sum can't exceed *n*·*max*_*t* = 150. We can't visit cells with bigger coordinates so there are only *O*((*n*·*max*_*t*)2) cells we can visit. 178 179 As usually in backtracks with memoization, for every *state* we can do computations only once — let's think what that "state" is. We can't say that a state is defined by the current cell only, because maybe before we visited it going in a different direction and now we would reach new cells. It also isn't correct to say that we can skip further simulation if we've already been in this cell going in the same direction, because maybe it was the different level of recursion (so now next step will in in a different direction, what can allow us to visit new cells). It turns out that a state must be defined by four values: two coordinates, a direction and a level of recursion (there are 8 possible directions). One way to implement this approach is to create `set<vector<int>> visitedStates` where each vector contains four values that represent a state. 180 181 The complexity is  what is enough to get AC. It isn't hard to get rid of the logarithm factor what you can see in the last code below. 182 183 If implementing the simulation part is hard for you, see the first code below with too slow exponential solution. It shows an easy way to deal with 8 directions and changing the direction by 45 degrees — you can spend a moment to hardcode changes of *x* and *y* for each direction and clockwise or counter-clockwise order and then keep an integer variable and change its value by 1 modulo 8. You can add memoization to this slow code yourself and try to get AC. 184 185 too slow *O*(2*n*) approach (TLE): [24070543](/contest/750/submission/24070543 "Submission 24070543 by Errichto") 186 the same code with memoization (AC): [24070548](/contest/750/submission/24070548 "Submission 24070548 by Errichto") 187 faster memoization without logarithm (AC): [24070567](/contest/750/submission/24070567 "Submission 24070567 by Errichto") 188 189 # [750E - New Year and Old Subsequence](/contest/750/problem/E "Good Bye 2016") 190 191 It's often helpful to think about an algorithm to solve some easier problem. To check if a string has a subsequence "2017", we can find the find the first '2', then to the right from that place find the first '0', then first '1', then first '7'. If in some of these 4 steps we can't find the needed digit on the right, the string doesn't have "2017" as a subsequence. To additionally check if there is a subsequence "2016", after finding '1' (before finding '7') we should check if there is any '6' on the right. Let's refer to this algorithm as *Algo*. 192 193 It turns out that the problem can be solved with a segment tree (btw. the solution will also allow for queries changing some digits). The difficulty is to choose what we want to store in its nodes. Let's first use the Algo to answer simpler queries: *"for the given segment check if it's nice"*. 194 195 There is only one thing that matters for segments represented by nodes. For a segment we want to know for every prefix of "2017" (e.g. for "20"): assuming that the Algo already got this prefix as a subsequence, what is the prefix we have after the Algo processes this segment. Let's see an example. 196 197 TODO 198 199 # [750F - New Year and Finding Roots](/contest/750/problem/F "Good Bye 2016") 200 201 **part1** 202 203 The goal is to find a vertex with exactly two neighbours — this will be the root. 204 205 Also, let's notice that for a leaf we would get a list of exactly one neighbour. So we will know if we asked about the root or a leaf. 206 207 **part2** 208 209 The solution is deterministic. 210 211 Any randomized solution would likely fail — there are 500 test cases per test file, and usually there are 30-100 tests for a problem, so you must pass around 25,000 test cases. That's bad if you ask too many queries even with a small probability. 212 213 **part3** 214 215 You can ask about a vertex (say, *A*), then ask about one of its neighbours (say, *B*), then ask about one of neighbours of *B*, and so on, until you get a leaf. The sequence of visited vertices (*A*, *B*, ...) is a path in the tree. 216 217 How can this path look like in the whole tree? Do we know the distance from *A* to the root of the tree? 218 219  220 221 **part4** 222 223 To be able to say where exactly the path is in the tree, we should do one extra step. 224 225 From the initial vertex *A*, choose some other neighbour *B*2 and go from there again until you get a leaf. Now we have path between two leaves. The middle vertex on the path is the LCA and we know its distance from the leaves, so we also know its distance from the root. 226 227  228 229 In this case, vertex *B*1 turned out to be the middle of the path: 230 231  232 233 Where should you go now to find the root? 234 235 **part5** 236 237 Let's call that "middle vertex of the path" as *P*. We asked a query about *P* already, so we know its neighbours. Two neighbours are on the path, and the third one (the one not yet asked/visited) must be the parent of *P*. Let's go to that parent (so, ask a query about it) and then again continue until you find a leaf. 238 239  240 241 Where should we go now? 242 243 **part6** 244 245 We know that we went from *P* to its parent, then maybe again to a parent, but eventually we started going down. 246 247 If we know the numbers of steps it took us to get to a leaf (so, the length of the blue path), we can calculate the number of steps we went up. So we know what is the current LCA of asked/visited vertices and we can go up from there. 248 249 Alternatively, we can notice that we have a new longer path between two leaves (marked green below). Let *P*2 be the midddle of the path. *P*2 must be the vertex closest to the root (so, LCA of everything we asked/visited so far). 250 251  252 253 We repeat the process, until we get the root of the tree (so, a vertex with two neighbours). What is the number of queries we can ask up to that moment? 254 255 **part7** 256 257 In the worst case, we start from *P*0 being a leaf, and then the *i*-th new path will have *i* + 1 vertices. The following drawing shows the visited (asked) vertices in the worst case for *h* = 5. The not-yet-visited neighbour of *P*3 must be the root. 258 259  260 261 For height *h*, we can ask up to 1 + 2 + 3 + ... + (*h* - 1) queries, which is . The limit from the statement is 16, while for *h* = 7 we get up to 21 queries. We are close to the solution. Do you see how to get rid of a few queries? 262 263 **part8** 264 265 If the parent of a current *P**i* is within distance 2 from the root, we can just check all vertices within distance 2 (red vertices on the drawing) and we will find the root there. 266 267  268 269 The number of queries needed now is 1 + 2 + 3 + 4 + (1 + 6) = 17, where "1+6" represents the "PARENT" and the red vertices. We exceed the limit just by 1 now. How to get rid of one query? 270 271 **part9** 272 273 If you already asked about all red vertices but one, the last one must be the answer. We don't have to ask a query about it. 274 275 That's it, we use at most 16 queries. 276 277 # [750G - New Year and Binary Tree Paths](/contest/750/problem/G "Good Bye 2016") 278 279 Iterate over *L* and *R* — the length of sides of a path. A *"side"* is a part from LCA (the highest point of a path) to one of the ends of a path. 280 281 For fixed LCA and length of sides, let the *"minimal*" path denote a path with the minimum possible sum of values. In each of the sides, this path goes to the left child all the time: 282 283  284 285 If the LCA is *x*, the smallest possible sum of vertices on the left side of the minimal path has the sum of vertices: 286 287 *S**L* = 2·*x* + 4·*x* + ... + 2*L*·*x* = (2*L* + 1 - 2)·*x* 288 289 We can find a similar formula for the minimum possible sum of the right side *S**R*. For fixed *L*, *R*, *x*, the total sum of any path (also counting LCA itself) is at least: 290 291 *S**L* + *LCA* + *S**R* = (2*L* + 1 - 2)·*x* + *x* + ((2*R* + 1 - 2)·*x* + 2*R* - 1) 292 293 From this, with binary search or just a division, we can compute the largest *x* where this formula doesn't exceed the given *s*. This is the only possible value of LCA. Larger *x* would result with the sum exceeding *s*. Smaller *x* would result in too small sum, even if a path goes to the right child all the time (so, the sum is maximized). Proof: every vertex is strictly smaller than the corresponding vertex in the "minimal" path for the computed largest possible *x*: 294 295  296 297 So, from *L* and *R* we can get the value of LCA. 298 299 Let's assume that the computed value of LCA is 1. For any other value we know that the value of vertex on depth *k* would be greater by (*x* - 1)·2*k* compared to LCA equal to 1, and we know depths of all vertices on a path, so we can subtract the sum of those differences from *s*, and assume the LCA is 1. 300 301 The sum of vertices from 1 to *a* is 2·*a* - *popcount*(*a*). Proof: if the binary representation of *a* has 1 on the *i*-th position from the right, there will be 1 on the (*i* - 1)-th position in the index of the parent of *a* and so on. So this bit adds 2*i* + 2*i* - 1 + ... + 1 = 2*i* + 1 - 1 = 2·2*i* - 1, so everything is doubled, and we get "-1" the number of times equal to the number of 1's in the binary representation of *a*. Thus, the formula is 2·*a* - *popcount*(*a*). 302 303 If endpoints are *a* and *b*, the sum of vertices will be 2·*a* - *popcount*(*a*) + 2·*b* - *popcount*(*b*) - 1 (we subtract the LCA that was counted twice). Since popcounts are small, we can iterate over each of them and we know the left value of equation: 304 305 *s*' + *popcount*(*a*) + *popcount*(*b*) + 1 = 2·(*a* + *b*) 306 307 Here, *s*' is equal to the initial *s* minus whatever we subtracted when changing LCA from the binary-searched *x* to 1. 308 309 The remaining problem is: Given binary lengths *L* and *R* of numbers *a* and *b*, their popcounts, and the sum *a* + *b*, find the number of such pairs (*a*, *b*). This can be solved in standard dynamic programming on digits. 310 311 To slightly improve the complexity, we can iterate over the sum *popcount*(*a*) + *popcount*(*b*) instead of the two popcounts separately. The required complexity is  or better. 312 313 # [750H - New Year and Snowy Grid](/contest/750/problem/H "Good Bye 2016") 314 315 Let's solve an easier problem first. For every query, we just want to say if Limak can get from one corner to the other. He can't do that if and only if blocked cells connect the top-right side with the bottom-left side — this is called a dual problem. 316 317  318 319 On the drawing above, the top-right side and bottom-left side are marked with blue, and blocked cells are black. There is a path of blocked cells between the two sides what means that Limak can't get from top-left to bottom-right corner. The duality in graphs changes the definition of adjacency from "sharing a side" to "touching by a corner or side" — the black cells on the drawing aren't side-adjacent but they still block Limak from passing through. Similarly, if Limak was allowed to move to any of 8 corner/side-adjacent cells, black cells would have to touch by sides to block Limak from passing through. 320 321 The idea of a solution is to find CC's (connected components) of blocked cells before reading queries, and then for every query see what CC's are connected with each other by temporarily blocked cells. To make our life easier, let's treat the blue sides as blocked cells too by expanding the grid by 1 in every direction. Then for every query, we want to check if new blocked cells connect the bottom-left CC and top-right CC. 322 323  324 325 Before reading queries, we can find CC's of blocked cells (remember that a cell has 8 adjacent cells now!). Let's name those initial CC's as *regions*. When a temporarily blocked cell appears, we iterate through the adjacent cells and if some of them belong to initial regions, we apply find&union to mark some regions as connected to each other (and connected to this new cell that is a temporary region of size 1). This can be done in  where *k* is the number of temporarily blocked cells. This solves the easier version of a problem, where we just check if Limak can get from one corner to the other — if the two special regions are connected at the end then the answer is "NO", and it's "YES" otherwise. 326 327 What about the full problem? Limak wants to move to the opposite corner and back, not using the same cell twice. If you treat a grid as a graph, this means checking if there is a cycle passing through the two corners (a cycle without repeated vertices). It's reasonable to then think about bridges and articulation points. An articulation point here would be such a cell that making it blocked would disconnect the two corners from each other — it's a cell that Limak must go through on both parts of his journey. Our dual problem becomes: check if the two sides are *almost connected* i.e. it's enough to add one more blocked cell to make the connection (that cell must be an articulation point). The previously described solution needs some modification. 328 329 We did F&U on regions adjacent to temporarily blocked cells. If some region was connected with some other region in the current query, let's call it an *interesting* region — there are *O*(*k*) of them. If we preprocess the set of pairs of regions that are initially *almost connected* (it's enough to add one more blocked cell to make them connected), we can then for a query iterate over pairs: a region connected to the bottom-right side and a region connected to the other side, and check if this pair is in the set of almost-connected regions. There are *O*(*k*2) pairs and if any of them is almost-connected, we have an almost-connection between the two sides and we print "NO", because Limak can't avoid revisiting cells. 330 331 My code: [50164800](/contest/750/submission/50164800 "Submission 50164800 by Errichto").