PROBLEM LINK:Setter: Praveen Dhinwa DIFFICULTY:Easy PREREQUISITES:UnionDisjoint Sets and Number theory (Knowledge of graphs and Connected components will be helpful). PROBLEM:Given an array $A$ of length $N$, We create graph consisting of $N$ vertices, each corresponding to an element in array $A$. Undirected edge (a,b) is added if and only if $gcd(A_a, A_b)$ is one. That is, $A[a]$ and $A[b]$ are coprime. We need to check whether this graph is connected or not, and if it isn't connected, Change the minimum number of elements in the array to make the graph connected, if the graph is always constructed in similar fashion. Note, $2 \leq A[i] \leq 50$ should hold at all times even after modifications. SUPER QUICK EXPLANATION
EXPLANATIONSo, another problem with primes. This editorial has two parts, one focusing on checking whether the graph is connected, and other making the graph connected if it is not yet connected. Initially discussing problem from graph view. First of all, Iterate over every pair of number, and check if there are coprime, if yes, add an edge between two vertices. This way, we have added all edges in $O(N^2)$. Now, using DFS, we can see the number of connected components in this resultant graph. If it is already connected (Number of connected components is 1), our graph is already valid, so we can just print the given array as output. (We can also use UnionDisjoint sets for checking if the graph is connected.) Now, Let's consider that the graph is not connected. Think about a number which will be coprime to all numbers (So that we will connect this vertex to all other vertices in the graph, getting connected graph irrespective of all other values in the array, in just one step. I know you all are good enough to guess I'm talking about $1$, but problem setter intentionally choose to keep $2 \leq A[i] \leq 50$ to make this task a bit harder :D Let's us suppose we choose a prime since it will not be coprime only to its multiples. Choose a prime above $N/2+1$ makes sure that only multiple of this number in the array is the element itself. So, just choose a prime and replace any element in array with this prime. I choose 47. Suppose evil setter already knows of this solution and set all values in the array as 47. Isn't our solution trapped? So, how do we handle this, Simple!! Just take another prime. It can be proven that the problem will be solved in one step since we can choose one element in the array, replace it with any such prime number in the array. But, we shall make his effort useless, by noticing that we can always make the graph connected, in just one step. For proof, see primes above or equal to $N/2+1$. Let's call them good primes. We can prove that if the graph has at least two good primes, then the graph is connected. Reason: Suppose we have two good primes in the array, so, It's guaranteed that all other elements in the array will be connected to at least one of the good prime. Thus, Graph is divided into at most two components, one containing first good prime while other containing the second good prime. These two good primes will also be connected to each other since two distinct primes are always Coprime to each other, Resulting in the graph being connected. So, I took primes 41 and 47 for this purpose, If the array doesn't consist of all 47, replace the first element with 47 and that's it. Otherwise, replace the first element with 41. The reason of not choosing a prime smaller than or equal to $N/2$ is that we will need to be careful about choosing which element to replace, and also handle multiples of this prime present in the array. It can be done easily, but choosing a good prime makes things simple enough. To Problem setter, Thanks a lot for proofreading editorial as well as suggesting important points to be kept in the editorial. Related problemI guess those all those who participated in October long challenge already know about one such problem. For those who didn't, Coprime Components. Please suggest more such problems. Time Complexity$O(N^2)$ for initial graph construction dominate overall time complexity. Apart from that, all other operations take time of order $O(N)$. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 19 Oct '18, 04:45

Test cases for this problem were weak. And me and my friends are noticing that everyday test cases are getting weak on codechef problems.
answered 22 Oct '18, 16:33

One more problem E. Connected Components?. answered 21 Oct '18, 19:41
Yes, I had done the contest, but just didn't find the link.
(21 Oct '18, 19:51)
1
I solved it a few days ago during the long challenge. So, I didn't experiment its soln with Coprime Components. Reasons 
(21 Oct '18, 20:00)

I wanted to confirm something. I checked a solution and in that the user simply checked if each element in the set has a number coprime to it. And if not then he replaces any one element with 43 or 47 as explained in the editorial. But I want to know why is this approach correct. Even if all the numbers do have a coprime partner, is it not possible that we get for example 2 connected components in the graph. answered 21 Oct '18, 21:17
Our solution was the same, but we simply iterated over the entire array to check if the array was already perfect or not, instead of forming a graph and performing DFS/DSU. The rest of the steps are pretty much the same. @nitangle @aryanc403 here's ours: https://www.codechef.com/viewsolution/21016053
(21 Oct '18, 22:17)
well you do need to chech the connected components. If connected components are 1, you are done else 47 or if 47 is already there 43.
(22 Oct '18, 19:34)

Hi , I wanted to create a separate post for this, but let me put it here first. According to the solution provided above, it is quite clear that the approach I have taken is same. However, I wasted around 67 hours simply because my code was getting a TLE. I wrote the program in Java, Python and C++ to see if it is accepted in any. After the contest I discussed my code with another codechef user(my friend) and he had done exactly the same thing with almost same code. Luckily, he has got a "correct answer" just within the time limit of 1 sec for C++. I ask and request the admins to please check my code and let me know where the mistake lies. Otherwise, I would have to say that Codechef has been unfair to me! My 3 different solutions can be found here:
Waiting for your valued response quickly. Thanks in advance. answered 23 Oct '18, 09:14
Some one please give me a reply. !!
(24 Oct '18, 12:09)
No idea about Python solution because I do not know python. For Java, the bottleneck is slow output. I ran a test case with T = 30000, N = 50 and all A[i] = 47. It ran in 4.63 seconds. As for C++, the Same mistake, as this problem involve a lot of input and output. I didn't run any case, but I guess so.
(24 Oct '18, 16:36)
for java, use a stringbuffer for saving intermediate outputs and in the end output that stringbuffer. println is slow. for c++, there is fast io by turning off synchronization. google it and you will find.
(24 Oct '18, 23:14)
Thanks guys for replying. If that is the case it feels bad that even though the logic was correct I wasn't rewarded. Very unfortunate. For C++, my friend had done same implementation of io and it has passed. So there is definitely something inconsistent in Codechef server!
(26 Oct '18, 18:33)

One thing not noted in the editorial: The number of test cases was given as "up to" $3\times 10^4$. This means that it is easily worthwhile to precalculate the coprime status of every possible combination of two numbers in the range $2 :50$. (if the range were larger, I would have made this a little more Then instead of a lot of calls to a $\gcd$ calculation, you are just looking up the status each time. I also reduced the given number list to a uniquevalue set, after checking that $n>1$. Things to note here are that a single value set of more than one element is not connected, and a single connection between two unique values means that all instances of those two values form a connected graph in the original set. Then I started testing for connection from large numbers downwards, since large primes connect to everything and large composites sweep for smaller primes to test. answered 30 Oct '18, 03:47
