### algoskipper's blog

By algoskipper, history, 3 weeks ago,

Can anyone hep me with this question I can think of LIS but am not able to solve it

Code implement with LIS

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(n) for(ll i=0;i<n;i++)
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
ll t;
cin>>t;
while(t--){

ll n;cin>>n;
vector<pair<ll,ll>>a(n);
f(n)cin>>a[i].first;
f(n){cin>>a[i].second;}
sort(a.begin(),a.end(),[&](pair<ll,ll>a,pair<ll,ll>b){
if(a.first==b.first)return a.second>b.second;
return a.first<b.first;
});
vector<ll>b;
vector<pair<ll,ll>>lp;
ll ans=1;
lp.push_back({-1,-1});
b.push_back(-1);
for(ll i=0;i<n;i++){
if(lp[lp.size()-1].first==a[i].first)continue;
auto it= lower_bound(b.begin(), b.end(), a[i].second);
if (it == b.end()) {
b.push_back(a[i].second);
lp.push_back(a[i]);
}
else {
lp[it-b.begin()]=a[i];
b[it-b.begin()] = a[i].second;
}
}
cout<<lp.size()-1<<endl;
}
}

• +3

 » 3 weeks ago, # | ← Rev. 2 →   +3 you could sort the boxes based on height and then find the LIS of the widths of the boxes since then all the boxes chosen will have height in sorted order as well as width in sorted orderlike in the example , sort based on height h : 6 10 10 12w : 6 5 10 12 and now you could find the LIS of w in this case it will be 3 -> 6 10 12
•  » » 3 weeks ago, # ^ |   0 I tried it but its giving wrong answer Below is my code if yoy can find any testcase or logic error #include using namespace std; #define ll long long #define f(n) for(ll i=0;i>t; while(t--){ ll n;cin>>n; vector>a(n); f(n)cin>>a[i].first; f(n){cin>>a[i].second;} sort(a.begin(),a.end(),[&](paira,pairb){ if(a.first==b.first)return a.second>b.second; return a.firstb; vector>lp; ll ans=1; lp.push_back({-1,-1}); b.push_back(-1); for(ll i=0;i
•  » » » 3 weeks ago, # ^ |   0 im a python user so cpp is a bit difficult for me ;-; , could you send me the question link , i will try solving it after todays contest.
•  » » » 3 weeks ago, # ^ |   0 Here is the code in python , i have found the LIS using segment tree. Спойлерclass Solution: def maxEnvelopes(self, envelopes: List[List[int]]) -> int: envelopes = sorted(envelopes,key = lambda x:(x[0],-x[1])) L1 = envelopes class SegmentTree: def __init__(self, data): self.n = len(data) self.tree = [0] * (2 * self.n) self.build(data) def build(self, data): for i in range(self.n): self.tree[self.n + i] = data[i] for i in range(self.n - 1, 0, -1): self.tree[i] = max(self.tree[i * 2], self.tree[i * 2 + 1]) def update(self, pos, value): pos += self.n self.tree[pos] = value while pos > 1: pos //= 2 self.tree[pos] = max(self.tree[2 * pos], self.tree[2 * pos + 1]) def query(self, left, right): left += self.n right += self.n max_val = float('-inf') while left < right: if left % 2: max_val = max(max_val, self.tree[left]) left += 1 if right % 2: right -= 1 max_val = max(max_val, self.tree[right]) left //= 2 right //= 2 return max_val k1 = 0 for i in range(len(L1)): k1 = max(k1,L1[i][1]) L = SegmentTree([0 for i in range(k1+1)]) ans = 0 for i in range(len(L1)): f = L.query(0,L1[i][1]) L.update(L1[i][1],1+f) ans = max(ans,1+f) return ansThis is my solution.The problem link — link.It is quite similar to the problem you showed, try submitting your answer here, it will show you what test case your answer failed for.
 » 3 weeks ago, # | ← Rev. 2 →   +1