Borjianamin's blog

By Borjianamin, history, 7 months ago, , Hi.
I want to solve a question. I know how to solve it but I want a better way to solve it. in first line number n is given and in second line, n numbers is given. We call value of i-th number as P_i. For the i-th number and j-th number, if (i - j) (P_i - P_j) < 0 is true, then there is edge between i and j in graph. (graph is undirected)
We want to find connected component of graph and print vertices in each connected component.

Input 1:
4
2 3 1 4
Output 2:
2
3 1 2 3
1 4
(output: print number of connected component, then each line, first print number of vertices in that component, then print vertices in increasing order)

Memory limit: 128MB
Time limit: 1 second
1 <= n <= 1000000

I noticed that the property, is property for checking inversion in an array. However the nlogn approach is only for count inversions but if I want to find them, then I need linear search in merge each time and so,my algorithm is not nlogn anymore.
There is two approach for find components. one of them is DFS and other is Disjoint set how every we want to print connected component so I thick that I couldn't use Disjoint set.
because of time limit and memory limit, I didn't know a best way.
Is it possible to help me or give me a idea?
Thanks. Comments (7)
 » Do you have a link to the problem? I think you can solve it in a similar divide and conquer way with Disjoint set, and if you do the implementation a certain way then it will amortize to $O(n \log n)$, but it would be nice to submit to a judge to verify before I post a possibly incorrect solution.
•  » » I didn't try it but If I want to use disjoint set, I need a vector to keep component and when merge two sets, merge two vector too. If it is correct, I will try it. if you have better way, please comment.
•  » » » What I've done is the classic merge sort inversion algorithm, but the only difference is as follows:When merging the two sorted vectors, if we take an element from the right list, we know that it should have an edge to everything remaining in our left list. However, we note that it will all become one component after that, so for any future elements in our right list that we need to merge, we can just merge it with the first element in our left list at that time. Thus, the first time we take an element from the right list, we merge with everything remaining in the left list, and then for all future elements we take from the right list, we merge with the front element remaining in the left list. This should keep the $O(n)$ factor of merging two lists the same (with perhaps some negligible ackermann term), so the complexity of the whole algorithm will remain close to $O(n \log n)$. Codetypedef pair pii; // p[i].first will contain the permutation // p[i].second will contain the index, so p[i].second = i as initialization pii p[N]; void solve(int l, int r) { if(l == r) return; int m = (l+r)/2; solve(l, m); solve(m+1, r); vector v; int id1 = l, id2 = m+1; bool connected = false; while(id1 <= m || id2 <= r) { if(id1 > m) v.push_back(p[id2++]); else if(id2 > r) v.push_back(p[id1++]); else if(p[id1].first < p[id2].first) v.push_back(p[id1++]); else { if(connected) { join(p[id2].second, p[id1].second); } else { for(int i = id1; i <= m; ++i) join(p[id2].second, p[i].second); connected = true; } v.push_back(p[id2++]); } } for(int i = l; i <= r; ++i) p[i] = v[i-l]; } There is probably a much cleaner way to attack this, but I think it should work (there also could be a bug, I don't know).
•  » » » » Thanks so much. I do it at first without any change in inversion count. I get some time limit but most of test are passed. When I implement your idea, I passed all tests. I didn't think about your amazing tip!!! Thanks.
•  » » » » » No problem, thanks for the problem! This was a really unique problem and this insight doesn't seem to be a common one.
 » please provide the link to the problem...
•  » » I couldn't provide. This is not in codeforces. It is a local site in our university used for contest and after contest we can send answer. It is private and I couldn't send a link for judge. I'm sorry.