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


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 1

int 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';
}
}