### HolkinPV's blog

By HolkinPV, 7 years ago, translation, ,

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 or n.

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 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.

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. The asymptotic is O(N·log2(N)).

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.

• +23

 » 7 years ago, # |   0 Thanks... :D
 » 7 years ago, # | ← Rev. 2 →   +6 problem E: we can also use BIT to solve this problem. first we should read all the queries and change every query (v,k) into (depth , left , right) :depth is the depth of the k sons of v,left and right are the indexes of vector W[d](it saves all the nodes with depth of d),then we can answer all the queries in the same depth together . So we transform the problem to another simple problem ,how many distinct values in an interval .it's easy to solve it just use BIT (off line ). here is my submission
•  » » 7 years ago, # ^ |   0 Any idea how to calculate on-line the number of distinct values in an interval? Thx
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 I think we can use a segment tree whose nodes store all distince values of an interval. The complexity is O(Nlog(N)^2) which is slower than offline solution.Please correct me if I'm wrong.
•  » » » » 7 years ago, # ^ |   0 I'm not sure that this works. When you have a query on the segment tree, you will have to merge all the sub-intervals your interval is made up of. I can not see how you can do this better than O(n). Please describe more of your solution if you think it works.
•  » » » » » 7 years ago, # ^ | ← Rev. 6 →   +6 You're right. I'd try another approach. Let p[i] is the smallest number such that a[p[i]] = a[i] and p[i] > i (nearest occurrence to the right, if there is no such number p[i] = N + 1). Then the queries boil down to count how many elements there are from p[L] to p[R] which are greater than R. Building a segment tree whose nodes store all sorted values of p[] in an interval, this can be done by binary search.
•  » » » » » » 7 years ago, # ^ |   0 Indeed, this solution works:) Thank you
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +3 O(Nlog(N)^2) which is lower than offline solution. As I know, offline solution works in O(NlogN). Do you mean "is higher (bigger, more, worse) than offline solution"?P.S. This online algorithm can be bit modified to O(logN) per query. You should go throw segment tree from up to down, in root use binary search [O(logN)] and each lower vertex gets link from its parent to right position in array [O(1)].
•  » » » » » 7 years ago, # ^ |   0 Sorry, my typo. It should be "slower".
 » 7 years ago, # |   0 HolkinPV, If we do DFS n times, that will take O(N^2) time, wont it? Can you please explain me how to do it properly? that would be a great helo.
 » 7 years ago, # |   0 may somebody explain problem E with a little more description? I can't understand why we are using deque and even can't completely understand the algorithm explained in the editorial
•  » » 7 years ago, # ^ | ← Rev. 8 →   0 Let Q[depth] be a vector >. Strings in sets in Q[depth] are the strings that are searched by now.When we are just starting search node v, and if we need to calculate queries (v,k1), (v,k2), ..., (v,kn) , we should record the end of Q[depth of v + ki] as cur[i]. When we are ending searching node v, the answer to query (v,ki) can be calculated. It equals to the number of distinct strings in Q[depth of v + ki][cur[i]+1] to Q[depth of v + ki][the end of Q[depth of v + ki]. See my code here(2624164) if you still do not understand.
 » 7 years ago, # |   0 in problem 246D — Colorful Graph We don't need to create new graph.it is solvable brute force in O(n+m) my submission
•  » » 7 years ago, # ^ |   +8 Your solution seems to be O(n * m). It's really strange that it gets AC.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -6 my code got AC because the complexity of my code is O(N+M) NOT O(N * M)
•  » » » » 7 years ago, # ^ |   0 It's O(N*M) because of the memset. I think the memset line is not necessary. You can change it with an integer array to keep tracks that a color is already inserted to other color set, so you can increment the set size.
 » 7 years ago, # |   0 For question E,Consider a connected tree where every node has 1 son exactly except for the last one which has 0 sons. ( so the graph is just a line )Then if there are 100000 nodes, and you store the deque for every node, then you store 100000 deques with their lengths being 1,2,...100000 which is 5000050000 elements. wouldn't that be time out?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 When we merge the deques, we don't create a new deque for every vertex. We can use one of the deques (the largest one) from the sons. Answers for the sons will be already calculated at this moment, so we don't care about them anymore :)In your case, only one deque will be created in the entire program — it will travel from children to parents.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 So we don't keep the deques for every vertex? then how do you answer queries if you only have one deque for the root of every tree?Or are you saying to pass the deque from the son to the parent by reference so it doesn't need to be deep copied? But if you do that then you will modify the son's deque so queries to that son will be incorrect.Edit: NVM, didn't read your post in entirety. Thanks I understand now
•  » » » » 7 years ago, # ^ |   +1 We do offline algorithm: for every vertex store all queries that rever to it. Then, it dfs, after the merge, then the deque is correct for the current vertex, answer all queries for this vertex and step out from dfs. Next step this deque, of course, may become incorrect — but all the answers for the children are already stored.
 » 7 years ago, # | ← Rev. 2 →   0 In problem 246D — Colorful Graph, we can just create for each different color a balanced search tree (map or set). If you want to count the neighbouring color diversity of a specific color, just for every edge containing one node of that color, check if the other node's color being connected was already counted or not with the balanced search tree. You can see my simple implementation.
 » 7 years ago, # |   0 Why is the asymptotic O(Nlg^2(N))? I know one of the lg is because of the set, But why always merging the small one into the big one is NlgN? I don't really know how to calculate this type of asymptotic. Could someone teach me, Thank you.
•  » » 6 years ago, # ^ |   -23 yin wei xiao ji he bu chao guo yi ban (o4
 » 4 years ago, # |   0 I submitted a code for "246A — Buggy Sorting" problem and I really think that it's right because the output even is right even in the test ,even if you try to resorted with the algorithm it will not be sorted at all. Can I know why it gives me wrong ? http://codeforces.com/contest/246/submission/11954037
 » 4 years ago, # | ← Rev. 2 →   0 hi, for problem D 246D — Colorful Graph this is my submission the idea is to build for each colour k set of integers Q[k] as described in the problem statement, i need to know the complexity of my solution i think it's O((n+m)lgn) is this true ?
 » 3 years ago, # |   0 I see that many solutions with worst case O(N^2) complexity have passed. those solutions simply added all the k-th sons to a set and found the size of the set. ideally they shouldnt have passed :/. It would easily fail on a test where all nodes are attached to 1 and the query repeatedly asks about direct sons of 1.
 » 2 years ago, # |   -8 I don't understand why this solution gives TLE, it should pass IMO, I've used a similar approach as in the editorial. Please help.Link: 28072464
 » 23 months ago, # |   0 can someone tell me why are we doing if (c[i1] != c[i2])