ALTERNATEDIV - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

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!

TIME COMPLEXITY:

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
please help me.

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 :frowning:

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 :slightly_smiling_face:.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? :slight_smile:

why wrong answer plzzzz help

#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() {
// your code goes here
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” ?
please explain???

No two elements are same.

In this code all even indices of array will be set to 1, therefore array will not be pairwise distinct if n > 2

Which is a required condition :

All A_i are pairwise distinct

After 5 and 10 , 6 and 12 will come . And 6 has already occurred once . To satisfy the condition of pairwise distinct elements , no element should occur twice.And this is the reason your code is giving wrong answer

I came upon this question, and someone who figured out the approach which is the same as the editorial is beyond me.

If you cant understand the solution like me there are 2 things to consider here :

  1. pairwise distinct, that is all numbers are DISTINCT.
  2. The number at even positions (1-based indexing) should either be (a) different parity or (b) greater than the immediate number.

example : 1 2 3 is valid but also 2 4 3 is also valid.

So how do we do this, we just take numbers from 1 till N. Suppose this number is x, then we fill odd position with x and even position with 2*x.

But observe that we want pairwise distinct, so we keep a map so that anytime this 2*x or x is present in the map we just mindlessly increment x till this is not true and proceed till we fill all N positions.

#include <bits/stdc++.h>

#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define sp ' '
#define nl '\n'
#define ll long long
#define ull unsigned long long
#define all(v) v.begin(),v.end()
#define vi vector<int>
#define range(a , min , max) a >= min and a <= max

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    vector<int> v(n);
    map<int , bool> m;
    
    int ctr = 2;
    for(int i = 0; i < n; i += 2) {
        while(m[ctr])
            ctr ++;
        
        v[i] = ctr;
        m[ctr] = true;
        
        if (i + 1 < n) {
            v[i + 1] = ctr * 2;
            m[ctr * 2] = true;
        }
        
        ctr ++;
    }
    
    for(auto &it : v)
        cout << it << sp;
    
    cout << nl;    
}

int main() {
    int tc;
    cin >> tc;
    while(tc--) {
        solve();
	}

    return 0;
}