SIMPLE

# PROBLEM:

Given an integer N, construct an array A of N elements such that

• A_i \mid A_{i+1} for all odd i,
• A_i \nmid A_{i+1} for all even i,
• A_i \ne A_j for all i\ne j, and
• 1\le A_i \le 2\cdot N for all i.

# EXPLANATION:

Let x=N-\lceil\frac{N}{2}\rceil+1. Then, the following sequence is valid:

[x, 2\cdot x, x+1,2\cdot(x+1), x+2,\dots]
Proof

It is easy to see that the elements at odd indices are in increasing order from x\to N. Similarly, the elements at even indices are in increasing order from 2\cdot x \to 2\cdot N (from 2\cdot x \to 2\cdot (N-1) when N is odd.)

Then,

2\cdot x = 2\cdot(N-\bigg\lceil\frac{N}{2}\bigg\rceil+1) > N

implies the sets \{x, x+1,\dots, N\} and \{2\cdot x, 2\cdot(x+1), \dots, 2\cdot N\} are disjoint; Therefore, all elements of the above sequence are unique.

A_i\mid A_{i+1} can be trivially verified to be true for all odd i.
A_i\nmid A_{i+1} holds true for all even i, since A_i > A_{i+1} (and a greater number cannot completely divide a smaller one).

Thus, the provided sequence fulfills all requirements of the problem, and is therefore valid!

O(N)

per test case.

# SOLUTIONS:

Editorialistâ€™s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

• 1
• 2
• 3
• 4
• 5

0 voters

1 Like

In this Problem, I have solved this problem in this way 1 2 3 6 4 8 5 10 â€¦
but I donâ€™t know why my solution is giving the wrong answer

int n;
cin >> n;
if (n == 1)
{
cout << 1 << endl;
}
cout << 1 << " " << 2 << " ";
if (n % 2 == 0)
{
for (int i = 3; i <= n; i += 2)
{
cout << i << " " << i * 2 << " ";
}
}
else
{
for (int i = 3; i <= n; i += 2)
{
if (i != n)
cout << i << " " << i * 2 << " ";
else
cout << i << " ";
}
}
cout << endl;


same here

whats wrong in my code??? i did exactly same!!!

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define tc int t; cin >> t; while(tâ€“)
#define inputa int n; cin >> n; int a[n]; for(int i=0; i<n; i++) { cin >> a[i]; }
#define inputv int n; cin >> n; vector a(n); for(int i=0; i<n; i++){ cin >> v[i]; }
#define endl â€ś\nâ€ť
#define all(x) x.begin(), x.end()
#define iterate(x) for(auto &it : x)

void faster() {

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif


}

int main(){

faster();

tc{

int n;
cin >> n;


if(n==1){
cout << 1 << â€ś\nâ€ť;
continue;
}
else if(n==2){
cout << â€ś1 2â€ť << â€ś\nâ€ť;
}

 int ans = 1;

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

if(i & 1){
cout << ans << " " ;
ans = ans*2;
}
else{
cout << ans << " ";
ans++;
}

}

cout << "\n";

}


}

your code is exceeding 2*N value which is given condition
and for n=2, it is outputting 1 2 two times

now???

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define tc int t; cin >> t; while(tâ€“)
#define inputa int n; cin >> n; int a[n]; for(int i=0; i<n; i++) { cin >> a[i]; }
#define inputv int n; cin >> n; vector a(n); for(int i=0; i<n; i++){ cin >> v[i]; }
#define endl â€ś\nâ€ť
#define all(x) x.begin(), x.end()
#define iterate(x) for(auto &it : x)

void faster() {

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif


}

int main(){

faster();

tc{

int n;
cin >> n;

if(n==1){
cout << 1 << "\n";
continue;
}
else if(n==2){
cout << "1 2" << "\n";
continue;
}
else{

int ans = 1;

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

if(i & 1){
cout << ans << " " ;
ans = ans*2;
}
else{
cout << ans << " ";
ans++;
}

}

cout << "\n";


}

}

}

bro this code give wrong answer for n=1

bro u dont even try your code on sample test case .It will wrong answer for all i>=6;

Why my solution 59740986 did not work ?
Can some one provide me the test case on which it is not working?

#include <bits/stdc++.h>
using namespace std;
int main(){
long long int n,a;
cin>>n;
while(nâ€“){

cin>>a;
vectorv;

v.push_back(1);
for(int i=1;i<a;i++){
if((i+1)%2==0){
int k = v[i-1]*2;
v.push_back(k);
}else{
int f = v[i-1]+1;
v.push_back(f);
}
}
for(auto i :v){
cout<<i<<" ";
}
cout<<endl;

}

return 0;
}

#include <bits/stdc++.h>

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}

#define ll long long

#define INF 1000000007

//INPUT:

#define testcase int t; cin >> t; while(tâ€“)

#define rep(i,a,b) for(int i=a;i<=b;i++)

//DEBUGGING OUTPUTS:

#define arrout(arr) for(int i=0;i<(sizeof(arr)/sizeof(arr[0]));i++){ cout << arr[i] << " ";}

#define vectout(v) for(int i=0;i<v.size();i++){ cout << v[i] << " ";}

#define mapout(m) for(auto i: m){ cout << i.first << " " << i.second << endl;}

using namespace std;

int main(){

sync;

#ifndef ONLINE_JUDGE

freopen(â€śinput.txtâ€ť, â€śrâ€ť, stdin);

freopen(â€śoutput.txtâ€ť, â€śwâ€ť, stdout);

#endif

testcase{

int n;

cin >> n;

int op=n;

int i=5,switcher=1,previ;

if(n==1){

cout << 2 << endl;

continue;

}

else if(n==2){

cout << 1 << " " << 3 << endl;

continue;

}

else if(n==3){

cout << 1 << " " << 3 << " " << 2 << endl;

continue;

}

else if(n==4){

cout << 1 << " " << 3 << " " << 2 << " " << 4 << endl;

continue;

}

else{

cout << 1 << " " << 3 << " " << 2 << " " << 4 << " ";

n-=4;

while(n){

if(switcher){

cout << i << " ";

previ=i;

i++;

nâ€“;

switcher=0;

}

else{

cout << previ*2 << " ";

nâ€“;

switcher=1;

}

}

cout << endl;

}

}

return 0;

}

WHAT WENT WRONG HERE IN THIS CODE? CAN SOMEONE EXPLAIN

#include <bits/stdc++.h>

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}

#define ll long long

#define INF 1000000007

//INPUT:

#define testcase int t; cin >> t; while(tâ€“)

#define rep(i,a,b) for(int i=a;i<=b;i++)

//DEBUGGING OUTPUTS:

#define arrout(arr) for(int i=0;i<(sizeof(arr)/sizeof(arr[0]));i++){ cout << arr[i] << " ";}

#define vectout(v) for(int i=0;i<v.size();i++){ cout << v[i] << " ";}

#define mapout(m) for(auto i: m){ cout << i.first << " " << i.second << endl;}

using namespace std;

int main(){

sync;

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);


#endif

testcase{

  int n;

cin >> n;

int op=n;

int i=5,switcher=1,previ;

if(n==1){

cout << 2 << endl;

continue;

}

else if(n==2){

cout << 1 << " " << 3 << endl;

continue;

}

else if(n==3){

cout << 1 << " " << 3 << " " << 2 << endl;

continue;

}

else if(n==4){

cout << 1 << " " << 3 << " " << 2 << " " << 4 << endl;

continue;

}

else{

cout << 1 << " " << 3 << " " << 2 << " " << 4 << " ";

n-=4;

while(n){

if(switcher){

cout << i << " ";

previ=i;

i++;

n--;

switcher=0;

}

else{

cout << previ*2 << " ";

n--;

switcher=1;

}

}

cout << endl;

}


}

return 0;

}

WHAT WENT WRONG HERE IN THIS CODE? CAN SOMEONE EXPLAIN

why is this code giving wrong ans

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll i=1;
while(n--)
{
cout<<i<<" ";
if(n!=0)
{
cout<<i*2<<" ";
n--;
}
if(i==1)
{
i=3;
continue;
}
i++;
}
cout<<endl;
}
}


What is wrong with my code
I did the exact same thing
2 4 3 6 4 8 5 10 6 12 7 14 8 16 â€¦

#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define mod 1000000007

void solve(){
int n;
cin>>n;
vector<int>v(n);
int k=2;
for(int i=0;i<n;i+=2){
v[i]=k;
k++;
}

for(int i=1;i<n;i+=2){
v[i]=v[i-1]*2;
}

for(int i=0;i<n;i++){
cout<<v[i]<<" ";
}
cout<<endl;
}

int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}


Why is this coming wrong answer??
#include<bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(tâ€“){
int a;
cin>>a;
int b[a];
for(int j=0;j<a;j++){
if(j==0){
b[j]=1;
}else if(j%2!=0) b[j]=j+1;
else b[j]=1;
}
for(int j=0;j<a;j++){
cout<<b[j];
}
cout<<endl;
}
return 0;
}

what is the meaning of this term â€śpairwise distinctâ€ť ?