Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Select the subset problem solution

YASH PAL, 31 July 2024
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 msn", 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';
}
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes