115.md (14752B)
1 Source: https://codeforces.com/blog/entry/2584 2 3 **Time Capsule Remarks (planted before the contest)** 4 5 Due to popular demand, today's problem statements are made to be as short as possible without too many (but existing!) embellishment. All of them are thinking-based problems (i.e., implementation is the easier of the two) - so I'm generally happy with the problems :). I hope nobody found them to be too easy :S 6 7 As you may have noticed, we decided not to give devastatingly weak pretests. I guess it's just really evil to give weak pretests for my first match. 8 9 And so, the editorial begins... 10 11 Remarks 12 13 I'm sorry - but I don't have access to my usual graphic editing tool and so, the graphics are fairly limited :) (Example: Lawnmower's pictures must be the ugliest lawnmower I have ever seen! (Is it even a lawnmower?) Not to mention I don't look like the actor at all...) 14 15 **[D2-A: Tram](//codeforces.com/contest/116/problem/A)** 16 17 If we know the number of people inside the tram at all possible time, then the answer is the maximum of such. We observe that the number of people inside the tram changes only at tram stops. The conclusion is that the answer will be the maximum of the number of people inside the tram directly before arriving at a particular stop and directly after leaving a particular stop (the more observant readers can notice that using only one of these is sufficient). 18 19 It's sufficiently easy to calculate the number of people inside the tram directly before and after leaving a tram stop. 20 21 **[D2-B: N Little Pigs](//codeforces.com/contest/116/problem/B)** 22 23 No... not maximum matching ;) 24 25 So, an equivalent less-evil rewording of the problem would be: "Return the number of wolves that are adjacent to at least one pig". 26 27 To see this, since each pig has at most one wolf adjacent to it (the constraints impose that) we don't need to worry at a single pig may get eaten by two different wolves. Hence, each wolf can eat any of the pig adjacent to it. 28 29 Remarks 30 31 It's more interesting to reverse this problem isn't it: 32 33 Each pig will be adjacent to at most one wolf 34 35 becomes 36 37 Each wolf will be adjacent to at most one pig 38 39 Can you solve this one? (Of course, not using network flow mind you ;) - that's overkill) 40 41 **[D2-C / D1-A Party](//codeforces.com/contest/115/problem/A)** 42 43 We let an employee without a manager called as root. There's an edge from a manager to an employee that he/she manages. 44 45 First notice that the graph is a collection of directed trees. Hence, we can assign a depth label to each node - denoting the number of nodes on the simple path from the root to it. The answer is then the maximum depth a node has. 46 47 Why? 48 49 First, the answer is bounded below by this number because any pair of employees in this path cannot be in the same group. Second, since the graph is a tree, each node in the graph has a unique depth label assigned to it. Simply put all nodes with the same depth in the same group. It's fairly easy to see that no one will be the superior of another within a group, for otherwise their depths will not be equal. 50 51 Remark 52 53 You might notice that there exist an O(N) implementation of the above algorithm, yet the constraint is 2000. Well, this problem was swapped with the D1-B because the previous D1-A was thought to be harder than expected. And so, in the process, we also decrease the constraint for N from 200,000 to 2,000. I hope you like it :) 54 55 **[D2-D / D1-B: Lawnmower](//codeforces.com/contest/115/problem/B)** 56 57 First, let's observe a particular strategy that turns out to be optimal at the end of our discussion. 58 59 Suppose we're on a row, facing right. This strategy say that we need to move to the right as long as there is a weed to the right of us either on this row or on the row directly below us. 60 61 The idea is that we need to mow that weed, hence, we need to move there. If it's in the same row as us, it's fairly obvious we have to mow that before going down. If it's at the row directly below us, since we can't move to the right in the row below us (since we'll be facing left there) we need to move there before going down. 62 63 The strategy then says that if we no longer need to move right, we go down, and face left. Repeat this until all weeds are mowed (replacing left and right in the discussion above) - and we have our strategy. 64 65 This strategy is optimal. Proof is using induction - but it's not particularly interesting, so the idea is given instead. 66 67 Suppose we're on a row, facing right, again. If there exist a weed to the right in this row or below us, then any solution will necessarily move right as far as our strategy goes (for the reason we discussed above). Some solution however choose to go further right despite having no weed in this row or the row directly below us. This solution is not optimal if we need to go left directly after going down, for we can just simply go down instead of going right-down-left. On the other case, if we don't need to go left directly after going down, then it means that we go down twice-in-a-row! Hence, instead of moving right in this row, we go down twice, then move right there. And then the induction can continue and the proof can follow. 68 69 Remarks 70 71 I guess the actor should be Toastman instead :). 72 73 Anyway, so sorry to disappoint you, but we decided to add some pretty strong pretest to this problem, despite the fact that many solutions will probably forget to take care of two consecutive empty rows. But still, the pretest we gave only consist of one column, so feel free to hack the stragglers :) (not that this suggestion matters after the contest but still...) 74 75 **[D2-E / D1-C Plumber](//codeforces.com/contest/115/problem/C)** 76 77 To solve this problem, let's imagine that the left and top sides of the grid also determines whether the pipe adjacent to that side has an end connecting it to the side or not. There are 2^(N+M) ways to pick them. We claim that if we fix them (i.e., pick one of the possible 2^(N+M) ways, then the entire grid's pipes are fixed). 78 79 To see this, notice that each pipe segment will have either one vertical end (it either have end on the top or end on the bottom) and one horizontal end (left or right). We can pick any 4 combinations of them. Suppose we pick a row, and determine whether the leftmost pipe should have an end to the left of it, or not. Suppose it doesn't have an opening to the left. It means that the leftmost pipe should have an opening to the right, the next pipe should have an opening to the left, the next pipe to the right, and so on. Continuing this way, we have fixed the horizontal ends for an entire row - and only that. Hence, if we pick one of the possible 2^(N+M) ways to pick the ends, then the horizontal ends of each row and vertical ends of each column is fixed. Since there is exactly one pipe segment that has a particular configuration of ends, there is exactly one possible completed grid for each of the 2^(N+M) ways to pick the ends. 80 81 Hence, the solution works by first checking if a solution exists. Any pre-assigned pipe simply sets whether or not its corresponding row and column has an end at the left and top side. We need to check that no two pipes sets this value contradictorily. If any of them are contradictory, then we return the answer as 0. Otherwise, we return 2^(number of rows without preassigned cell + number of columns without preassigned cell). 82 83 **[D1-D Unambiguous Arithmetic Expression](//codeforces.com/contest/115/problem/D)** 84 85 This problem is solved using Dynamic Programming. The somewhat straightforward dynamic programming is to represent the state as {start_pos, end_pos}, which represents the number of unambiguous arithmetic expression on the substring of the input starting at start_pos and ending at end_pos. This however has a complexity of O(N^3) and is not suitable for our problem. 86 87 The solution uses the state {pos, braces}. This state is somewhat tricky to explain. This means that we have read the first pos characters in the input. We're expected to read a single unambiguous arithmetic expression, close it with some number of brackets that we don't care (to be explained below), and then, if braces is zero, that's it. Otherwise, we're then expected to read a binary operator (either + - * or /), then open a bracket, then move the state to {pos + some_value, braces-1}. That is, braces keeps track on the number of second operands of binary expression that we need to make. 88 89 For an example how this works, let's try to solve a particular test case: 90 91 "++0*+1" 92 93 Let's denote with quotes the part of the input that we haven't processed. We're going to create the unambiguous arithmetic expression by scanning it left to right and making some choices. 94 95 There are three choices: 96 97 1) Create a unary expression. In the example above, 98 99 "++0*+1" -> +("+0*+1" 100 101 We don't really care about where the closing bracket is yet. 102 103 2) Create a binary expression. In the example above, 104 105 +("+0*+1" -> +(("+0*+1" 106 107 How does this tells that we will need to create a binary expression? The second open bracket does not have any operator preceeding it. The only thing that can makes this a proper prefix of an unambiguous arithmetic expression is that if this bracket belongs to the first operand of a binary expression. 108 109 For our example, we suppose we read another unary expression 110 111 +(("+0*+1" -> +((+("0*+1" 112 113 3a) Read an integer. In our example above, 114 115 +((+("0*+1" -> +((+(0))*("+1" 116 117 There are two questions. a) how do we know the number of closing brackets we have to make? This is actually easy - for every open bracket we have, if it's for a unary expression, we simply close and repeat. Otherwise it's a closing bracket for possibly the first operand to a binary expression, so we close it, and we read a binary operator (* in the example above), and try to read the second operand of the binary expression. 118 119 Finally: 120 121 +((+(0))*("+1" -> +((+(0))*(+("1" 122 123 3b) We try to read an integer again and we have no open brackets that belongs to the first operand of a binary expression, and we have ourself a possible answer. 124 125 +((+(0))*(+("1" -> +((+(0))*(+(1))) 126 127 So, in the state {pos, braces}, pos determines the starting location of the remaining unprocessed input. braces indicates the number of open brackets that belongs to a binary expression. So, in the examples above: 128 129 1) 130 131 "++0*+1" -> +("+0*+1" is represented by 132 133 {0, 0} -> {1, 0} 134 135 More specifically, for unary expressions, {pos, braces} -> {pos+1, braces} 136 137 2) 138 139 +("+0*+1" -> +(("+0*+1" is represented by 140 141 {1, 0} -> {1, 1} 142 143 More specifically, for binary expressions, {pos, braces} -> {pos, braces+1} 144 145 3a) 146 147 +((+("0*+1" -> +((+(0))*("+1" 148 149 {2, 1} -> {4, 0} 150 151 More specifically, {pos, braces} -> {pos + length_of_integer + 1, braces-1} 152 153 3b) 154 155 +((+(0))*(+("1" -> +((+(0))*(+(1))) 156 157 {5, 0} -> Done 158 159 More specifically, {pos, braces} -> done if braces is zero and the remaining input forms a single integer. 160 161 Remarks 162 163 My favorite problem of this match (because it's hard-to-think and easy-to-code) ;). This turns out to be the hardest problem of the match. 164 165 During the match, three coders ([shik](//codeforces.com/profile/shik "Lieutenant colonel shik"), [ivan.popelyshev](//codeforces.com/profile/ivan.popelyshev "Colonel ivan.popelyshev"), and [watashi](//codeforces.com/profile/watashi "General watashi")) submitted solutions which I think works in N^2. [Petr](//codeforces.com/profile/Petr "General Petr") submitted a solution that (I think) uses Catalan number, while [Egor](//codeforces.com/profile/Egor "Colonel Egor") submitted a solution which uses polynomial to quickly count each of the dp values (see his [comment](//codeforces.com/blog/entry/2584?locale=ru#comment-55420) in the Editorial). [tourist](//codeforces.com/profile/tourist "General tourist") submitted a solution which uses a highly-optimized inner loop with no branching and expensive operations (only a single multiplication) - he cleverly avoid branching in his code. 166 167 **[D1-E Races](//codeforces.com/contest/115/problem/E)** 168 169 We process the roads one by one. Associated with each road is the races whose UBi is that road (i.e., races that 'ends' at that road). We will discuss the Dynamic Programming solution first, then improve it with a data structure into the optimal solution. 170 171 Let's say we're going to process a road. Our state is this : DP[X] is the maximum possible profit such that the last X roads before this road are fixed and the X+1-th road before this road is NOT fixed. We are going to compute the value of DP for the next iteration, let's call this FUTURE. FUTURE[0] is obtained if we don't fix this road, FUTURE[0] = maximum amongst the value of DP. Otherwise, if we decide to fix this road, then for each of DP[X], FUTURE[X+1] >?= DP[X] - cost to fix the road + all races' profit that ends at this road and whose starting point is not before X roads from current road (i.e., all the races that is contained and ends at this road). This should work in N^2 + N * M. It can be improved to N^2 + M 172 173 The data structure approach is slightly different. We will use a segment tree that allows finding a maximum value in a subset and modifying the values of a range, all of which should work in either O(1) or O(log N). The segment tree will consist of N+1 leaves. However, not all the leaves are active at the start of the algorithm. At the start, only one leaf is active and it corresponds to the initial value of DP[0]. Next, we can compute the maximum value amongst all active leaves in O(log N). Then, we create a new active leaf that corresponds to FUTURE[0]. This will be located in the same tree however, the values represented by the leaves will be shifted one to the right - this is done implicitly (for example, we use the last node as DP[0] for the first iteration, but treat it as DP[1] for the next, and so on). These shifted values will correspond to FUTURE[X], since we notice that FUTURE[X] = DP[X-1] - cost to fix the road + races that this series contains and ends at this current road (i.e., it's value directly depends on the leaf BEFORE it was shifted). Next, we decrement the value of all these new leaves (except FUTURE[0]) by the cost to fix the road (in O(log N)). Finally, for each race that ends at this road, we increment the value of the leaves that contains this race. This will be continuous, i.e., FUTURE[X] for X in [race_len, INFINITY]. This can also be done in O(log N). Since a race ends at at most one road, the total complexity this will contribute is M log N. 174 175 The answer will then simply the maximum value amongst all members of the tree. 176 177 Remarks 178 179 This is one of the problems I submitted to this year's IOI but didn't got accepted - I sort of agree that this doesn't suit IOI very well. IOI likes a non-numeric output :) #goparrots!