PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: ro27
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Primality testing in \mathcal{O}(\sqrt X) time OR the sieve of Eratosthenes
PROBLEM:
An array A is called frequal if each x\in A has a frequency of exactly d(x) (where d(x) denotes the number of divisors of x).
Given N, construct a frequal array of length N whose number of distinct elements is maximal.
EXPLANATION:
Since we’d like the number of distinct elements to be as large as possible, and each element must occur as many times as it has divisors, ideally we’re looking for numbers with few divisors.
In particular, the best we can do is to use 1 (which has 1 divisor), and any prime p (which has 2 divisors).
Any other integer has \gt 2 divisors, and so isn’t optimal to use.
Why?
Let’s look at a few cases.
- If we have at least two numbers with \geq 3 divisors each, we can replace them all (except maybe 1) with primes.
- Let k denote the total sum of divisors of all these numbers. If k is even, use \frac{k}{2} primes; otherwise use \frac{k-1}{2} primes and one p^2 (which has 3 factors).
- Note that since k \geq 6, this always improves the number of distinct elements of the array.
- If there’s exactly one such number, we look a couple cases again.
- As earlier, let k denote its number of divisors. If k \geq 4, a similar strategy as above increases the number of distinct elements and brings us to the k\leq 3 case.
- If k = 3 and 1 doesn’t already exist in the array, it’s optimal to use a 1 and a prime instead.
- If 1 does exist in the array, we could’ve used two primes instead for the same result.
This gives us a rather simple construction.
- If N is even, find \frac{N}{2} prime numbers and repeat each of them twice.
This gives us \frac{N}{2} distinct elements. - If N is odd, add a 1 to the array and then add two copies each of \frac{N-1}{2} different primes.
This gives us \frac{N-1}{2} + 1 distinct elements.
The only remaining part is actually finding the \approx\frac{N}{2} distinct primes we need.
There are several ways to do that: for example you can precompute primes till a certain limit using a sieve, or even just bruteforce primality testing in \mathcal{O}(\sqrt{X}) time.
In the worst case, we need 10^4 primes; and the 10^4-th prime is just a bit larger than 10^5 so any reasonable primality test (i.e, sqrt or faster) should work.
TIME COMPLEXITY:
\mathcal{O}(N\sqrt{10^5}) (or \mathcal{O}(N) after precomputing primes) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key(a) -> gives index of the element(number of elements smaller than a)
// find_by_order(a) -> gives the element at index a
#define accelerate ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long int
#define ld long double
#define mod1 998244353
#define endl "\n"
#define ff first
#define ss second
#define all(x) (x).begin(),(x).end()
#define ra(arr,n) vector<int> arr(n);for(int in = 0; in < n; in++) {cin >> arr[in];}
const int mod = 1e9 + 7;
const int inf = 1e18;
int MOD(int x) {int a1 = (x % mod); if (a1 < 0) {a1 += mod;} return a1;}
int N = 1e6;
vector<int>yep(N + 1, true);
int power( int a, int b) {
int p = 1; while (b > 0) {if (b % mod1 & 1)p = (p % mod1 * a % mod1) % mod1; a = (a % mod1 * a % mod1) % mod1 ; b >>= 1;}
return p % mod1;
}
void lessgoo()
{
int n;
cin >> n;
if (n == 1) {
cout << 1 << endl;
return;
}
if (n % 2 != 0) {
cout << 1 << " ";
n--;
}
for (int i = 1; i >= 0; i++) {
if (yep[i]) {
cout << i << " " << i << " ";
n -= 2;
if (n == 0)break;
}
}
cout << endl;
}
signed main()
{
accelerate;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int test = 1;
cin >> test ;
yep[0] = yep[1] = false;
for (int i = 2; i <= N; i++) {
if (yep[i] && i * i <= N) {
for (int j = i * i; j <= N; j += i) {
yep[j] = false;
}
}
}
for (int tcase = 1; tcase <= test; tcase++)
{
// cout << "Case #" << tcase << ": ";
lessgoo();
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = []
for x in range(2, 10**9):
if len(a)+2 > n: break
a += [x, x]
for y in range(2, x+1):
if y*y > x: break
if x%y == 0:
a.pop()
a.pop()
break
if n%2 == 1: a.append(1)
print(*a)