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:
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();
}
)