MATHOLOGY - Editorial

editorial
, , , , , , , ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Segment Tree, Greedy, Square Root Decomposition

PROBLEM:

Given an array of N positive integers. You have to answer Q queries, each requiring you to determine the maximum possible GCD over all subsequences (of length >1) of a specified range of the array.

EXPLANATION:

Hint 1

Observe that it is sufficient to select only 2 elements in the specified range to achieve the maximum possible gcd.

Why?

It is known that:

\gcd(a,b)\ge \gcd(\gcd(a,b),c)=\gcd(a,b,c)

Therefore, since the gcd never increases on adding another element, it makes sense to select the least possible number of elements.

Hint 2

Armed with this observation, write a naive bruteforce to solve the problem in O(N^2) per query.

Solution

For each element in the range, compute the gcd with every other element in the range. The answer is then the maximum over these computed values.

This is too slow to pass the subtasks apart from the 1^{st} one.

Hint 3

Let d(x) represent the number of divisors of positive integer x. Then, for a fixed a, there are exactly d(a) possible values of \gcd(a,b) over all valid b.

Thus, instead of iterating over every pair of elements, can you iterate on the divisors of every element (in the range) to calculate the maximum possible gcd?

Solution

Let D_x represent the set of divisors of integer x.

Let S be the multiset of \{D_{A_l}, D_{A_{l+1}},\dots,D_{A_r}\}. Then, it is easily verifiable that the maximum possible gcd is the largest number in S that occurs more than once.

Precomputing divisors for all A_i can be done in \approx O(N\sqrt{\max A_i}). Then, the above method can determine the solution in O(N\cdot d) per query, where d\le 100 represents the maximum number of divisors (for the given constraints).

This is an improvement to our naive bruteforce, but will only pass the first two subtasks.

Hint 3

Offline (aka, no updates) range queries is a significant pointer towards sorting the queries first and then solving.

Solution for subtask 3; Unrelated to complete solution

Standard application of Mo’s Algorithm. The time complexity is O((N+Q)\cdot d\cdot\sqrt N), which works for the first 3 subtasks.

Solution

Start by sorting all queries in increasing order of their right (R value) bound.

We iterate over array A from 1 to N. Let i represent the current index we are processing. Also, let v_x represent the maximum gcd over all pairs of elements in the subarray A[x..i]. Then, answer to any query of the form [l, i] equals v_l.
Initially, v_x is 0 for all x.

Here’s how we can efficiently update array v in each iteration -
Traverse over all divisors of A_i - call the current divisor d. Consider the largest p<i such that d\mid A_p. Then, update v_x = \max(v_x,d) for all x\le p.
It is easy to see (by recursion) that at the end of the above operation, the updated array matches the aforementioned definition of v.

How do we implement this?
The value of p can be efficiently determined in O(1) by maintaining a sliding window during our iteration. Range updates (and point queries) to v can be done in O(\log N) using a segment tree with lazy propagation.

The total time complexity is therefore:

O(N\cdot d\cdot \log N + Q\cdot\log N)

This however, TLE’s on exactly one test in the last subtask!
To remedy this, observe that the number of updates is a magnitude more than the number of queries. Thus, we could switch to a data structure with faster updates and slightly slower queries - Square Root Decomposition.
For this, we must appropriately convert our operations to be point update (giving O(1) per update) and range query (with O(\sqrt N) per query), which is left to the reader as a simple exercise.

TIME COMPLEXITY:

Precomputing divisors of each integer takes O(N\sqrt{\max A_i}).

Sorting the queries takes O(Q\log Q). Building array v for each index i takes O(d), where d is the number of divisors of A_i. Determining the answer to each query takes O(\sqrt N) with range queries. The total time complexity is therefore

O(N\cdot d + Q\sqrt N)

per test case.

SOLUTIONS:

Editorialist’s solution can be found TBD

2 Likes
2

Editorialist’s solution link is not working , kindly check it once !!

3

It’ll be updated in some time.

4

Still not updated.

5

Can anyone please explain why my solution is failing?
https://www.codechef.com/viewsolution/62514092

6

Hey beruboiv :smiling_face:
I think your segment tree implementation have an error , I wrote the code with same logic but with Fenwick Tree so you can go through it :slight_smile: .

#include <iostream>
#include<bits/stdc++.h>
#include<deque>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<stdio.h>
#include<bitset>
#include<string>
#include<vector>
#include<unordered_map>
#include<queue>
#include<set>
#include<fstream>
#include<map>
#define int long long int
#define ld long double
#define pi 3.1415926535897932384626433832795028841971
#define MOD 1000000007
#define MOD1 998244353
#define print(vec) for (int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << "\n";
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int inf = 1e18;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#ifdef __SIZEOF_INT128__
ostream& operator << (ostream &os, __int128 const& value) {
    static char buffer[64];
    int index = 0;
    __uint128_t T = (value < 0) ? (-(value + 1)) + __uint128_t(1) : value;
    if (value < 0)
        os << '-';
    else if (T == 0)
        return os << '0';
    for (; T > 0; ++index) {
        buffer[index] = static_cast<char>('0' + (T % 10));
        T /= 10;
    }
    while (index > 0)
        os << buffer[--index];
    return os;
}
istream& operator >> (istream& is, __int128& T) {
    static char buffer[64];
    is >> buffer;
    size_t len = strlen(buffer), index = 0;
    T = 0; int mul = 1;
    if (buffer[index] == '-')
        ++index, mul *= -1;
    for (; index < len; ++index)
        T = T * 10 + static_cast<int>(buffer[index] - '0');
    T *= mul;
    return is;
}
#endif
int add(long long a, long long b) {return ((a % MOD) + (b % MOD)) % MOD;}
int subtract(long long a, long long b) {return ((a % MOD) - (b % MOD)) % MOD;}
int mult(long long a, long long b) {return ((a % MOD) * (b % MOD)) % MOD;}
int add1(long long a, long long b) {return ((a % MOD1) + (b % MOD1)) % MOD1;}
int subtract1(long long a, long long b) {return ((a % MOD1) - (b % MOD1)) % MOD1;}
int mult1(long long a, long long b) {return ((a % MOD1) * (b % MOD1)) % MOD1;}
int expo(int a, int b, int mod) {
    int res = 1;
    while (b > 0)
    {   if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
        b = b >> 1;
    } return res;
}
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int mminvprime(int a, int b) {
    return expo(a, b, b + 2);
}
const int maxn = 1e5 + 12;
vector<int> a, d[maxn], sofar(maxn);
int n;
vector<int> c;
void update(int ind, int val)
{
    while (ind > 0)
    {
        c[ind] = max(c[ind], val);
        ind = ind - (ind & (-ind));
    }
}
int query(int ind)
{
    int s = 0;
    while (ind <= n)
    {
        s = max(s, c[ind]);
        ind = ind + (ind & (-ind));
    }
    return s;
}
int32_t main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    for (int i = 1; i < maxn; ++i)
    {
        sofar[i] = 0;
        for (int j = i; j < maxn; j += i) d[j].push_back(i);
    }
    while (tt--)
    {
        int q;
        cin >> n >> q;
        a.assign(n + 1, 0);
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
        }
        c.assign(n + 1, 0);
        vector<pair<int, int>> qrs[n + 1];
        for (int i = 1; i <= q; ++i)
        {
            int l, r;
            cin >> l >> r;
            qrs[r].push_back({l, i});
        }
        vector<int> ans(q+1);
        for (int i = 1; i <= n; ++i)
        {
            for (auto x : d[a[i]])
            {
                if (sofar[x]) update(sofar[x], x);
                sofar[x] = i;
            }
            for (auto [l, ind] : qrs[i])
            {
                ans[ind] = query(l);
            }
        }
        for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
        for (int i = 1; i <= n; ++i)
        {
            for (auto x : d[a[i]]) sofar[x] = 0;
        }
    }
    return 0;
}
1 Like
7

Thanks @jatin0308_adm ,
I understood my mistake, it was a fault in segment tree logic only.
But now I am getting a TLE, is there a way to remedy this?
https://www.codechef.com/viewsolution/62739656

8

Hey @beruboiv :smiling_face: ,
I think this is due to tight constraints and you are logic is not the good fit so try reduce the number of operations(I think this is due to implementation of 2 seg trees).

1 Like
9

Thanks! I will look into that.