0
$\begingroup$

We know how DSU(Disjoint Set Union) can be used to find the connectivity between two users. However, I was wondering if it can be used with a Segment Tree.

Let me explain my idea further. Suppose we have $N$ people, numbered from $1$ to $N$. I have a list of input specifying if two people are friends or not. Running a DSU on the data will tell me if any two people are friends or not. Easy and simple up till here. Now, suppose I have some queries of type, ranges provided in the format $[l_1, r_1]$, $[l_2, r_2]$ up-to $[l_k, r_k]$. I need to answer on the union of these ranges if they all are friends or not.

Now what I thought: Using a bottom-up approach on a Segment Tree, I fill the nodes of the tree with either $0$ or $1$ denoting friends or not-friends. But then I thought that for a query like $[1, 3]$ and 1-based indexing on the Segment Tree, my query will pass as $[1]$ and $[2,3]$ on reaching the bottom of the tree. Now $[2,3]$ will directly return as the tree[node] value but the $[1]$ will pass on to my array that I have used for building the tree. Also, the array should contain a relation between $1$ and ($2, 3$) for proper working of the Tree. Here's when I can't really understand as to how to proceed further.

Maybe the entire idea is wrong and it doesn't really need Segment Trees, or maybe requires more than one Segment Trees. Any help here is appreciated.

$\endgroup$
  • $\begingroup$ Don't try to cheat. This is clearly the problem codechef.com/JAN19A/problems/PARRTY from an ongoing contest. $\endgroup$ – Jakube Jan 10 at 11:24
  • $\begingroup$ @Jakube Well I have provided one way to approach it, I am asking for further recommendation. I don't think that is 'cheating' $\endgroup$ – user94836 Jan 10 at 15:22
  • $\begingroup$ I completely disagree. The idea of these programming contests is not to ask other people to solve the problem for you. You are clearly stuck, so the "one way to solve it" might not even work. Also there is money on the line. So publishing or discussing solutions is not o.k. If you are really don't wanna cheat, and are just curious, then wait a few days until the contest ends and discuss it afterwards. $\endgroup$ – Jakube Jan 10 at 19:21
  • $\begingroup$ From Codechef's COC: "Do not ask or discuss any aspect of any CodeChefs’ problem during an ongoing contest on any other platform, online or offline. Discussion of strategy should be avoided during the contest and postponed till the end." $\endgroup$ – Jakube Jan 10 at 19:21
  • $\begingroup$ @Jakube Any help now? I did read the editorial but wanted to check if it's possible this way. $\endgroup$ – user94836 Jun 24 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy