Graph on an array CodeChef SnackDown 2021 Advance Practice Contest

Question:

You are given a sequence of integers A1,A2,…,AN. You may change any number of its elements (possibly zero), obtaining a new sequence of positive integers B1,B2,…,BN. Each element of B must be an integer between 2 and 50 (both inclusive).

Let's define an undirected graph G with N vertices (numbered 1 through N). For each pair of different vertices i and j, there is an edge between i and j if and only if Bi and Bj are coprime.

You should choose the sequence B in such a way that G is a connected graph. The number of elements which need to be changed to obtain B from A should be minimum possible. Find one such sequence B and the minimum required number of changes.

It can be proven that a solution always exists — it is always possible to modify sequence A in such a way that G is connected.

Input:

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N.
• The second line contains N space-separated integers A1,A2,…,AN

Output:

For each test case, print two lines. The first line should contain a single integer — the minimum required number of changes. The second line should contain N space-separated integers B1,B2,…,BN — the modified sequence.

If there are multiple solutions, you may print any one.

Constraints:

• 1≤T≤3⋅104
  
• 1≤N≤50
  
• 2≤Ai≤50 for each valid i i

Example Input

2
2
2 3
2
2 4

Example Output

0
2 3
1
2 3

Explanation

Example 1: There is an edge in G$G$ between vertices 1$1$ and 2$2$. This graph is connected, so there is no need to change any elements.

Example 2: There is no edge between vertices 1$1$ and 2$2$ since gcd(2,4)≠1$\mathrm{g}\mathrm{c}\mathrm{d}(2,4)\ne 1$. This graph is not connected. We can change element A2=4$A_2=4$ to 3$3$ and make this graph connected.

Program Code in C++

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int tc;

vector <int> parent(55);

void make_set(int i){

parent[i] = i;

}

int find_parent(int v){

if (v == parent[v]) return v;

return parent[v] = find_parent(parent[v]);

}

void set_union(int a,int b){

a = find_parent(a); b = find_parent(b);

if (a != b)

parent[b] = a;

}

int main(){

FIO;

cin>>tc;

while(tc--){

int n;

cin>>n;

vector <int> arr(n);

parent.resize(n);

for (int i=0;i<n;i++) {cin>>arr[i];make_set(i);}

for(int i=0;i<n;i++){

for(int j=i+1;j<n;j++){

if (__gcd(arr[i],arr[j]) == 1)

set_union(i,j);

}

}

int cnt = 0;

for (int i=0;i<n;i++){

if (find_parent(i) == i) cnt++;

}

if (cnt == 1){

cout<<"0"<<endl;

for(int i=0;i<n;i++) cout<<arr[i]<<" ";

cout<<endl;

}

else {

int minPrime = *min_element(arr.begin(),arr.end());

if (minPrime  == 47) arr[0] = 43;

else arr[0] = 47;

cout<<"1"<<endl;

for (int i=0;i<n;i++) cout<<arr[i]<<" ";

cout<<endl;

}

}

}

Links:

Dance Moves CodeChef SnackDown 2021 Round 1A

Min Max LCM CodeChef SnackDown 2021 Round 1A

Round Robin Ranks CodeChef SnackDown 2021 Round 1A

Chefland And Average Distance Solution

Protecting the Poison Solution

Lighting Rectangle Solution

Robot Walk Solution

Floor Division Game CodeChef SnackDown 2021 Advanced Practice Contest 

Yet Another SubSegment Sum Problem CodeChef SnackDown 2021 Advanced Practice Contest

CodeChef SnackDown 2021 Beginner Practice Contest

Register for CodeChef SnackDown 2021

More info about CodeChef SnackDown 2021 

More information

CodeChef is one of the largest online coding platform and SnackDown is one of it's of grandest programs held ever year. SnackDown is a global programming event that invites programmers all over the world to participate in India's most prestigious multi-round programming competition. SnackDown is open to everyone who has a knack in programming. 

This question that is Graph on an Array is of CodeChef SnackDown 2021 Advanced Practice Contest. Here you will get a brief explanation of the problem and after reading the explanation if you are still stuck and have no clue to understand the problem then you can visit the solution of the question given above.

Hope you learnt something from this explanation and solution. Code it guys, practice coding more and more.