379.md (3652B)
1 Source: https://codeforces.com/blog/entry/10171 2 3 Excuse me for my english, but I tried very hard to.=) 4 5 #### A: [379A - New Year Candles](/contest/379/problem/A "Good Bye 2013") 6 7 Let *cur**a* amount of new candles, *cur**b* — amount of burnt out. Initially *cur**a* = *a*, *cur**b* = 0, after burning all *cur**a* new candles, amount of hours incremented by *cur**a* and *cur**b* + = *cur**a*, lets make all burnt out candles into new *cur**a* = *cur**b* / *b* , repeat this algorithm until we can make at least one new candle. #### B: [379B - New Year Present](/contest/379/problem/B "Good Bye 2013") If wallet contains more then one coin, then between orders to "put a coin" we can orders to move to adjacent wallet then back. Since for each orders to "put a coin" we spend at most 2 other orders, number of total orders for maximum test equals 300 * 300 * 3 = 270000 it less then 106. 8 9 #### C: [379C - New Year Ratings Change](/contest/379/problem/C "Good Bye 2013") 10 11 We can to sort ratings in nondecrease order, then iterate by them we can keep minimal rating not used before. If *a**i* > *cur*, *i*'s user recieve *a**i* of rating and *cur* = *a**i* + 1, else *a**i* ≤ *cur* then *i*'s user recieve *cur* of rating and *cur* increased by one. 12 13 #### D: [379D - New Year Letter](/contest/379/problem/D "Good Bye 2013") 14 15 We can't fairly calculate *s**k* because of length of this string which can be very large. But note that whole string not need, we just need number of *AC* substrings, first and last letter. That help us to easy calculate number *AC* substrings for any *s**k* for some *s*1, *s*2. Let's iterate through *s*1, *s*2 using alphabet of *A*, *C*, and any other letter. We need just first and last letter and number of *AC*. Using some *s*1, *s*2 we can calculate *s**k*. 16 17 #### E: [379E - New Year Tree Decorations](/contest/379/problem/E "Good Bye 2013") 18 19 Let's keep union of first *i* pieces, *S*(*i*) denote the area of union for the first *i* pieces. Then to know visible part of *i*'s piece we need to calculate *S*(*i*) - *S*(*i* - 1), ( 20 21 Unable to parse markup [type=CF_TEX] 22 23 and with end at *x* = 1. Union looks like a downward convex polyline, lets represent it sequence of points, adjacent are connected. So calculate *i*'s union, if new union will be contains new segment, this segment must intersects two segments of union, this intersection we can calculate for the amount of points in union. All points lower than new segment must be erased from union. Because each segment can add at most one point in union calculating of one range is O(*n*2). 24 25 #### F: [379F - New Year Tree](/contest/379/problem/F "Good Bye 2013") 26 27 Coming soon. 28 29 #### G: [379G - New Year Cactus](/contest/379/problem/G "Good Bye 2013") 30 31 This problem can be solved for tree by using of dynamic programming *d*[*v*][*c*][*a*], where *v* — vertex, *c* — type of vertex(whose toys are hanged or nothing are hanged there), *a* — number of toys hanged by Jack for this subtree, *d*[*v*][*c*][*a*] denote of maximum number of toys which can be hanged by Jill. Value *d*[*v*][*c*][*a*] can be calculated iterated through sons of *v* vertext and type of these vertices. Let's compress our cactus into tree by compressing each cycle into vertex. Vertex of tree will be looks like sequence of vertex from cactus which have edges not from this cycle and intermediates that belongs only to this cycle. Now we can calculate all *d*[*v*][*c*][*a*] for this tree but we must be carefully processing a vertices.