Another longest inc subseq

Ashu1318 · November 1, 2020, 10:36am

the n*n method gives tle in this que ,how to implement binary search lis method on pairs ??

mr.encoder · November 1, 2020, 10:40am

Hey @Ashu1318 take this for reference

Hikari9/UVa/blob/master/SPOJ LIS2 - Another Longest Increasing Subsequence Problem.cpp

// SPOJ LIS2 - Another Longest Increasing Subsequence Problem
// http://www.spoj.com/problems/LIS2/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
#define x first
#define y second

using namespace std;
const int N = 100001;
typedef pair<int, int> point;

int n;
point dummy;
set<point> s[N];

bool cmp(const point& a, const point& b) {
	return a.x < b.x && a.y < b.y;

This file has been truncated. show original

Ashu1318 · November 1, 2020, 10:48am

actually cant understood the logic of this solution ,can explain it little bit more

mr.encoder · November 1, 2020, 10:54am

A pair (a,b) is less than another pair (c,d) if and only if a < c and b < d.

This can be easily solved in O(N^2) time by adapting the standard dynamic programming technique.
The classic O(N log N) solution to the standard LIS problem can be extended to give a subquadratic solution to the LIS problem with pairs, with some difficulty. We cannot simply remember one minimum value for every possible length; we have to maintain “staircase-like” structures containing all minimal pairs for each length, that is, up to N copies of the data structure described here, implemented using an ordered dynamic set of pairs keyed on the first member. We can then query one copy of this structure in O(log N) time (to check whether it contains any pair less than the current pair), giving O(log^2 N) time for the binary search step, and O(N log^2 N) time in all. This is the fastest solution I know to the problem.

mr.encoder · November 7, 2020, 8:27am

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.