Codeforces Round 641 Div 2

Problem A: Orac and Factors

Given two numbers N and K, apply f(N) to N exactly K times, where f(n) is the smallest positive divisor of n except 1.

Hint 1

• After applying f(N) for the first time, what property do you observe on the result?

Hint 2

• After applying f once, the resulting number will be even, why?
• If so, for the remaining (k - 1) times, 2 will be added to the result.

Time Complexity

$\mathcal{O}(\sqrt{N})$

Code

typedef long long ll;
void solve() {
    ll n, k;
    cin >> n >> k;

    ll factor = 2;
    ll maxFactor = sqrt(n);
    while (factor <= maxFactor) {
        if (n % factor == 0) { // smallest factor except 1
            break;
        }
        ++factor;
    }
    if (n % factor != 0) { // no factor in [2, sqrt(n)], so f(n) = n
        factor = n;
    }

    ll res = n + factor + (k - 1)*2; // 2 for the remaining (k - 1) times
    cout << res << endl;
}

---

Problem B: Orac and Models

Problem Statement:

• You are given an array arr containing n elements. Find the maximum beautiful subsequence length.
• A subsequence of arr is beautiful, if for every adjacent elements, with indices $i_{j}$ and $i_{j + 1}$ in the array, where $i_{j} < i_{j+1}$, $i_{j+1}$ is divisible by $i_{j}$ and $arr[i_{j}] < arr[i_{j+1}]$.

Hint 1

• What if you already knew the maximum subsequence length for all subarrays starting from 0 and ending till index (i-1)?
• How will you find the answer for subarray starting from 0 and ending at index (i) ?

Hint 2

• Well, what can be the previous index where you may pick an element in the subsequence? It must be a factor of i!
• So, for all factors of i, say j, which can be computed in sqrt(n) time, see if arr[j] < arr[i] holds, then update answer for arr[0...i] by maximum of ans[i], ans[j] + 1.
• See code for details.

Time Complexity

$\mathcal{O}(N \sqrt{N})$

Code

typedef long long ll;
void solve() {
    ll n;
    cin >> n;
    vector<ll> arr(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }

    vector<ll> dp(n + 1, 0);
    ll res = 1;
    for (int i = 1; i <= n; ++i) {
        ll cur = 1;
        for (int j = 1; j <= sqrt(i); ++j) {
            if (i % j == 0 && arr[j] < arr[i]) {
                cur = max(cur, 1 + dp[j]);
            }
            if (i % j == 0 && arr[i/j] < arr[i]) {
                cur = max(cur, 1 + dp[i/j]);
            }
        }
        dp[i] = cur;
        res = max(res, dp[i]);
    }
    cout << res << endl;
}

---

Problem C: Orac and LCM

Problem Statement:

• You are given an array arr containing n elements.
• Construct a multiset containing the lcm of all pairs of elements, say M.
• Find the gcd of all the elements in M.
• Note the constraints. So, $\mathcal{O}(n^2)$ solution won’t work.

Constraints:

• $$2 \leq N \leq 10^5$$
• $$1 \leq arr[i] \leq 2*10^5$$

Hints:

• Consider the prime factorization of two numbers a and b say:
  • For simplicity, considering k as the maximum no. of primes that we can get in the problem.
  • $$a = p_{1}^{n_{1}} p_{2}^{n_{2}} \cdots p_{k}^{n_{k}}$$
  • $$b = p_{1}^{m_{1}} p_{2}^{m_{2}} \cdots p_{k}^{m_{k}}$$
  • So, gcd(a, b) = $p_{1}^{min(n_{1}, m_{1})} p_{2}^{min(n_{2}, m_{2})} \cdots p_{k}^{min(n_{k}, m_{k})}$
  • And lcm(a, b) = $p_{1}^{max(n_{1}, m_{1})} p_{2}^{max(n_{2}, m_{2})} \cdots p_{k}^{max(n_{k}, m_{k})}$
• So, when we take lcm of two numbers, we get the maximum of the powers of the primes for each prime and multiply them.
• We need to get gcd of lcm of all pairs of the numbers.
• So, let’s just focus on one prime number, say 2, that might occur in factorization of the numbers.
  • Let’s assume there are 3 numbers and powers of 2 in their factorizations are: 1, 2, 3.
  • So, when you will consider all 3 choose 2, i.e. 3 pairs, the powers of 2 you will be getting in the lcms will be: max(1, 2), max(1, 3), max(2, 3) = 2, 3, 3.
  • So, in the gcd, the power of 2 will be 2, since we need to take the minimum one in gcd.
  • Can you try building up some observation for more numbers and given the power of the prime?
  • Will the power be the second minimum one? Always? Or in some particular case? When the prime is present in factorization of all N numbers.
• Consider a case when a particular prime is not available in atleast 2 numbers, so multiplying those 2 numbers you get no power of that prime. Thus, it won’t come in gcd also.
• Consider one more example:
  • There are 5 numbers and powers of 2 are: 0, 3, 4, 4, 5.
  • Here, also when computing lcm of pairs, the min power you will get will be 3, i.e. second minimum.
  • Now, also thinking about complexity of solution, you can’t see for every prime if it divides every number, That will cost $\mathcal{O}(primes \ below\ 2*10^5 \times N)$.
  • So, we will update the minimum powers as we factorize the number, using the shortest prime factor approach (see some articles on it) to do prime factorization in $\mathcal{O}(log N)$.
  • Please see the code for more details.

Code

typedef long long ll;
const int MAXN = 2e5;
// stores smallest prime factor for every number
ll spf[MAXN];
// stores the minimum power of a prime occurring in any factorization
ll min1[MAXN];
// stores the second minimum power of a prime occurring in any factorization
ll min2[MAXN];
// Calculating SPF (Smallest Prime Factor) for every number till MAXN.
void sieve();
// A O(log n) function returning prime factorization
// by dividing by smallest prime factor at every step
// returns the pairs of {prime, its power}
vector<pair<int, int>> getFactorization(int x);

void solve() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (auto &a : arr) {
        cin >> a;
    }

    sieve();
    memset(min1, -1, sizeof(min1));
    memset(min2, -1, sizeof(min2));

    vector<int> cnt(MAXN, 0); // count of the numbers in which a particular prime appears in the factorization
    for (int i = 0; i < n; ++i) {
        int x = arr[i];
        vector<pair<int, int>> fact = getFactorization(x); // {prime, its power} pairs
        for (auto ff : fact) {
            int p = ff.first; // prime
            int c = ff.second; // power of prime occurring in factorization

            // update first min and second min for the given power
            if (min1[p] == -1) {
                min1[p] = c;
            } else if (min2[p] == -1) {
                int m = min1[p];
                if (c <= m) {
                    min1[p] = c;
                    min2[p] = m;
                } else {
                    min1[p] = m;
                    min2[p] = c;
                }
            } else {
                int m1 = min1[p];
                int m2 = min2[p];
                if (c <= m1) {
                    min1[p] = c;
                    min2[p] = m1;
                } else if (c <= m2) {
                    min2[p] = m2;
                }
            }
            ++cnt[p];
        }
    }

    ll res = 1;
    for (int i = 2; i < MAXN; ++i) {
        if (cnt[i] == n) { // prime occurring in all the numbers, consider second min power
            res *= pow(1ll * i, min2[i]);
        } else if (cnt[i] == n - 1) { // prime occuring in n - 1 numbers, consider first min power
            res *= pow(1ll * i, min1[i]);
        }
    }
    cout << res << endl;
}


void sieve() {
    spf[1] = 1;
    for (int i = 2; i < MAXN; i++)

    // marking smallest prime factor for every
    // number to be itself.
    spf[i] = i;

    // separately marking spf for every even
    // number as 2
    for (int i = 4; i < MAXN; i += 2) spf[i] = 2;

    for (int i = 3; i * i < MAXN; i++) {
        // checking if i is prime
        if (spf[i] == i) {
        // marking SPF for all numbers divisible by i
        for (int j = i * i; j < MAXN; j += i)
            // marking spf[j] if it is not
            // previously marked
            if (spf[j] == j) spf[j] = i;
        }
    }
}

// A O(log n) function returning prime factorization
// by dividing by smallest prime factor at every step
// returns the pairs of {prime, its power}
vector<pair<int, int>> getFactorization(int x) {
    vector<pair<int, int>> ret;
    while (x != 1) {
        int cur = spf[x];
        int cnt = 0;
        while (x && spf[x] == cur) {
            ++cnt;
            x = x / spf[x];
        }
        ret.push_back({cur, cnt});
    }
    return ret;
}

---