![](/style/images/good.png)
1
![](/style/images/bad.png)
LIS with condition problem
source link: https://codeforces.com/blog/entry/109462
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LIS with condition problem
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
2 3 4 6 9
output
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;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK