ARRGRAPH - EDITORIAL

general
, , , , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Praveen Dhinwa
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Union-Disjoint 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 co-prime.

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

  • Use union disjoint sets to check whether the graph is already connected. Union operations can be performed naively in O(N^2).
  • If the graph is connected, print the array. Otherwise, It can be proved that changing exactly one element in the array can make the graph connected.
  • Choose one position in the array, replace it with a prime not used in the array. (Prime not used can be found by the sieve, and are guaranteed to exist since the graph is connected.)

EXPLANATION

So, 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 co-prime, 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 Union-Disjoint 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 co-prime 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 :smiley:

Let’s us suppose we choose a prime since it will not be co-prime 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 Co-prime 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 problem

I 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
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

2

One more problem E. Connected Components?.

1 Like
3

Yes, I had done the contest, but just didn’t find the link.

4

I solved it a few days ago during the long challenge. So, I didn’t experiment its soln with Coprime Components. Reasons -
I already got full points.
Plagiarism hammer.

1 Like
5

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.

6

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

7

Test cases for this problem were weak. And me and my friends are noticing that everyday test cases are getting weak on codechef problems.
For this problem, many people just checked whether for every index i, there exists an index j such that gcd(a[i], a[j])=1. If yes then answer is 0 otherwise 1. But this solution fails when array is
A=[15, 14,21, 10] and many solutions will fail in this case. Bcz here (15, 14) makes a connencted component and another connected component is (21, 10). So every number is connected with one another but still graph is not connected.
PS: Some of my friends also did the same thing and they got AC :P.

Another such case:

In problem PERIODIC, we submitted a wrong solution that fails even when n=15. But still we got 50 points that lead us to wrong assumption that we are doing well. Actually after finding every k, we took minimum but actually we needed gcd to get AC.

2 Likes
8

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.

9

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 6-7 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.

10

Some one please give me a reply. !!

11

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.

12

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.

13

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!

14

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 unique-value 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.

My Python code