ALTERNATEDIV - Editorial

infinitepro · March 5, 2022, 4:45pm

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

dark_69 · March 5, 2022, 5:40pm

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;

divinekosmos · March 5, 2022, 5:43pm

same here

kshitij123k · March 5, 2022, 5:45pm

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";

}

}

dark_69 · March 5, 2022, 5:49pm

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

kshitij123k · March 5, 2022, 6:55pm

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";

}

mayank_2807 · March 6, 2022, 6:55am

bro this code give wrong answer for n=1

mayank_2807 · March 6, 2022, 7:02am

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

anon96839459 · March 6, 2022, 7:38am

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

agraz030 · March 6, 2022, 12:26pm

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;
}

vansh_69420 · March 6, 2022, 12:26pm

#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

vansh_69420 · March 6, 2022, 12:26pm

#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

polmbil · March 6, 2022, 2:56pm

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;
    }
}

chirag8011 · March 7, 2022, 4:50pm

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;
}

puneetbh_007 · March 7, 2022, 4:50pm

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;
}

prontent_11 · March 8, 2022, 1:11pm

what is the meaning of this term “pairwise distinct” ?
please explain???

pandey_adm · March 8, 2022, 5:59pm

No two elements are same.

pandey_adm · March 8, 2022, 7:19pm

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

blackcoder0212 · April 24, 2022, 9:50am

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

tomb_123 · January 28, 2023, 8:42am

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 :

pairwise distinct, that is all numbers are DISTINCT.
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;
}