➤ Problem Link : 4D. Mysterious Present
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
bool comp(pair<int,pair<int,int> > a, pair<int,pair<int,int> > b)
{
if(a.second.first != b.second.first)
return a.second.first < b.second.first;
return a.second.second < b.second.second;
}
void printAll(int v, int sol[],pair<int,pair<int,int> > arr[])
{
if(sol[v]==v)
{
cout<<arr[v].first<<" ";
return;
}
printAll(sol[v],sol,arr);
cout<<arr[v].first<<" ";
}
int main()
{
int n,w,h,a,b;
cin>>n>>w>>h;
pair<int,pair<int,int> > arr[n];
int k=0;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
if(a > w && b > h)
{
arr[k].first=i;
arr[k].second.first = a;
arr[k++].second.second = b;
}
}
if(k==0)
{
cout<<"0";
exit(0);
}
sort(arr,arr+k,comp);
int dp[k+1];
int sol[k+1];
ll top=0;
dp[0]=1;
sol[0]=0;
for(int i=1;i<k;i++)
{
dp[i]=1;
sol[i]=i;
for(int j=i-1;j>=0;j--)
{
if(arr[j].second.first < arr[i].second.first && arr[j].second.second < arr[i].second.second && dp[j]+1>dp[i])
{
dp[i]=dp[j]+1;
sol[i]=j;
}
}
if(dp[i]>dp[top])
top=i;
}
cout<<dp[top]<<"\n";
printAll(top,sol,arr);
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
➤ Problem Link : 4D. Mysterious Present
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
bool comp(pair<int,pair<int,int> > a, pair<int,pair<int,int> > b)
{
if(a.second.first != b.second.first)
return a.second.first < b.second.first;
return a.second.second < b.second.second;
}
void printAll(int v, int sol[],pair<int,pair<int,int> > arr[])
{
if(sol[v]==v)
{
cout<<arr[v].first<<" ";
return;
}
printAll(sol[v],sol,arr);
cout<<arr[v].first<<" ";
}
int main()
{
int n,w,h,a,b;
cin>>n>>w>>h;
pair<int,pair<int,int> > arr[n];
int k=0;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
if(a > w && b > h)
{
arr[k].first=i;
arr[k].second.first = a;
arr[k++].second.second = b;
}
}
if(k==0)
{
cout<<"0";
exit(0);
}
sort(arr,arr+k,comp);
int dp[k+1];
int sol[k+1];
ll top=0;
dp[0]=1;
sol[0]=0;
for(int i=1;i<k;i++)
{
dp[i]=1;
sol[i]=i;
for(int j=i-1;j>=0;j--)
{
if(arr[j].second.first < arr[i].second.first && arr[j].second.second < arr[i].second.second && dp[j]+1>dp[i])
{
dp[i]=dp[j]+1;
sol[i]=j;
}
}
if(dp[i]>dp[top])
top=i;
}
cout<<dp[top]<<"\n";
printAll(top,sol,arr);
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.