269.md (16447B)
1 Source: https://codeforces.com/blog/entry/6596 2 3 ### [Div II A — Fancy Fence](/contest/270/problem/A "270A - Fancy Fence") 4 5 #### Problem 6 7 The problem is to tell whether there exists a regular polygon with angle equal to *a*. 8 9 #### Solution 10 11 Consider all supplementary angles of the regular *n*-polygon with angle *a*, which are equal to . Their sum is equal to , because the polygon is convex. Then the following equality holds: *n*·(180 - *a*) = 360, which means that there is an answer if and only if . 12 13  14 15 Time: *O*(*t*). 16 17 Memory: *O*(1). 18 19 Implementation: [C++](http://ideone.com/xnq9Iu), [Java](http://ideone.com/D2hHEL) 20 21 #### Comments 22 23 The problem can be also solved by rotating vector (1, 0) by angle  until it returns in this position (but at most 360 times), and checking that only one full turn has been made (implementation example: C++). 24 25 It is also a rare problem on Codeforces that contains just 1 sample test, 1 pretest and 1 full test. 26 27 ### [Div II B — Multithreading](/contest/270/problem/B "270B - Multithreading") 28 29 #### Problem 30 31 In this problem we are asked to find the number of *n*-permutation elements that definitely have been moved after performing any sequence of move-to-front element operations. Equally, we should find the maximum possible number of elements that could have not been moved. 32 33 #### Solution 34 35 If some *a**i* is greater than *a**i* + 1, it is clear that *a**i* definitely contains a new message because the order of these two elements has changed. Let the last such element be *a**k*. Then all of the elements *a**k* + 1, *a**k* + 2, ..., *a**n* can contain no new messages, since their order has not changed. The answer to the problem is *n* - *k*. If there is no such *a**k* the order hasn’t changed at all and there may be no new messages. 36 37 Time: *O*(*n*). 38 39 Memory: *O*(*n*) / *O*(1). 40 41 Implementation: [C++](http://ideone.com/PJFbnJ), [Java](http://ideone.com/0DR19E) 42 43 #### Comments 44 45 The problem was born while staring at the Codeforces main page and trying to think up an easy Div II problem. =) 46 47 ### [Div II C / Div I A — Magical Boxes](/contest/269/problem/A "269A - Magical Boxes") 48 49 #### Problem 50 51 We are given *a**i* squares with side length 2*k**i*. It is allowed to insert squares only inside larger ones, and no two squares should overlap. We must determine the minimum *p* so we can place all the given squares inside a square with side length 2*p*. 52 53 #### Solution 54 55 Suppose we can put all the squares inside a square with side length 2*p*. Then we can insert each *k**i* type squares independently along the grid as shown in the picture. No two squares will overlap, since 2*x* divides 2*y*, if *x* < *y*. That means that we can find the smallest square that can hold all the given squares with side length 2*k**i* for each *k**i* separately. The answer will be the side length of the largest such square. 56 57  58 59 To be able to put *a**i* squares with side length 2*k**i* inside a square with side length 2*s*, the following should hold: 60 61 (2*s*)2 ≥ (2*k**i*)2·*a**i* 4*s* ≥ 4*k**i*·*a**i* 4*s* - *k**i* ≥ *a**i* 62 63 We can then find the minimum *s*: 64 65   66 67 In a special case, if we obtain *s* = *k**i*, *s* should be increased by 1. 68 69 Time: . 70 71 Memory: *O*(1). 72 73 Implementation: [C++](http://ideone.com/NORd3X), [Java](http://ideone.com/Zp7Nno) 74 75 #### Comments 76 77 The problem can be also solved using binary search on *p*. However, we can see that each square with side length 2*k* + 15 holds any number of squares with side length less than 2*k*, since . So it is enough to find the first square that fits from range 2*max*{*k*} + 1 to 2*max*{*k*} + 15. 78 79 ### [Div II D / Div I B — Greenhouse Effect](/contest/269/problem/B "269B - Greenhouse Effect") 80 81 #### Problem 82 83 There are *n* points on the line, each of type from 1 to *m*. We can freely divide the line into *m* - 1 intervals and replace some points so each point with type *i* is inside the *i*-th interval numbered 1 to *m* from left to right. We must find the minimum number of points to replace. 84 85 #### Solution 86 87 First, observe that the coordinates don’t matter: only the order of the points is important. Let there be some number of points we can replace to achieve the good arrangement. Then all the other points remain in their positions, so their values must be in increasing order from left to right. Then we must find the maximum number of points that can remain in their positions, which is the longest non-decreasing subsequence of types in the input. If it is of length *l*, the answer is *n* - *l*. 88 89 In this problem it was enough to implement a quadratic solution. We count *dp*[*i*][*j*] — the length of the longest non-decreasing subsequence on prefix [1;*i*], with element of type *j* being the last in subsequence. The transition is as follows: 90 91  92 93 For easy implementation, we can maintain only array *dp*[*j*], and skip the second case. 94 95 Time: *O*(*n*2) / . 96 97 Memory: *O*(*n*2) / *O*(*n*). 98 99 Implementation: [C++](http://ideone.com/8uzrrr) 100 101 #### Comments 102 103 We had to solve this problem during the work on our project, the origin lies in arranging some rectangular table borders. Our original project dp implementation actually runs in *O*(*nm*). 104 105 ### [Div II E / Div I C — Flawed Flow](/contest/269/problem/C "269C - Flawed Flow") 106 107 #### Problem 108 109 In this problem we are given an undirected graph and its flow, and we must reconstruct the edge directions of this flow. 110 111 #### Solution 112 113 The key element to solving the task is the following observation: if we know all the incoming edges of a vertex, all the remaining edges must be outgoing. The source has no incoming edges, so we already know that all its edges are outgoing. For all other vertices except the sink the amount of incoming and outcoming flow is the same, and is equal to half of the sum of the flow along its incident edges. The algorithm then is to repeatedly direct all the flow from the vertices for which all the incoming edges are known. This can be done with a single BFS: 114 115 ``` 116 for all v from 2 to n-1 117 f[v] := sum(flow(v,u))/2; 118 put source in queue 119 while queue is not empty 120 v := pop(queue) 121 for all edges (v, u) 122 if (v, u) is not directed yet 123 direct v -> u 124 f[u] = f[u] - flow(v,u) 125 if u not sink and f[u] = 0 126 push(queue, u) 127 ``` 128 129 As the flow contains no cycles, we can sort the vertices topologically. Then we can be sure that, until all edge directions are known, we can put at least the first vertex with unknown edges in the queue, as all of its incoming edges will be from vertices with lower indices, but we took the first vertex with unknown edges. 130 131 Time: *O*(*n* + *m*) 132 133 Memory: *O*(*n* + *m*) 134 135 Implementation: [C++](http://ideone.com/ePdlwd), [Java](http://ideone.com/qE3vYO) 136 137 #### Comments 138 139 The obvious "easy" solution is to run some maxflow algorithm and get the answer. However, such implementations failed on anti-maxflow pretest #6. 140 141 ### [Div I D — Maximum Waterfall](/contest/269/problem/D "269D - Maximum Waterfall") 142 143 #### Problem 144 145 We are given *n* horizontal segments on a plane, and 2 extra topmost and bottommost segments. These two segments are the source and the sink of the flow. A flow can pass from one segment to a lower segment, if their horizontal projections overlap and there is no other segment between them so their projections overlap. The value of the flow on such segment edge is equal to the length of the horizontal projection overlap. We must find the maximum possible value of the flow along a single segment path. 146 147 #### Solution 148 149 We will use a sweepline algorithm to solve this task. This horizontal sweepline runs from bottom to top, and holds the parts of the segments that are visible from the line this sweepline is currently at. Each part also holds the reference to its original segment. The sweepline itself is implemented with a binary search tree. 150 151 The events of the sweep are the segments. When a new segment is found, we want to find all the lower segments that we can direct the flow onto from this segment. These can be only the original segments of the parts currently in the sweepline whose projections overlap with this segment. Then we iterate over all such parts *p* (finding the first such part is an  operation). How do we know that we can direct the flow onto *p*? Observe that if there is some segment that prevents this, there should be also a part *q* in the sweepline that also can be seen from the current segment. And since the projections of all three segments overlap, this part can only be directly to the left or to the right of *p* in the binary search tree. So we just check whether the original segments of the two parts next to *p* prevent the flow from the current segment to the original segment of *p*. 152 153 Afterwards, we remove all such parts from the sweepline, and insert a new part corresponding to the new segment. If the new segment only partially covered an existing part, we reinsert the remaining portion of that part. There are at most two such portions — one on each side of the segment. Thus each segment inserts at most 3 new parts and the size of the sweepline is *O*(*n*). Each part is handled just once before removal, so the total time of such operations is . 154 155 Once we know we can direct the flow through  we can immediately update the maximum downwards flow of *a*: 156 157 *f**a* = *max*(*f**a*, *min*(*f**b*, *min*(*r**a*, *r**b*) - *max*(*l**a*, *l**b*))) 158 159 When we reach the top, *f**top* will be the answer. 160 161  162 163 Time:  164 165 Memory: *O*(*n*) 166 167 Implementation: [C++](http://ideone.com/bka28U), [Java](http://ideone.com/frmAwe) 168 169 #### Comments 170 171 Another problem from our project. You can also first build a graph from the segments using the same sweepline and then find the path with the maximum flow in that graph. In the original problem you have to find this graph and there are no top and bottom segments. 172 173 ### [Div I E — String Theory](/contest/269/problem/E "269E - String Theory") 174 175 #### Problem 176 177 In this problem we have an *n* × *m* rectange. Each unit midpoint is connected with a segment to some other midpoint not on the same side of the rectangle. We can change the order of the columns and rows, but the segments must remain attached to their midpoints. We should find such a rearrangement that no two segments intersect, or tell that there is no solution. 178 179 #### Solution 180 181 There are overall 6 types of segments that connect the sides: 182 183 1. left-top; 184 2. top-right; 185 3. right-bottom; 186 4. bottom-left; 187 5. left-right; 188 6. top-bottom; 189 190 If there are both left-right and top-bottom segments, there is no solution. Otherwise there remain only 5 types of segments. Without loss of generality suppose there are no left-right segments. Let’s take a closer look at what should the end picture of the rectangle be: 191 192  193 194 All left-top segments should be at the left top corner connecting positions (L,i) and (T,i), otherwise they surely would cross some other segment. Similarly must be positioned top-right, right-bottom, bottom-left segments. Finally, all top-bottom segments should be parallel. We also observe that the number of left-top segments must be equal to the number of right-bottom segments and the number of top-right segments should be equal to the number of bottom-right segments. Thus the important observation: the picture of the end arrangement is unique and can be determined from the input simply by counting the number of segments of each type. 195 196 Next we define a cycle to be the sequence of segments, where the second midpoint of some segment in the cycle is equal to the first midpoint in the next segment in the cycle. In the given example there are two such cycles (but the direction of each cycle actually matters): 197 198  199 200 Then we observe that the set of the cycles does not change with any permutation by the definition of the cycle. We can make a sketch of the solution: we should find the cycle sets in the given arrangement and in the end arrangement, and compare them for equality. 201 202 At this point we actually find all the cycles in both arrangements. There are only two types of cycles: 203 204 1. (left-top)  (top-right)  (right-bottom)  (bottom-left); 205 2. other cycles. 206 207 We can easily check whether the sets of first type cycles match, since the length of such cycles is 4. If they match, we rearrange the columns and rows involved to match the end arrangement. 208 209 How to compare the remaining cycles. Consider a following example: 210 211  212 213 Let the difference in the number of left-top and left-bottom segments be *i*, and this number plus the number of top-bottom segments *s*. If we enumerate the midpoints as in the figure, we can see that each top midpoint *k* is connected to the bottom midpoint  (top-right segments continue as corresponding left-bottom segments). Thus we can describe it as a permutation 214 215  216 217 Our cycles correspond to the cycles in this permutation, with top-right segment continuation to left-bottom segment corresponding to the case where permutation cycle element decreases. It is known that the number of such permutations is  and their length is . So all these cycles have the same length. Denote the remaining segment types as some letters (in picture A, B, C). Then not only the length, but the strings describing the cycles are also the same, but can be shifted cyclically (here the direction of the cycles also is important). Besides, we know this string from the correct arrangement cycle. Thus we need to compare all the remaining given arrangement cycle strings to this string, considering cyclic shifts as invariant transformations. For each string this can be done in linear time, for example, using the Knuth-Morris-Pratt algorithm. When we find a cyclical shift for each cycle, we can position its relevant columns and rows according to the end arrangement. 218 219 Time: *O*(*n* + *m*). 220 221 Memory: *O*(*n* + *m*). 222 223 Implementation: [C++](http://ideone.com/bm0GQP), [Java](http://ideone.com/QYJR6c) 224 225 #### Comments 226 227 This is a total killer task for coding. It took both of us around 5 hours to code the implementation. Congratulations again to [kelvin](/profile/kelvin "Grandmaster kelvin"), at the time of writing still the only one to solve the problem (and of course to anyone who will get this difficult problem accepted =) ).