382.md (4475B)
1 Source: https://codeforces.com/blog/entry/10442 2 3 [382A - Ksenia and Pan Scales](/contest/382/problem/A "Codeforces Round 224 (Div. 2)") 4 5 This problem is just a technic problem. So, you should take weights one by one and place the current one into the side of the scales that contains lower number of weights. At the end you should output answer in the correct format. 6 7 [382B - Number Busters](/contest/382/problem/B "Codeforces Round 224 (Div. 2)") 8 9 In the problem you should understand, what is the structure of Artur's operation. You can see that this operation is near operation (*b* + *x*) % *w* (To see that just apply *b* = *w* - *b* - 1). There is nothing hard to get the formula of changing a during the operation. So, if you have *k* operations, you can see, that *b* = (*b* + *k*·*x*) % *w*, *a* = *a* - (*b* + *k*·*x*) / *w*, *c* = *c* - *k*. When you've got all the formulas, you can solve the problem using binary search. 10 11 [382C - Arithmetic Progression](/contest/382/problem/C "Codeforces Round 224 (Div. 2)") 12 13 This problem is about considering cases: 14 15 1) If *n* = 1, the answer is -1. Because of any two numbers is arithmetical progression. 16 2) If array is constant, the answer if that constant. 17 3) If you have arithmetical progression initially, you can compute its difference *d*. In this case you should just to output *minVal* - *d*, and *maxVal* + *d*, where *minVal* is minimum value among *a*[*i*], and *maxVal* is maximum value among *a*[*i*]. But in case of *n* = 2, also you should check (*a*[0] + *a*[1]) / 2. If this number is integer, it is needed to be output. 18 4) Else, the answer has at most one integer. You find this integer you should sort the sequence, and find the place where the number is missed. If such a place exists you should add the corresponding number to the sequence, else, the answer is 0. 19 5) In all other cases the answer is 0. 20 21 [382D - Ksenia and Pawns](/contest/382/problem/D "Codeforces Round 224 (Div. 2)") 22 23 In this problem from every cell except # there is one next cell. That's why this graph is almost functional graph. If this graph contains a cycle, then answer is -1 because the length of the cycle is at least two. 24 25 In the other case, there are no cycles in the graph. Let's find the longest path in it, denote is as *len*. Then is answer is at least 2·*len* - 1 because we can put the two pawns in the first two cells of this path. 26 27 But in some cases we could get the answer 2·*len* if there are two non-intersecting by vertices (not #) paths of length *len*. They are non-intersecting because if they intersect in some cell then they will be equal to the end (and the statement says that such moves are invalid). 28 29 So, we should check if the graph contains two non-intersecting by vertices (not #) paths of length *len*. It could be done in any way. For example, using dfs searches. 30 31 [382E - Ksenia and Combinatorics](/contest/382/problem/E "Codeforces Round 224 (Div. 2)") 32 33 In this problem you should count trees with some properties. It can be done using dynamic programming. The main idea is that the maximum mathing in tree can be found using simple dynamic *dp*[*v*][*used*] (*v* -- vertex, *used* — was this vertex used in matching). So you should to count the trees tou should include in state of the dynamic values dp[v][0]$ and *dp*[*v*][1]. 34 35 In other words, you should use dynamic programming *z*[*n*][*dp*0][*dp*1] — number of rooted trees with *n* vertices and values of dynamic in root *dp*[*root*][0] = *dp*0 and *dp*[*root*][1] = *dp*1. But in simple implementation this solution will get TL. There are two ways to get AC. The first is to opltimize code and make precalc. The second is to optimize asymptotics. 36 37 The author's solution uses the second way. To optimize solution you should mark that values *dp*0 and *dp*1 differs at most by one. That is *dp*0 = *dp*1, or *dp*0 = *dp*1 + 1. So the first dynamic becomes *r*[*n*][*dp*0][*add*]. Another optimization is there are not so many triples (*n*, *dp*0, *add*) with non-negative values (about 250), so you can you use lazy programming to calculate this dynamic. 38 39 Comments that describe other solutions: 40 41 [http://codeforces.com/blog/entry/10423#comment-158177](https://codeforces.com/blog/entry/10423#comment-158177) 42 [http://codeforces.com/blog/entry/10423#comment-158182](https://codeforces.com/blog/entry/10423#comment-158182)