PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Binary search, math
PROBLEM:
The div-MEX of an array is the smallest positive integer that doesn’t divide any element of it.
You’re given an array A (1 \leq A_i \leq M).
At most one element of A can be replaced by any integer between 1 and M.
Find the maximum possible div-MEX of A.
EXPLANATION:
The div-MEX is the smallest integer that doesn’t appear as a divisor of anything else - so, to maximize this, we can instead try to maximize k such that 1, 2, 3, \ldots, k all appear as divisors of something.
Let’s think about how to check whether every integer from 1 to k can appear as a factor.
Let c_x denote the number of indices i such that A_i is a multiple of x.
How do I compute this?
Let \text{freq} be an array of length M, where \text{freq}[x] denotes the number of times x appears in A.
Once this is computed, do the following:
- Iterate x from 1 to M.
- For a fixed x, iterate y across all multiples of x, i.e, y = x, 2x, 3x, \ldots till you cross M.
- Once x and y are fixed, add \text{freq}[y] to c_x.
This takes \mathcal{O}(M + \frac{M}{2} + \frac{M}{3} + \ldots + \frac{M}{M}) = \mathcal{O}(M\log M) time.
Now, note that the replacement operation can be thought of as a deletion operation followed by an insertion operation.
For each i from 1 to k,
- If c_x = 0, the number we insert must be a multiple of x, otherwise i won’t appear as a factor of anything.
- If c_x = 1, there’s exactly one element that’s a multiple of x.
If this element is deleted, then we need the value we insert to be a multiple of x; otherwise it can be ignored. - If c_x \gt 2, then even if we delete one element, x will be there as a factor of something else for sure.
So, such x can be ignored entirely.
Now, suppose we choose to delete A_i.
Then, the value we insert in its place must be:
- A multiple of every x \leq k such that c_x = 0.
- A multiple of every x \leq k such that x is a factor of A_i and c_x = 1 (since removing A_i will leave these factors unrepresented).
Clearly, the smallest possible value we need to insert is the smallest common factor of all these numbers: in other words, their LCM.
If this LCM is \leq M, we’re fine - otherwise replacing A_i cannot give us all factors \leq k.
Now, we need a way to compute this quickly enough for every index i.
First, all elements \leq k with c_x = 0 are always present, so we don’t need to go over them all each time: simply compute their LCM once and store it, say as the value L.
Next, when computing the c_x values, if c_x \gt 0, store one index of an element that’s a multiple of x.
If c_x = 1 this will then be the unique element that’s a multiple of x.
Let this be id_x.
Let r_i denote the LCM of all the divisors of A_i that are \leq k but have c_x = 1.
To compute this quickly, start with r_i = 1 for every i; then for each x from 1 to k,
- If c_x = 1, set r_{id_x} = \text{lcm}(r_{id_x}, x).
Finally, check if \text{lcm}(r_i, L) \leq M for any i or not, which can be done by just iterating through them all.
Overall, this takes \mathcal{O}(N + M) LCM operations: one pass from 1 to k to populate the r_i values and also compute L (the LCM of all x with c_x = 0), and then one pass through the r_i values.
Each LCM operation takes \mathcal{O}(\log M) time.
Note that the LCM when computing the value of L can get quite large, so you should break out immediately once it crosses M.
This gives us a relatively quick way to check whether obtaining every factor from 1 to k is possible.
Now, simply binary search to find the largest value of k which is valid; and the answer is k+1.
TIME COMPLEXITY:
\mathcal{O}((N+M)\log^2 M) per testcase.
CODE:
Tester'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<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case)
{
ll n,m; cin >> n >> m;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
vector<ll> cnt(m+5);
rep1(i,n) cnt[a[i]]++;
vector<ll> mul(m+5);
rep1(i,m){
for(int j = i; j <= m; j += i){
mul[i] += cnt[j];
}
}
vector<ll> mul_val(m+5);
rep1(i,m){
if(mul[i] != 1) conts;
for(int j = i; j <= m; j += i){
if(cnt[j]){
mul_val[i] = j;
}
}
}
auto ok = [&](ll mid){
ll lc = 1;
vector<ll> lci(m+5,1);
rep1(i,mid){
if(mul[i] > 1) conts;
if(!mul[i]){
lc = lcm(lc,i);
amin(lc,(ll)inf1);
}
else{
ll j = mul_val[i];
lci[j] = lcm(lci[j],i);
amin(lci[j],(ll)inf1);
}
}
rep1(i,m){
if(!cnt[i]) conts;
if(lcm(lc,lci[i]) <= m){
return true;
}
}
return false;
};
ll lo = 1, hi = m;
ll ans = -1;
while(lo <= hi){
ll mid = (lo+hi) >> 1;
if(ok(mid)){
ans = mid;
lo = mid+1;
}
else{
hi = mid-1;
}
}
ans++;
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<int> who(m+1, -1), freq(m+1), muls(m+1), id(m+1, -1);
for (int i = 0; i < n; ++i) {
who[a[i]] = i;
++freq[a[i]];
}
for (int i = 1; i <= m; ++i) for (int j = i; j <= m; j += i) {
muls[i] += freq[j];
if (freq[j]) id[i] = who[j];
}
int lo = 1, hi = m;
vector<int> reqd(n, 1);
while (lo < hi) {
int mid = (lo + hi + 1)/2;
// can I get everything <= mid?
long long LCM = 1;
for (int i = 1; i <= mid; ++i) {
if (muls[i] == 0) LCM = min(lcm(LCM, i), m+2ll);
if (muls[i] == 1) {
reqd[id[i]] = lcm(reqd[id[i]], i);
}
}
long long best = m+2;
for (int i = 0; i < n; ++i) {
long long cur = min(m+2ll, lcm(LCM, reqd[i]));
best = min(best, cur);
reqd[i] = 1;
}
if (best <= m) lo = mid;
else hi = mid-1;
}
cout << lo+1 << '\n';
}
}
might be because i use python since log2M should be quite close to root(M) and there was no AC submission of this problem in python XD
, ig i will try it a bit more using the logic in the editorial. Thanks 