CDEC2208- Editorial

PROBLEM LINK:

Smart Solution to Avoid Collision

Author: Priyanshu Trivedi
Tester: Tushar Gupta
Editorialist: Priyanshu Trivedi

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

DP, Longest Common Subsequence

PROBLEM:

Given two arrays of pairwise distinct strings find the maximum numbers of strings remaining after deleting some (or possibly none) strings from either of the arrays.

QUICK EXPLANATION:

Common and in same order hints for LCS, it’s a direct question of longest common subsequence but it fails for the n^2 approach if n>1000 so for n being around 10^5 we need to find an efficient algorithm.

EXPLANATION:

This can be converted to a lis(longest increasing subsequence) question by maintaining an array which contains the index of the common elements in one array and then find its lis to find the answers. As the strings in an array are pairwise distinct we can use binary search for finding the index of common strings. Hence reducing the overall complexity to O(n*log(n)). This can be either implemented through vector of pair of map.

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>

using namespace std;

using ll=long long;

ll lis(vector a)

{

ll n,INF,i,j,ans;

n=a.size();

INF=1e9;

vector<int> d(n+1, INF);

d[0]=-INF;

for (i=0;i<n;i++)

{

    j=upper_bound(d.begin(), d.end(),a[i])-d.begin();

    if (d[j-1]<a[i] && a[i]<d[j])

    d[j] = a[i];

}

ans=0;

for (i=0;i<=n;i++)

{

    if (d[i]<INF)

    ans=i;

}

return ans;

}

int main(void)

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

ll t,n,m,i,k;

cin>>t;

string s;

while(t--)

{

    vector<pair<string,ll>>vp;

    cin>>n>>m;

    vector<string>a,b;

    for(i=0;i<n;i++)

    {

        cin>>s;

        a.push_back(s);

    }

    for(i=0;i<m;i++)

    {

        cin>>s;

        b.push_back(s);

    }

    vector<ll>pos,common_project_pos;

    for(i=0;i<n;i++)

    {

        cin>>s;

        a.push_back(s);

    }

    for(i=0;i<m;i++)

    {

        cin>>s;

        vp.push_back({s,i});

    }

    sort(vp.begin(),vp.end());

    for(auto x:vp)

    {

        b.push_back(x.first);

        pos.push_back(x.second);

    }

    for(i=0;i<n;i++)

    {

        if(binary_search(b.begin(),b.end(),a[i]))

        {

            k=pos[(lower_bound(b.begin(),b.end(),a[i])-b.begin())];

            common_project_pos.push_back(k);

        }

    }

    cout<<lis(common_project_pos)<<"\n";

}

return 0;

}