# HackerEarth Select the subset problem solution

In this HackerEarth Select the subset problem solution You are given an array A and B of size N.

You must select a subset of indices from 1 to N such that for any pair of indices (x,y), x != y in the subset one of the following conditions holds true:
1. A[x] < A[y] and B[x] < B[y]
2. A[x] > A[y] and B[x] > B[y]
3. A[x] = A[y] and B[x] != B[y]

Your task is to determine the largest possible size of a subset that satisfies the provided conditions.

## HackerEarth Select the subset problem solution.

`#include "bits/stdc++.h"#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)#define time__(d) \    for ( \        auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \        blockTime.second; \        debug("%s: %d ms\n", d, (int)chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \    )#ifdef LOCAL#include "pprint.hpp"#endif#define endl '\n';#define pb push_back#define mod 1000000007#define ll long long int#define prn(x) cerr<<x<<endl;#define all(x) x.begin(),x.end()using namespace std;#define test_case 1int lis(vector<int> &v){    int l=1;    vector<int> Lis;    Lis.pb(v[0]);    for(int i=1;i<(int)v.size();++i){        if(v[i]>Lis[l-1]){            Lis.pb(v[i]);            ++l;        }        else{            int pos = lower_bound(all(Lis),v[i])-Lis.begin();            Lis[pos]=v[i];        }    }    return l;}void solution(){    int n;    cin>>n;    assert(n>=1 && n<=100000);    vector<int> a(n+1),b(n+1);    for(int i=1;i<=n;++i){        cin>>a[i];        assert(a[i]>=1 && a[i]<=1000000000);    }    for(int i=1;i<=n;++i){        cin>>b[i];        assert(b[i]>=1 && b[i]<=1000000000);    }    vector<pair<int,int>> v;    for(int i=1;i<=n;++i){        v.pb({a[i],b[i]});    }    sort(all(v));    vector<int> vv;    for(auto x:v)        vv.pb(x.second);    cout<<lis(vv)<<endl;}int main(int argc, char *argv[]){    int t=1;    if(test_case)        cin>>t;    assert(1 <= t and t <= 10);        while(t--){            solution();        }    return 0;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAX_N = 1e5 + 14;template<class cmp>struct LS {    vector<int> v;    vector<pair<int, int> > his;    void add(int x) {        int p = upper_bound(v.begin(), v.end(), x - 1, cmp()) - v.begin();        if (p == v.size()) {            his.push_back({-1, 0});            v.push_back(x);        }        else {            his.push_back({p, v[p]});            v[p] = x;        }    }    void swap(LS<cmp> &od) { od.v.swap(v); }    void merge(LS<cmp> &od) {        if (od.v.size() > v.size())            v.swap(od.v);        for (int i = 0; i < od.v.size(); i++)            if (cmp()(od.v[i], v[i])) v[i] = od.v[i];    }    void undo() {        assert(his.size());        if (his.back().first == -1)            v.pop_back();        else            v[his.back().first] = his.back().second;        his.pop_back();    }};typedef LS<less<int> > Lis;typedef LS<greater<int> > Lds;int main() {    ios::sync_with_stdio(0), cin.tie(0);    int t;    cin >> t;    while (t--) {        int n;        cin >> n;        pair<int, int> a[n];        for (int i = 0; i < n; ++i)            cin >> a[i].first;        for (int i = 0; i < n; ++i)            cin >> a[i].second;        sort(a, a + n);        Lis lis;        for (int i = 0; i < n; ++i)            lis.add(a[i].second);        cout << lis.v.size() << '\n';    }}`