aeonary's blog

LIS with condition problem
By aeonary, history, 17 months ago, In English

Please help me. The statement is: Give an array A with n integers(n <= 10^5). Your task is to find the longest increasing subsequence that gcd of 2 consecutive elements is > 1.

Example:

input

5

2 3 4 6 9

output

4

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think this is solvable in n.sqrt(max(Ai)).logn.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think sqrt(maxAi) part can be even reduced to <= 30 since each number can have at most <= 20 unique prime factors if Ai <= 10^9

    → Reply
»
17 months ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

Heyy man, the general idea is shown below:

#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <algorithm>

using namespace std;

vector<int> factorize(int n) {
    vector<int> factors;
    int s = 2;
    while (s * s <= n) {
        if (n % s == 0) factors.push_back(s);
        while (n % s == 0) n /= s;
        s++;
    }
    if (n > 1) factors.push_back(n);
    return factors;
}

int brute(vector<int> v) {
    vector<int> dp(v.size(), 0);
    int ans = 0;
    for (int i = 0; i < v.size(); ++i) {
        dp[i] = v[i] > 1;
        for (int j = 0; j < i; ++j) {
            if (v[j] < v[i] && gcd(v[j], v[i]) > 1) {
                dp[i] = max(dp[i], dp[j] + 1);
                ans = max(dp[i], ans);
            }
        }
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    int mx = 0;
    map<int, vector<int>> lis_map;
    vector<int> a;
    while (n--) {
        int num;
        cin >> num;
        a.push_back(num);
        // map from prime to lis
        auto factors = factorize(num);
        int mx_pos = 0;
        for (int prime: factors) {
            auto & lis = lis_map[prime];
            int sz = upper_bound(lis.begin(), lis.end(), num) - lis.begin();
            mx_pos = max(mx_pos, sz + 1);
            if (lis.size() == sz) {
                lis.push_back(num);
            } else {
                lis[sz] = min(lis[sz], num);
            }
        }
        mx = max(mx, mx_pos);
        for (int prime: factors) {
            auto & lis = lis_map[prime];
            int pos = upper_bound(lis.begin(), lis.end(), num) - lis.begin();

            //TODO: you can compress the LIS array without doing this iteration using some tricks
            while (pos < mx_pos) {
                if (pos == lis.size()) lis.push_back(num);
                else
                lis[pos] = min(lis[pos], num);
                ++pos;
            }
        }
    }
    cout << "algo " << mx << endl;
    cout << "brute " << brute(a) << endl;
    return 0;
}
→ Reply