, 
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.
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 orn.
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.
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.
This problem had little in common with problem 208E - Blood Cousins. 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.
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 vand deque <set > z. This deque for every depth i of the subtree of v save set — all different names (integers) on depth i.
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.
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.
Không có nhận xét nào:
Đăng nhận xét