CAARRAY-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Satyam
Tester: Nishank Suresh, Abhinav sharma
Editorialist: Devendra Singh

DIFFICULTY:

2453

PREREQUISITES:

GCD

PROBLEM:

Given an integer N, construct an array A of length N such that:

  • 1 \leq A_i \leq 10^{18} for all (1 \le i \le N);
  • For all (1 \leq i \leq N), there exists a subsequence S of array A such that the length of the subsequence 2 \leq k \leq N and gcd(S_1,S_2,\ldots,S_k)=i.
    Note that gcd(S_1,S_2,\ldots,S_k) denotes the gcd of all elements of the subsequence S_1, S_2, \ldots, S_k.

It can be proven that it is always possible to construct such A under given constraints. If there exist multiple such arrays, print any.

EXPLANATION:

Take four consecutive numbers, let the smallest one be a, \rightarrow [a, a+1, a+2, a+3].
and on these indices assign values as a\cdot (a+3) , a\cdot (a+2), (a+1)\cdot (a+2) , (a+1)\cdot(a+3). First two elements have a gcd of a ( as a+2 and a+3 are coprime ), similarly second and third element have a gcd of a+2 , first and fourth have a gcd of a+3 and third and fourth have a gcd of a+1. Start assigning values from i=N and keep moving towards 1 by assigning values in windows of size 4. In the end if 1 element remains assign it 1, if two elements remain assign them 1 and 2 otherwise assign 2, 3 and 6. In this way we have a subset of size 2 for each value of g from 1 to N such that the gcd of this subset is g.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long 
const ll INF_MUL=1e13;                                                             
const ll INF_ADD=1e18; 
#define pb push_back               
#define mp make_pair           
#define nline "\n"                              
#define f first                                       
#define s second                                        
#define pll pair<ll,ll>    
#define vl vector<ll>   
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>> 
#define all(v) v.begin(),v.end()
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);        
#endif                 
void _print(ll x){cerr<<x;}     
void _print(string x){cerr<<x;}  
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} 
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using muloset=tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;        
const ll MAX=500500;
void solve(){               
    ll n; cin>>n;
    vector<ll> a(n+5,0);
    ll pos=1;
    for(ll i=(n%4)+1;i<=n-3;i+=4){
        a[pos++]=i*(i+3),a[pos++]=(i+1)*(i+3);
        a[pos++]=(i+1)*(i+2),a[pos++]=i*(i+2); 
    }
    ll ext=1;
    for(ll i=2;i<=(n%4);i++){ 
        a[pos++]=i;
        ext*=i; 
    } 
    if(pos==n){
        a[pos]=ext;
    }
    for(ll i=1;i<=n;i++){  
        cout<<a[i]<<" ";
    }
    cout<<nline; 
    return;           
}                                                        
int main()                                                                            
{ 
    ios_base::sync_with_stdio(false);                                    
    cin.tie(NULL);                         
    #ifndef ONLINE_JUDGE                   
    freopen("input.txt", "r", stdin);                                           
    freopen("output.txt", "w", stdout);      
    freopen("error.txt", "w", stderr);                        
    #endif        
    ll test_cases=1;                   
    cin>>test_cases; 
    while(test_cases--){
        solve();
    }
    cout<<fixed<<setprecision(15);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}    
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    int n;
    cin >> n;
    if (n == 3)
    {
        cout << 2 << ' ' << 3 << ' ' << 6 << '\n';
        return;
    }
    for (int i = n; i >= 1; i -= 4)
    {
        if (i <= 3)
            for (int j = 1; j <= i; j++)
                cout << j << ' ';
        else
        {
            int a = i - 3;
            cout << a * (a + 3) << ' ' << a * (a + 2) << ' ' << (a + 1) * (a + 3) << ' ' << (a + 1) * (a + 2) << ' ';
        }
    }
    cout << '\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}
3 Likes

Whats wrong in this logic : Lets say for n I consider this pattern

2 3 4 5 …, n , (lcm(2,3,4,5,…,n).
@devendra7700

2 Likes

LCM increases very quickly it will exceed 10^{18} for the first 50 numbers

4 Likes

oh ok got it thanks alot!

1 Like

Approach
Property : consecutive numbers are coprime, so if I take a = 2 * 3, b = 3 * 3, gcd(a,b) = 3
So applying this in question, let’s take n = 5

1 * 5 = a
2 * 5 = b
2 * 4 = c
3 * 4 = d
3 * 3 = e

gcd(a, b) = 5
gcd(b, c) = 2
gcd(c, d) = 4
gcd(d, e) = 3
gcd(a, b, c, d, e) = 1

CODE :

#include <bits/stdc++.h>
#define int long long int

void solve(){
    int n;
    std::cin >> n;
    int i = 1, j = n;
    n -= 1;
    while(n > 0){
        std::cout << i*j << " " << (i+1)*j << " ";
        i++, j--, n -= 2;
    }
    if(n == 0)
        std::cout << i*j << " ";
    std::cout << "\n";
}

     
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 1;
    std::cin >> t;
    while(t--){
        solve();
    }
}
13 Likes

It goes more than 10^18 for larger values of n.

for just n = 41, LCM = 219060189739591200

How do we know that subset (size>1) will have gcd = 2.

(a+1)(a+2) is even.

Can someone please tell me how to write this problem’s checker?

[Solution: 66428202 | CodeChef]. How is this solution passing. For n=8 this gives answer as[5,2,3,4,30,42,56,8] and we don’t have a subsequence for which gcd is 7??

1 Like

Lets construct from n to 1, if we are constructing k and 3k <= n, we can get k = gcd(3k, 2k).
So we need to construct numbers from n to ceil(n/3), so we can use n numbers to construct 2n/3 numbers.
a, a-1, a-2, …, a-5, and a*(a-1)(a-5) <= (10^3)^6=10^18, so to construct 6 numbers we can use 7 numbers, 7/6 < 3/2

https://www.codechef.com/viewsolution/66428202 how is this passing. For n=8 this gives answer as[5,2,3,4,30,42,56,8] and we don’t have a subsequence for which gcd is 7??

1 Like

I think the verifier makes a more interesting problem. How did you setup the scoring program? i.e., how can we determine a given solution is correct? For each set of multiples of i, we have to determine if there is a subset whose gcd is i. Is there an efficient way to do this without eventually enumerating all subsets for some cases?

For n = 1000, lcm(2, 1000) > 10 ^ 18, which crosses the constraint

I am fairly certain that something is wrong with the verifier
This is an AC submission (very likely plagiarized) https://www.codechef.com/viewsolution/66430636 that gives the following output for
N=5 case
2 \ 3 \ 4 \ 20 \ 30
There is no way to get a GCD of 5 from this.

N=7 case
2 \ 3 \ 4 \ 5 \ 30 \ 42 \ 56
There is no way to get a GCD of 7 from this.

1 Like

O(N^2)?

I use a different approach.
First, we construct an array B with integers from 2 to N, then sort B in ascending order of the number of suffix 0s of each integer, in another word, __builtin_ctz(x).
Then, we construct array A where A_1 = B_1, A_i = lcm(B_{i - 1}, B_i), 2 \le i \le N - 1, A_N = B_{N - 1}.
You can verify that this A satifies the requirement. (I brute forced, so trust me :smile:)

How the testing exactly happens, it is takes exponential time?

When we are checking if number x is possible we can go through array and only gcd multiples of x, if result = x it’s possible overwise impossible

Yeah explain the O(n^2) solution. I could not find any except 2^n