godmodegod's blog

Help this newbie!!
By godmodegod, 2 days ago, In English

A chain is a sequence of positive integers A1, A2, A3, ..., An such that Ai+1 divides Ai. (In other words, A1 is a divisor of A2, A2 is a divisor of A3, and so on.)

The length of a chain is the number of elements in the sequence.

Given N elements, you need to find a chain of maximum length using a subset of the given elements.

1<=N<=1e6 1<=a[i]<=1e6

Now, you can sort the array and track gcd (LIS like approach), but how do you come up with a solution which adheres to the time limit?

N = 5 array = 4 2 5 80 4

ans = 4, i.e. [2,4,4,80]

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

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Did you try by yourself?

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007

int LIS(unsigned int ind, vector<int>&a, int gg) {
	if (ind == a.size())return 0;
	int take = 0;
	int ngg = __gcd(gg, a[ind]);
	if (ngg != 1)take = max(LIS(ind + 1, a, ngg) + 1, take);

	int nottake = LIS(ind + 1, a, gg);
	return max(take, nottake);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int n;
	cin >> n;
	vector<int> a(n);

	for (int i = 0; i < n; ++i)cin >> a[i];
	sort(a.begin(), a.end());

	int ans = 0;

	for (int i = 0; i < n; ++i) {
		ans = max(ans, LIS(i, a, 0));
	}

	cout << ans << endl;



	return 0;
}

    Obvious TLE.

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

      would you please share the problem link?

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

      Btw this solution is completely wrong.

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

        sort -> apply DP

        I will lyk if I manage to implement it.

        → Reply
        • »
          »
          »
          »
          »
          38 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it 
          #include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include "Templates/printContainer.h"
#endif
#define dbg(x) cout << #x << " = " << x << endl;
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ins insert
#define INF 1000000000
#define pii pair<int,int>
#define EPS 1e-9
#define Endl "\n"
#define fst first
#define snd second
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define sqr(a) (a)*(a)
#define log(b,n) (log2(n)/(log2(b))) //logBase_b_(n)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define _hello cout<<"hello\n";
#define _pow2(k) 1LL<<k
const long long mod=1e9+7;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
using namespace std;
bool _areEqual(double x,double y)
{
    return (abs(x-y)<EPS) ? true : false;
}

string _bin(int decimal)
{
    //prints n bit integer
    int n=8;
    //you can change according to ur need
    string bin;
    for(int i=0;i<n;i++)
    {
        bin.pb(((decimal&(1<<i))>>i)+'0');
    }
    reverse(bin.begin(),bin.end());
    return bin;
}
bool isPrime(ll n)
{
    if(n==2) return true;
    int lim=sqrt(n)+1;
    for(int i=3; i<=lim; i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}

template <typename T> void inputContainer(std::vector<T>& v)       { for(auto &it:v) cin>>it; }
template <typename T> void base1InputContainer(std::vector<T>& v)  { int n=v.size()-1; for(int i=1;i<=n;i++)cin>>v[i]; }
                      void printVector(std::vector<int>& v)        { for(auto it:v)cout<<it<<" "; cout<<endl; }
                      void base1printContainer(std::vector<int>& v){ int n=v.size()-1; for(int i=1;i<=n;i++)cout<<v[i]<<" ";cout<<endl; }
class DSU
{
public:
    vector<int> rank,parent;
    DSU(int n)
    {
        for(int i=0; i<=n; i++)
            rank.pb(0);
        //parent.resize(n);
        for(int i=0; i<=n; i++)
            parent.pb(i);
    }
    int _findParent(int u)
    {
        if(u==parent[u]) return u;
        //else
        return parent[u]=_findParent(parent[u]);
    }
    void _union(int u,int v)
    {
        int pu=parent[u];
        int pv=parent[v];
        if(pu==pv) return;
        //else
        if(rank[pu]<rank[pv])
        {
            parent[pu]=pv;
        }
        else if(rank[pu]>rank[pv])
        {
            parent[pv]=pu;
        }
        else
        {
            parent[pu]=pv;
            ++rank[pv];
        }
    }
};

class edge
{
public:
    int u,v,w;
    edge(int u,int v,int w)
    {
        this->u=u;
        this->v=v;
        this->w=w;
    }
    bool operator<(const edge& other) const
    {
        return w>other.w;
    }

};

int dp[1000000];
int n;
int f(vector<int>& v,int i,int lastTaken)
{
    if(i==-1) return 0;
    if(dp[i]!=-1) return dp[i];
    int takeIt;
    if(v[i]%lastTaken==0)
        takeIt=1+f(v,i-1,v[i]);
    else takeIt=INT_MIN;
    int dontTakeIt=f(v,i-1,lastTaken);
    return dp[i]=max(takeIt,dontTakeIt);
}
void solve()
{
    memset(dp,-1,sizeof(dp));
    cin>>n;
    vector<int> a(n);
    for(auto &it:a)
        cin>>it;
    sort(rall(a));
    cout<<f(a,n-1,1)<<endl;
	//comment out fast_io if I/O related problem occurs
}
int main() {
    fast_io;
    int t = 1;
    cin >> t;
     for (int i = 1; i <= t; i++)
         solve();
}

//graphs -->vector<int> adj[n+1]; n=# of vertices
/*
taking graph input
for(int i=1;i<=n;i++)
{
    cin>>u>>v;
    adj[u].pb(v);
    adj[v].pb(u);//ONLY IF UNDIRECTED GRAPH
}
*/

          This might work

          → Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't know if this will help, but the number of distinct elements in the final subset will be < 20. Because:

Spoiler

Edit: it's wrong, I misunderstood the problem at first.

→ Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

for every index i and for every prime p, draw an edge from i to the smallest index j such that that A_j is divisible by p*A_i. This creates a DAG and then you can DP on this to find the longest path. I think you can do this N log N.

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

    Could you implement it please, thanks!!!

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

    Won't this TLE? N <= 10^6 and there are roughly 70K primes less than 500000.

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

      For A_i there are only MAX_N/A_i numbers you can multiply by (even less primes), so if you combine identical values that bounds the complexity to the harmonic series (N/1 + N/2 + ...) or N log N.

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

      Oh shoot primes don't even matter, there are very few possible edges (by the same harmonic series argument) so you can just draw all edges explicitly and then find the answer.

      → Reply
  • »
    »
    47 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    void solve()
{

    int n, ans = 0; cin >> n;
    vector<int> a(n);

    for (auto &i : a) cin >> i;
    int mx = *max_element(a.begin(), a.end());

    vector<int> dp(mx + 1, 0);
    for (auto &i : a) dp[i]++;

    for (int i = mx; i >= 1; i--) {

        if (!dp[i]) continue;
        int val = dp[i];

        for (int j = 2 * i; j <= mx; j += i)
            dp[i] = max(dp[i], val + dp[j]);

        ans = max(ans, dp[i]);

    }

    cout << ans << "\n";
}

    Won't this be enough?

    → Reply
  • »
    »
    38 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    sir will this work? I have very little knowledge so asking

    #include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include "Templates/printContainer.h"
#endif
#define dbg(x) cout << #x << " = " << x << endl;
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ins insert
#define INF 1000000000
#define pii pair<int,int>
#define EPS 1e-9
#define Endl "\n"
#define fst first
#define snd second
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define sqr(a) (a)*(a)
#define log(b,n) (log2(n)/(log2(b))) //logBase_b_(n)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define _hello cout<<"hello\n";
#define _pow2(k) 1LL<<k
const long long mod=1e9+7;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
using namespace std;
bool _areEqual(double x,double y)
{
    return (abs(x-y)<EPS) ? true : false;
}

string _bin(int decimal)
{
    //prints n bit integer
    int n=8;
    //you can change according to ur need
    string bin;
    for(int i=0;i<n;i++)
    {
        bin.pb(((decimal&(1<<i))>>i)+'0');
    }
    reverse(bin.begin(),bin.end());
    return bin;
}
bool isPrime(ll n)
{
    if(n==2) return true;
    int lim=sqrt(n)+1;
    for(int i=3; i<=lim; i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}

template <typename T> void inputContainer(std::vector<T>& v)       { for(auto &it:v) cin>>it; }
template <typename T> void base1InputContainer(std::vector<T>& v)  { int n=v.size()-1; for(int i=1;i<=n;i++)cin>>v[i]; }
                      void printVector(std::vector<int>& v)        { for(auto it:v)cout<<it<<" "; cout<<endl; }
                      void base1printContainer(std::vector<int>& v){ int n=v.size()-1; for(int i=1;i<=n;i++)cout<<v[i]<<" ";cout<<endl; }
class DSU
{
public:
    vector<int> rank,parent;
    DSU(int n)
    {
        for(int i=0; i<=n; i++)
            rank.pb(0);
        //parent.resize(n);
        for(int i=0; i<=n; i++)
            parent.pb(i);
    }
    int _findParent(int u)
    {
        if(u==parent[u]) return u;
        //else
        return parent[u]=_findParent(parent[u]);
    }
    void _union(int u,int v)
    {
        int pu=parent[u];
        int pv=parent[v];
        if(pu==pv) return;
        //else
        if(rank[pu]<rank[pv])
        {
            parent[pu]=pv;
        }
        else if(rank[pu]>rank[pv])
        {
            parent[pv]=pu;
        }
        else
        {
            parent[pu]=pv;
            ++rank[pv];
        }
    }
};

class edge
{
public:
    int u,v,w;
    edge(int u,int v,int w)
    {
        this->u=u;
        this->v=v;
        this->w=w;
    }
    bool operator<(const edge& other) const
    {
        return w>other.w;
    }

};

int dp[1000000];
int n;
int f(vector<int>& v,int i,int lastTaken)
{
    if(i==-1) return 0;
    if(dp[i]!=-1) return dp[i];
    int takeIt;
    if(v[i]%lastTaken==0)
        takeIt=1+f(v,i-1,v[i]);
    else takeIt=INT_MIN;
    int dontTakeIt=f(v,i-1,lastTaken);
    return dp[i]=max(takeIt,dontTakeIt);
}
void solve()
{
    memset(dp,-1,sizeof(dp));
    cin>>n;
    vector<int> a(n);
    for(auto &it:a)
        cin>>it;
    sort(rall(a));
    cout<<f(a,n-1,1)<<endl;
	//comment out fast_io if I/O related problem occurs
}
int main() {
    fast_io;
    int t = 1;
    cin >> t;
     for (int i = 1; i <= t; i++)
         solve();
}

//graphs -->vector<int> adj[n+1]; n=# of vertices
/*
taking graph input
for(int i=1;i<=n;i++)
{
    cin>>u>>v;
    adj[u].pb(v);
    adj[v].pb(u);//ONLY IF UNDIRECTED GRAPH
}
*/
    → Reply
»
40 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

dp problem

→ Reply