Problem Link :Author : Bogdan CiobanuTester : Misha ChorniyEditorialist : Anand JaisinghPreRequisites :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 coprime. 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 :
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 :
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 coprime 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 coprime connected components. This procedure purely makes use of prime factorization , coprimness 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 coprime 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 coprime to $curr$. This is the most important step. Since we are left with just the numbers coprime 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 :
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 coprime 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 $. Authors Code : LinkAnother 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 asked 22 Oct '18, 06:10

could you please explain how the complexity is O(maxn⋅log2(maxn))? answered 22 Oct '18, 14:48

well,it seems that the number of times your algorithm calls $\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

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

manni_99 It is sooner for 5 points, in consideration of 0.5sec TL. answered 26 Oct '18, 20:47

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<ll> 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 squarefree 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

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
