246.md (3503B)
1 Source: https://codeforces.com/blog/entry/5934 2 3 [246A - Buggy Sorting](/contest/246/problem/A "Codeforces Round 151 (Div. 2)") 4 5 In this problem you should hack the sorting algorithm, of course it was incorrect. It was correct only for arrays with *n* < = 2. In other cases you could print *n*, *n*–1, ..., 1 as a counter-example. To make the sorting right, the second cycle should be from 1 but not from *i*. 6 7 [246B - Increase and Decrease](/contest/246/problem/B "Codeforces Round 151 (Div. 2)") 8 9 Note, that you can always get the answer *n*–1. To get this result you should make first *n*–1 equal using the last element as the second element in pair of given operation. But after it, the whole array could become equal. It could happen if the sum of array’s elements is divisible by *n*. So the answer is *n*–1 or *n*. 10 11 [246C - Beauty Pageant](/contest/246/problem/C "Codeforces Round 151 (Div. 2)") 12 13 This problem was rather mathematical. The correct solution is: firstly take every element once, then take the maximum and any other, then two maximums and any other, then three maximums and any other and so on. In this case, you get as many sets as you need in this problem. It is easy to check, that all sums will be different. 14 15 [246D - Colorful Graph](/contest/246/problem/D "Codeforces Round 151 (Div. 2)") 16 17 This problem could be solved in this way: create new graph where vertices are the colors of the given graph. The edge between vertices *u* and *v* belongs this new graph if there are two vertices *a* and *b* in the given graph such that *c*[*a*] = *u* and *c*[*b*] = *v*. So, the answer is such color *k* with minimum number, that the degree of the vertex *k* in the new graph is maximum (without multiple edges). Such solution could be written using *O*(*M*·*log*(*N*)) time. 18 19 [246E - Blood Cousins Return](/contest/246/problem/E "Codeforces Round 151 (Div. 2)") 20 21 This problem had little in common with problem [208E - Blood Cousins](/contest/208/problem/E "Codeforces Round 130 (Div. 2)"). In comments to this problem there was given a solution using structure deque (array in which you can add or delete elements from both endings). Let’s describe solution using this structure. 22 23 Firstly all different names change with different integers and for every vertex *v* save all queries with this vertex. Then for every vertex, which is root of some tree make dfs, the parameters of dfs are vertex *v* and deque <set > *z*. This deque for every depth *i* of the subtree of *v* save set — all different names (integers) on depth *i*. 24 25 This deque could be calculated simply. Consider all sons of *v* and calculate such deque for them. Obviously, the size of our deque *z* will be maximum of sizes of descendants’ deques. Then consider every descendants’ deques and merge appropriate sets of integers. Of course, we will merge smaller set to a larger set. After that you should insert to the beginning of deque *z* the set of size 1 — color of vertex *v*. 26 27 After this, you can at once answer all queries of vertex *v*. Answer is 0 if *v* has no descendants on the depth *k* or the size of *z*[*k*]. It is known that such method has good asymptotic, the author’s solution works about one second. The asymptotic is *O*(*N*·*log*2(*N*)). 28 29 The solution should be realized carefully. You must not copy every element of your set or deque. You should do swap of smaller and greater set or deque without copying elements ant than merge smaller to greater.