FO7's blog

Wonderful DP problem
By FO7, history, 16 months ago, In English

Given a sequence of integers ,find a subsequence of largest length such that in the subsequence adjacent elements are not equal at most k times. n<=1e3,k<=n<=1e3 .. Any Hints or ideas?

upd: Thank You everyone. Final solution:

suppose u are at index i.say p denotes index of prev elements.say given array is a ; dp[x][y]=max length when u have explored only till x index and atmost y non equla adjacent pairs.

brute force dp(O(n3)):- for(int p=0;p<i;p++) { for(int j=0;j<k;j++) {int a=-1,b=-1; if(a[i]==a[p]) a=dp[p][j]+1; else if(j>=1) b=dp[p][j-1]+1;

dp[i][j]=max{dp[i][j],a,b} }

}

Very easy to optimise: we want just max out of dp[0 ....... i-1][j] and max out of dp[0...... i-1][j-1] using map[value][j].I have tried to be accurate .Still U find some thing to be correct pls inform.

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (23)
| Write comment?
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

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

Can you give me link of problem?

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

    I don't have the link as it is from interview round(offline)

    → Reply
»
16 months ago, # |
← Rev. 4   Vote: I like it +6 Vote: I do not like it

Maybe this will work:

Let F(i, j) be the largest length of a subsequence ending at the i-th index with at most j not equal adjacent elements.

F(i, j) = max( F(s, j), F(s, j-(a[i] != a[s])) + 1) , for 0 <= s < i.

Time complexity O(n^3).

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

Longest subsequence with at most $$$k$$$ non-equalling elements?

$$$dp_{i,p,j} = $$$ Longest subsequence with $$$k$$$ non-equalling elements, ending with element $$$p$$$

$$$dp_{i,p,j} = max(dp_{i,p,j}, dp_{i-1,p,j})$$$

$$$dp_{i,a_i,j} = max(dp_{i,a_i,j}, dp_{i-1,p,j-(a_i \neq p)}+1))$$$

Time Complexity: $$$O(n^3)$$$

Memory Complexity: can be optimized to be $$$O(n^2)$$$, probably $$$O(n)$$$

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

    As far what u have written seems wrong.pls explain if i am wrong

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

My idea is something along the line of this:

First, compress the array such that if it has $$$m$$$ distinct elements, all the elements are numbered from $$$0$$$ to $$$m-1$$$. Let $$$dp_{i,j}$$$ be longest subsequence such that the last element is $$$i$$$ and there are at most $$$j$$$ non equal pairs of adjacent element. Ofc, initially $$$dp_{i,j}=0$$$ for all $$$0 \leq i \leq m-1$$$ and $$$0 \leq j \leq k$$$.

Iterate the array from the $$$1$$$-st element to the $$$n$$$-th element and at the $$$i$$$-th transition, it goes like this:

  • $$$dp_{a_i,0} := dp_{a_i,0}+1$$$
  • $$$dp_{a_i,j} := \max (dp_{a_i,j},\max(dp_{c,j-1}))+1$$$ for $$$1 \leq j \leq k$$$ and $$$0 \leq c \leq m-1$$$

The complexity of this would be $$$O(nmk)$$$, but I think it could be either optimized to $$$O(nk \log m)$$$ or $$$O(nk)$$$. Also note that this $$$dp$$$ will only return the length of the longest subsequence. If you want to extract the subsequence, put the index information of previous $$$dp$$$ that gives maximum value during transition and then after all the elements have been processed, work backwards from any $$$dp$$$ with largest value to find the subsequence.

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

I think we can solve with simple recursion + memoization.we will track previous element and count of adjacent equal element with help of previously choosen element.Sorry if bad explanation.

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

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

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

First let's split the array into continuous segments of equal valuse so insted of a1,a2..,an we will have (a1=a2=...=ai)(ai+1=ai+2=....).....(ak=ak+1=..=an) we can see that a solution picking the first element from each group will have 0 pairs o adjacent elements equal (since adjacent groups have diffrent vaues) and then we can simply add any k elements that are not first in their grup .This is optimal because the answer will be number of grupos +k .Our answer (the lenght) will be number of diffrent adjacent pairs(<=number of groups)+ number of equaladjacent pairs(<=k),so our solution min(n, whit number of groups +k) lenght will be optimal.This can be easly solved in O(n).

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    Simple implementation

    #include <iostream>

using namespace std;
int v[1005];
int main()
{
    int n,i,k,cnt=0;
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
        if(v[i]!=v[i-1] ||i==1)
        {
            cnt++;
        }
    }
    cout<<min(cnt+k,n);
    return 0;
}
    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      failing for test case [1,1,2,3,2,1] & k=2 answer should be 5 [1,1,2,2,1] giving 6 crt me if i am wrong :)

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

        The from 5 weeks ago was very bad at Cp and read the statement wrong (i tought it was at most k pairs of equal adjacent elemnts).

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

FO7 can you kindly provide the optimized code

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

Time Complexity O(n*k), tested with naive O(n^2*k) dp. 

arr=[1,1,2,3,2,1]
k=2

dp={i:[0,set(),Counter()] for i in range(k+1)}

for i in arr:
    prev=0
    for j in range(k+1):

        cur=max(prev+1,(dp[j][0]+1)*(i in dp[j][1]),dp[j][2][i]+1)       

        prev,dp[j][2][i]=dp[j][0],cur

        if dp[j][0]<cur:
           dp[j][:]=[cur,set(]

        if cur==dp[j][0]: 
           dp[j][1].add(i)    

return dp[k][0]
→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can You please explain your apporach, please its working no doubt but I want to know how you have thinked, and how its working, can you please tell

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

Here is my attempt to the question.

int main() { int n,k; cin>>n>>k; vectorvalues; for(int i=0;i<n;i++) { int x; cin>>x; values.push_back(x); } vector<vector>dp(n+1,vector(k+1,0)); unordered_map<int,unordered_map<int,int>>mp; unordered_map<int,int>mp1; for(int i=0;i<=k;i++) dp[0][i]=1;

for(int i=0;i<n;i++)
{
    unordered_map<int,int>mp2=mp1;
    for(int j=0;j<=k;j++)
    {   
        //The length of the longest subsequence ending at some index less than i and with the value values[i] with atmost j adjacent unequal values.
        dp[i][j]  = mp[values[i]][j]+1;
        if(j>0)
            dp[i][j] = max(dp[i][j],mp2[j-1]+1); //Pick the maximum of all the values at index from 0 to i-1 with atmost j-1 adjacent unequal numbers.
        //update the maximum length for the current value with atmost j adjacent unequal numbers.
        mp[values[i]][j] = max(mp[values[i]][j],dp[i][j]);
        //update maximum length for all sequences ending at 0 to j with atmost j adjacent unequal characters
        mp1[j] = max(mp2[j],dp[i][j]);
    }

}
cout<<dp[n-1][k]<<endl;

}

→ Reply