×

Division 1

Division 2

# Pre-Requisites :

DSU, Number Theory

# Problem :

You are given an array $A$ of size $N$. Now, we create a graph , where there exists an adge between nodes $i$ and $j$ if $A[i]$ and $A[j]$ are co-prime. Find the number of Connected Components in this graph

# Explanation :

As a beginning note, I would like to state that most of the AC submissions on the leaderboard can be hacked with specific cases after reading those solutions, and creating tests for this problem that covers all cases and hacky solutions is quite hard. Now, let's move to the solution :

The first part of this problem is to make some really important observations :

1. We can first convert each number to its square free form, i.e let some number given in the input be $x = p_1^{e_1} \times p_2^{e_2} ... \cdot p_k^{e_k}$, where all $p_i$ are pairwise distinct primes, We can convert this number to $p_1 \cdot p_2 \cdot ... p_k$, since even after this conversion, two initially co-prime numbers still remain co-prime and vice-versa

2. Let us have $2$ components , component $i$ and component $j$. Then, if we can find some number $x$ from component $i$ and some number $y$ from component $j$, such that $(x,y)=1$, then we can merge components $i$ and $j$.

We will use these two crucial observations to solve the problem. Before that, we should use observation $1$ and get new array $A$. Let's consider a modified version of the problem :

Create a modified graph, where there exists an edge between nodes $A[i]$ and $A[j]$,if $(A[i],A[j])=1$. Note that there exists only nodes for $A[i]$ that exists in the input. Now, we can perform dfs/dsu over this graph to get its connected components.

Now, the number of connected components in the original graph can be recovered as follows :

1. For each connected component of size $> 1$, we know that regardless of the frequency of each of the number originally in the input belonging to this component, each of them will create a single connected component in the original graph too. This is due to the fact that for each pair of numbers, there exists another number co-prime to them. So we add $1$ to the answer

2. For each connected component of size $1$, we should add to the answer the frequency of the number of this connected component ( number of times it occurs in the input ) , since each of those elements will form a different connected component in the original graph.

Implemented naively, this can be done in $O(N^{2} \cdot log_2 (max(A[i]))$ time. This should be enough to pass sub task 1.

Here, we notice that the most costly part is how we find and merge the co-prime components.We will try and solve this modified version faster,we can optimize the $(N^{2} \cdot log N )$ part in many ways. We attempt to create a procedure that can find all the co-prime connected components. This procedure purely makes use of prime factorization , co-primness and divisibility, and does not use anything like dfs over complement graphs or so on.

Note that whenever we use the word input, I refer to the modified version of array $A[]$ we create using observation $1$, not the originally given array.

First of all, we need all primes $\le 2 \cdot 10^5$. This can be pre computed using Sieve of Eratosthenes.Next, for each prime $p$, we build a vector $v$, that stores the list of all distinct numbers divisible by this prime, that occur in the input.

Now, we are ready to go to the main part. We maintain a vector active and a function $f(num,pos)$. Initially active contains all numbers that occur at least once in the input. Now, whenever we reach a certain number $num$ for $f$, we try and maintain the active list in such a way that that all numbers having gcd $> 1$ with num are not in the active list.

We ensure that at each step, $pos <$ the total number of primes, and $num \cdot primes[pos] \le 2 \cdot 10^5$. Now, let $curr = num \cdot primes[pos]$ Let us assume all numbers not co-prime to $num$ are not present in the active vector. Now, we also remove from active all numbers that $primes[pos]$ divides. Now, we are left only with numbers that are co-prime to $curr$.

This is the most important step. Since we are left with just the numbers co-prime to $curr$, we merge the connected components of all numbers belonging to active and the connected component of $curr$. Basically, at each step, we sequentially eliminate from the active vector all numbers that a prime belonging to $num$ divides. In the first step, we eliminate all the numbers divisible by the smallest prime that divides num, then the second step and so on. Pseudo Code for this function $f$ looks something like this :

f(num,pos)
{
f(num,pos+1)

// active is a global vector

Now, eliminate from active all numbers divisible by primes[pos]

Now, active only has elements co-prime to num * primes[pos], merge connected components

Now, f(num*primes[pos],pos+1)

Now, undo all changes done to the active vector, and backtrack
}


Basically, we put observation $2$ into practice using an efficient method,.On how to maintain state of the active vector , how to cleverly delete elements from the active vector and so on, you can easily read the code now. This dfs type function visits each element in the range $[1,2 \cdot 10^5]$ exactly once.

What we just did is ensure that when we reach it, we have a vector such that all elements not co-prime to it are absent from the vector. After we finish processing an element, we undo all changes done to the active vector by this $primes[pos]$, and then backtrack.

Overall , this process has a time complexity of $O(maxn \cdot log^2 (maxn))$, where $maxn = 2 \cdot 10^5$.

Another Noteworthy Solution by @karolis_kusas : Link

If you feel short of understanding even after reading this, please let me know in comments. I'll try and elaborate even more, but most probably you should be able to understand after reading the code too. Also, you can also read about some additional comments / alternative solutions for this problem here

6★anand20
121312
accept rate: 0%

19.8k350498541

 3 could you please explain how the complexity is O(maxn⋅log2(maxn))? answered 22 Oct '18, 14:48 2★pk301 627●1●10 accept rate: 16%
 2 well,it seems that the number of times your algorithm calls f(num,pos)is like this: $\sum\limits_{i=1,i\;is\;a\;prime}^{MAXN}\left(\sum\limits_{j=1}[j's\;maxinum\;prime\;divisor\;is\;less\;than\;i]\right)\cdot\lfloor \frac{MAXN}{i}\rfloor$ although it turns out that the formula above is equal to 35083469 when MAXN=200000,which is closed to $N\log^2 N$,I still would like to know how you figure out the time complexity is $O(N\log^2N)$ answered 22 Oct '18, 18:28 21●2 accept rate: 0%
 1 The time limit is too strict. How can you set the time limit as 0.5s when the author's solution itself is taking 0.45s to pass? I have greatly optimized my code but still keep getting TLE on the last test case. answered 22 Oct '18, 17:31 81●4 accept rate: 0%
 0 Should n^2 log n work for 30 points or 5 points ? answered 25 Oct '18, 09:26 2★manni_99 1 accept rate: 0%
 0 manni_99 It is sooner for 5 points, in consideration of 0.5sec TL. answered 26 Oct '18, 20:47 126●4 accept rate: 5%
 0 Can anyone explain how the deletion and insertion into the active vector is being handled. Also can anyone give any tips on how I can optimize my code. I am using set for active and I remove and add elements to it instead of maintaining an active vector. Rest of the logic I think is the same. Every time I see whether num is present in the input(after changing input to square-free form). If it is then I take union of all the elements present in the active at that point and then at the end undo all the changes done in that iteration and delete that num from active set (if it was present in the input). I think the deletion and insertion into the set are not fast enough in my code. Here is a link to my code. answered 02 Nov '18, 06:00 5★aa6565 1●1 accept rate: 0%
 0 How's the complexity O(Nlog(N)log(N)) ? Could you elaborate on that ? I couldn't figure that out even after reading the author's code... answered 17 Nov '18, 19:08 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,303
×639
×374
×211
×125

question asked: 22 Oct '18, 06:10

question was seen: 2,060 times

last updated: 13 Mar, 14:58