Restore Sequence codechef november long challenge problem solution

 Restore Sequence codechef  november  long challenge  problem solution -

Restore Sequence codechef  november  long challenge  problem solution  lets read problem statement.

Alice has a very complex machine ― when fed with a sequence A1,A2,…,AN$A_1,A_2,\dots ,A_N$, it produces a sequence B1,B2,…,BN$B_1,B_2,\dots ,B_N$, where for each valid i$i$, Bi$B_i$ is the largest index j$j$ such that Ai$A_i$ divides Aj$A_j$ (since Ai$A_i$ divides itself, such an index always exist). For example, if the machine is fed with A=[2,6,5,3,4]$A=[2,6,5,3,4]$, it produces B=[5,2,3,4,5]$B=[5,2,3,4,5]$.

Alice gave you a sequence B$B$ that was produced by the machine. Find an integer sequence A$A$ such that when it is fed into the machine, then the machine produces the sequence B$B$. Alice does not like huge integers, so make sure that 1≤Ai≤4⋅106$1\le A_i\le 4\cdot {10}^6$ holds for each valid i$i$.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains a single integer N$N$.
• The second line contains N$N$ space-separated integers B1,B2,…,BN$B_1,B_2,\dots ,B_N$.

Output

For each test case, print a single line containing N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$. For each valid i$i$, 1≤Ai≤4⋅106$1\le A_i\le 4\cdot {10}^6$ should hold.

If there are multiple solutions, you may print any of them. It is guaranteed that at least one solution exists.

Constraints

• 1≤T≤2⋅104$1\le T\le 2\cdot {10}^4$
• 1≤N≤105$1\le N\le {10}^5$
• 1≤Bi≤N$1\le B_i\le N$ for each valid i$i$
• the sum of N$N$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$

Subtasks

Subtask #1 (20 points): B1,B2,…,BN$B_1,B_2,\dots ,B_N$ are pairwise distinct

Subtask #2 (80 points): original constraints

Example Input

2
5
5 2 3 4 5
4
4 4 4 4

Example Output

2 6 5 3 4
2 6 3 12

link-https://www.codechef.com/NOV20B/problems/RESTORE

Restore Sequence codechef Solution -

read also -https://www.technicalkeeda.in/2020/11/magical-candy-problem-solution-codechef.html

Logic-

It's necessary that b[i]>=i

let's assume my final ans is 2*n,2n-1,2n-2,2n-3...........n+1

I choose this initial sequence because ith element of this sequence cannot divide any other incoming element of this sequence.

store this sequence into a final answer vector

Now you have to change this sequence in such a way it can produce given B.

Now start iterating given array B.

Now change final ans like this

int k=v[i];

            if(v1[i]>v1[k-1]){

                v1[k-1]=v1[i];

            }

            else{

                v1[i]=v1[k-1];

            }

Finally, print ans vector.

Follow the code below.

Note-

This question can be done by another approach. 

Must Join Telegram channel for Editorial -

https://t.me/competitiveProgrammingDiscussion

Other Solution-https://www.technicalkeeda.in/2020/11/Iron-magnet-problem-solution-codechef.html

My code-