Problem Link :
[Division 1][1]
[Division 2][2]
Author : [Bogdan Ciobanu][3]
Tester : [Misha Chorniy][4]
Editorialist : [Anand Jaisingh][5]
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 :
-
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
-
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 :
-
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
-
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 .
Authors Code : [Link][6]
Another Noteworthy Solution by @karolis_kusas : [Link][7]
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][8]
[1]: https://www.codechef.com/OCT18A/problems/CPCOMP))
[2]: https://www.codechef.com/OCT18B/problems/CPCOMP
[3]: https://www.codechef.com/users/bciobanu
[4]: https://www.codechef.com/users/mgch
[5]: https://www.codechef.com/users/anand20
[6]: https://www.ideone.com/N11lPY
[7]: https://www.codechef.com/viewsolution/20611956
[8]: https://discuss.codechef.com/questions/137838/please-share-your-approach-to-cpcomp-problem-of-oct-long-challenge