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.
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
Any idea how to calculate on-line the number of distinct values in an interval? Thx
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.
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.
You're right. I'd try another approach. Let p[i] is the smallest number such that
a[p[i]] = a[i]andp[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.Indeed, this solution works:) Thank you
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)].
Sorry, my typo. It should be "slower".
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.
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
Let Q[depth] be a vector<set<string> >. 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.
in problem 246D — Colorful Graph We don't need to create new graph.
it is solvable brute force in O(n+m) my submission
Your solution seems to be O(n * m). It's really strange that it gets AC.
my code got AC because the complexity of my code is O(N+M) NOT O(N * M)
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.
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?
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.
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
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.
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.
Exactly! Don't get how that problem is rated 1700 lol
It's 1600 btw
I solved it before the rating were recalculated.
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.
yin wei xiao ji he bu chao guo yi ban (o4
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 ?
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.
I also thought they should TLE but those are actually correct solutions. These guys are big-brain. Note that they actually store the solution for the same set of sons. It can be proved that the total size of these sets is at most $$$O(n\sqrt{n})$$$. Consider a node $$$u$$$. Let $$$p_1,p_2,\dots,p_k$$$ be its ancestors, where $$$p_i$$$ is $$$u$$$'s $$$i$$$-th ancestor. Then $$$u$$$ is in the set of queried sons if and only if we are querying ($$$p_i,i$$$). We claim that there are only $$$O(\sqrt{n})$$$ possible outcomes of these sets.
Observe that the $$$(i+1)$$$-the son query of $$$p_{i+1}$$$ is strictly larger than the $$$i$$$-the son query of $$$p_{i}$$$ if and only if $$$p_{i+1}$$$ has a $$$(i+1)$$$-th son which is not a $$$i$$$-th son of $$$p_i$$$. This means it has a different branch with depth at least $$$(i+1)$$$. Therefore the subtree rooted at $$$p_{i+1}$$$ is at least $$$(i+1)$$$ larger than the subtree rooted at $$$p_i$$$. So the "size increase" of query outcome can happen at most $$$O(\sqrt{n})$$$ times because the tree size would exceed $$$n$$$ otherwise. Apply the same argument for every node we can conclude that the total size of these query outcomes is at most $$$O(n\sqrt{n})$$$.
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
E can be solved using DSU on trees too. See this blog.
can someone help what's wrong with my solution of problem D. I do simply dfs and store all the diverse neigh. solution
Refer this