LIS and variation

LIS ( Longest Increasing Subsequence ) যখন আমাদের কোন লিস্ট দেওয়া হবে যার numerical value আছে প্রতিটা element এর এবং  এই লিস্ট থেকে আমাদের এমন একটা সাব লিস্ট নিতে হবে যেই সাব লিস্ট sequentially increasing order এ হবে ,  যদি আমরা এমন একটা সাব লিস্ট নেই যেইটার length আমাদের all possible chosen sub list এর মধ্যে বৃহত্তর তাহলে সেই সাব লিস্টটাকে LIS বলে । যদি উদারণ দেই , ( 3 , 4 , 1 , 8) যদি আমাদের লিস্ট হয় তাহলে { 3 } , { 4 } , { 1 } , { 8 } , { 3 , 4 } , { 4 , 8 } , { 1 , 8 } , { 3 , 4 , 8 } এইগুলো আমাদের all possible sub list যা increasing order এ আছে এদের মধ্যে { 3 , 4 , 8 } এই লিস্ট এর length সবথেকে বৃহত্তর তাই এইটা আমাদের LIS ।

LIS বের করার জন্য যেহেতু একটা single element এর value ( LIS length ) তার আগের element গুলার উপর নির্ভর করে , LIS কে তাই dynamic programming algorithm ( DP ) বলা যায় । আমার কাছে LIS সবথেকে সহজতর (বুঝার জন্য) ডায়নামিক প্রোগ্রামিং আল্গরিথম । তবে প্রোগ্রামিং কনটেস্ট এ খুব কমই আমরা সরাসরি কোন প্রবলেম পাব যেখানে খালি LIS বের করতে  বলছে । আমাদের অনেক প্রবলেম সল্ভ করতে হবে যেখানে দৃশ্যমান বা অদৃশ্যমান LIS লুকাইয়া থাকবে । এই লিখাটার উদ্দেশ্য হচ্ছে LIS এর সব ধরণের ভ্যারিয়েশন এর একটা প্রাথমিক ধারণা তুলে ধরা ।  

LIS এর সব থেকে naive solution হচ্ছে O(n^2) । আমরা যদি LIS বের করতে চাই প্রাথমিক ভাবে সব element এর LIS length 1 দিব , তারপর iterate করে current element এর অবস্থান থেকে এর আগের সব element এর মধ্যে দেখব কোন element টা আমাদের current element থেকে ছোট বা সমান ( ক্ষেত্রে বিশেষ এ , অনেক সময় বলাই থাকে কোন duplicate element থাকবে না  ) যদি এমন কোন element পাই তাহলে check করে দেখব আমাদের current element এর LIS ভ্যালু আপডেট করা যায় কিনা , এইভাবে আমারা সব element এর LIS ভ্যালু পেয়ে যাব এদের মধ্যে যার ভ্যালু ম্যাক্সিমাম এইটাই আমাদের LIS ।

	const int NX = 1000; // লিমিট
	int LIS[ NX + 5 ] , input[ NX + 5 ], n ;
	void solve()
	{
	scanf("%d",&n); // সিকুয়েন্স লেংথ
	for( int i = 0 ; i < n ; i++ )
	{
	scanf("%d",&input[i]); // ইনপুট সিকুয়েন্স
	}
	int ans = 0 ;
	for( int i = 0 ; i < n ; i++ )
	{
	LIS[i] = 1 ;
	for( int j = i - 1; j >= 0 ; j-- )
	{
	if( input[j] <= input[i] ) // আগের কোন নাম্বার আমাদের বর্তমান নাম্বার থেকে ছোট
	{
	LIS[i] = max( LIS[i] , LIS[j] + 1 );
	}
	}
	ans = max( ans , LIS[i]); // চেক আপডেট আন্সার

view raw LIS_O(N_sq).cpp hosted with ❤ by GitHub

অনেক ক্ষেত্রেই O(n^2) solution আমাদের জন্য খুব একটা ফলপ্রসূ নাও হতে পারে যদি দেখা যায় আমাদের 10^5 or 10^6 সংখ্যক element এর জন্য LIS বের করতে বলা হচ্ছে তাহলে আমাদের টাইম লিমিট দেখে আরো better কিভাবে আমরা LIS  পাব তা নিয়ে ভাবতে হবে। LIS এর একটা ছোট এবং ফাস্ট একটা সলুশ্যন হচ্ছে C++ এর বিল্ট ইন set ব্যাবহার করে nlg(n) এ সল্ভ করা । তবে এইখানে বলে রাখা ভাল যদি আমরা যদি set use করি তাহলে এইখানে duplicate কোন ভ্যালু LIS এ থাকবে না ।

	const int NX = 1000; // লিমিট
	int input[ NX + 5] , n ;
	void LIS_with_set()
	{
	set < int > lis ;
	set < int > :: iterator it ;
	scanf("%d",&n);
	for( int i = 0 ; i < n ; i++ )
	{
	scanf("%d",&input[i]);
	lis.insert( input[i]);
	it = lis.find( input[i]);
	it++;
	/*if its not the end of lis then removing it position
	value for better small value on that position */
	if( it != lis.end()) lis.erase(it);
	}
	cout << lis.size() << endl ;
	}

view raw LIS_set.cpp hosted with ❤ by GitHub

আমরা একটা উদারন দিয়ে বুঝতে পারি এইটা কিভাবে কাজ করে । ধরি { ১ , ৩ , ২ , ৪ } হচ্ছে আমাদের প্রাথমিক লিস্ট । স্বাভাবিকভাবে আমরা প্রথম element থেকে সামনে আগাবো । প্রথমে আমরা ১ আমাদের সেট এ পুশ করি , তাহলে set এর length হচ্ছে ১ । যদি তা একটা নরমাল array এর সাথে compare করি ( 0 index starting ) তাহলে LIS নামক array এর 0 index এ আছে ১ , এবং যখন আমরা find operation টা করছি  এর মাধ্যমে আসলে আমরা ১ যেখানে আছে এর index খুঁজে বের করছি । যেহেতু ১ এখন ০ নাম্বার ইনডেক্স এ আছে তাই আমরা it value এখন ০ পাব , এখন যদি  এর ভ্যালু ১ বাড়িয়ে দেখি ১ নাম্বার ইনডেক্স এর কোন অস্তিত্ব LIS array তে নাই বা ১ এই হচ্ছে আমাদের সর্বশেষ ভ্যালু যদি আমরা ১ পর্যন্ত প্রাপ্ত সব ভ্যালুকে sorted আকারে দেখি । তারপর ৩ set এ insert করার পরও আমরা একই অবস্থা পাব । তখন { ১ , ৩ } হবে আমাদের set array । কিন্তু যেহেতু set এ সর্ট আকারে সব ভ্যালু থাকে যখন ২ insert হবে আমাদের set array হবে { ১ , ২ , ৩ } এখন যখন আমরা find দিয়ে ২ এর অবস্থান খুজব আমরা পাব ১ নাম্বার ইনডেক্স এবং এর থেকে ১ পজিশন বাড়িয়ে দেখলাম যেমন এখন ২ , ২ নাম্বার ইনডেক্স এর অস্তিত্ব আছে , যাতে আছে ৩ । এর মাধ্যমে আমরা বুঝি আমরা এমন কোন কিছু পেয়েছি যেটার মাধ্যমে আমাদের set array এর length বেড়েছে কিন্তু element টা শেষ পজিশনে আসেনি । অর্থাৎ আমাদের প্রাপ্ত LIS হয়তো আপডেট হবে না কিন্তু এর একটা পজিশনে আমারা কম value এর কিছু insert করতে পারি যা পারে হয়তো আমাদের জন্য পরে লাভবান হতে পারে , তাই আমরা ৩ রিমুভ করে দিব । ফলে set array হবে { ১ , ২ } , এরপর যখন ৪ insert হবে আমাদের set array হয়ে যাবে { ১ , ২ , ৪ } । এইখানে ৩ রিমুভ যদি নাও করতাম তাহলেও তো অনেক এর কাছে লাগতে পারে { ১ , ৩ , ৪ } এমন কিছু পাইতাম যা লেংথ ও ৩ যা এই লিস্ট এর জন্য হাইস্ট । কিন্তু যদি আমাদের লাস্ট element , ৪ না হয়ে ৩ হত তাহলে ??? তাহলে কিন্ত ৩ এর পর কোন আপডেট লেংথ পেতে পাইতাম না , তাই যখনই কোন পজিশনের জন্য আপডেট ভ্যালু পাওয়া যাবে আপডেট করাটা জরুরী ।

এইভাবে কোড অনেক ছোট হচ্ছে কিন্তু একটা প্রবলেম থেকে যায় এইখানে duplicate ভ্যালু allow না । অনেক এর মনে হতে পারে তাওলে আমরা multiset use করব । আইডিয়া ঠিক আছে multiset duplicate value allow করলেও কিন্তু find আসলে lower_bound হিসাবে কাজ করে যখনই কোন duplicate value পাবে তার পজিশন এর জন্য ঠিক ভাবে কাজ করবে না ।  আমাদের তাই upper_bound ব্যাবহার করতে হবে find এর বদলে । multiset এবং সাথে upper_bound করে আমরা duplicate value এর জন্যও LIS পেয়ে যেতে পারি ।

	// duplicate value allowed
	const int NX = 1000;
	int input[ NX + 5] , n ;
	void LIS_with_set()
	{
	multiset < int > lis ;
	multiset < int > :: iterator it ;
	scanf("%d",&n);
	for( int i = 0 ; i < n ; i++ )
	{
	scanf("%d",&input[i]);
	lis.insert( input[i]);
	it = lis.upper_bound( input[i]);
	if( it != lis.end()) lis.erase(it);
	}
	cout << lis.size() << endl ;
	}

view raw LIS_multiset.cpp hosted with ❤ by GitHub

এখন আমরা LIS দ্বারা কিছু ইন্টারেস্টিং প্রবলেম এর সলুশ্যন ট্যাকনিক দেখব ।

LIS দিয়ে আমরা classical DP problem LCS সল্ভ করতে পারি এবং মজার ব্যাপার হচ্ছে better time limit এ । একটা প্রবলেম দিয়ে দেখি এইটা ।

XMEN
প্রবলেমটাতে আমাদের আমাদের একটা লিমিট N দেওয়া হবে এবং ( 1 - N ) পর্যন্ত দুইটা list দেওয়া হবে এদের মধ্যে থেকে আমাদের common longest sequence এর length বলতে হবে । classical LCS problem , কিন্তু লিস্ট length ( 10^5 )  পর্যন্ত হতে পারে এবং এর জন্য যদি আমারা LCS দিয়ে ট্রাই করি ( O(N^2) ) solution এর জন্য TLE পেয়ে যেতে পারি যা আমরা প্রায় nlg(n) এ LIS দিয়ে করে ফেলতে পারতাম । এই কাজের জন্য আমরা যেকোন একটা list কে base list ধরে ( 1 - N ) পর্যন্ত ভ্যালুর জন্য কিছু dummy value( serial number of that set ) সেট করব যার উপর আমরা যদি অপর লিস্ট এর উপর LIS করি তাহলে আমরা LCS পেয়ে যাব । ব্যাপারটা কিভাবে সম্ভব হবে আমারা একটা টেস্ট কেইজ দিয়ে দেখি । ধরে নিলাম আমাদের দুইটি sequence হচ্ছে { ৪ , ২ , ১ , ৩ } এবং অপরটা হচ্ছে { ১ , ৪  , ২ , ৩ } । যদি আমরা প্রথমটাকে আমাদের বেস ধরি তাহলে ,
৪ -> ১
২ -> ২
১ -> ৩
৩ -> ৪

যদি এই ভ্যালু গুলা দিয়ে সেকেন্ড লিস্টটা রিপ্লেস করি তাহলে { ১ , ৪ , ২ , ৩ } হয়ে যাবে { ৩ , ১ , ২ , ৪ } যার মধ্যে যদি LIS দেখি { ১ , ২ , ৪ } হচ্ছে আমাদের বৃহত্তর sequence যা { ৪ , ২ , ৩ } আমাদের LCS দুইটা sequence এর মধ্যে ।

	/*
	Problem Link ::: http://www.spoj.com/problems/XMEN/
	*/
	//BISMILLAHIRRAHMANIRRAHIM
	/*
	manus tar shopner soman boro
	all my suceesses are dedicated to my parents
	Author :: Shakil Ahmed
	.............AUST_CSE27.........
	prob ::
	Type ::
	verdict::
	*/
	#include <bits/stdc++.h>
	#define pb push_back
	#define mp make_pair
	#define pi acos(-1.0)
	#define ff first
	#define ss second
	#define re return
	#define QI queue<int>
	#define SI stack<int>
	#define SZ(x) ((int) (x).size())
	#define all(x) (x).begin(), (x).end()
	#define sqr(x) ((x) * (x))
	#define ms(a,b) memset((a),(b),sizeof(a))
	#define G() getchar()
	#define MAX3(a,b,c) max(a,max(b,c))
	#define II ( { int a ; read(a) ; a; } )
	#define LL ( { Long a ; read(a) ; a; } )
	#define DD ({double a; scanf("%lf", &a); a;})
	double const EPS=3e-8;
	using namespace std;
	#define FI freopen ("input.txt", "r", stdin)
	#define FO freopen ("output.txt", "w", stdout)
	typedef long long Long;
	typedef long long int64;
	typedef unsigned long long ull;
	typedef vector<int> vi ;
	typedef set<int> si;
	typedef vector<Long>vl;
	typedef pair<int,int>pii;
	typedef pair<string,int>psi;
	typedef pair<Long,Long>pll;
	typedef pair<double,double>pdd;
	typedef vector<pii> vpii;
	// For loop
	#define forab(i, a, b) for (__typeof (b) i = (a) ; i <= b ; ++i)
	#define rep(i, n) forab (i, 0, (n) - 1)
	#define For(i, n) forab (i, 1, n)
	#define rofba(i, a, b) for (__typeof (b)i = (b) ; i >= a ; --i)
	#define per(i, n) rofba (i, 0, (n) - 1)
	#define rof(i, n) rofba (i, 1, n)
	#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
	template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
	template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
	//Fast Reader
	template<class T>inline bool read(T &x){int c=getchar();int sgn=1;while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; x*=sgn; return ~c;}
	//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
	//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
	//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
	//int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction
	/* ************************************** My code start here ****************************************** */
	const int NX = 100000 + 10 ;
	int ID[NX] ;
	int main()
	{
	// freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int cs , t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	int n = II ;
	ms( ID , 0 );
	rep ( i , n )
	{
	int x = II ;
	ID[x] = i ;
	}
	set < int > s ;
	set < int > :: iterator it ;
	rep( i , n )
	{
	int x = II ;
	s.insert( ID[x] );
	it = s.find( ID[x] );
	it++;
	if( it != s.end() ) s.erase(it);
	}
	cout << s.size() << endl ;
	}
	return 0;
	}

view raw XMEN.cpp hosted with ❤ by GitHub

এমন একটি প্রবলেম হচ্ছে 10635 - Prince and Princess ।

Looking for a Subsequence

এইটা অনেক ভাল একটা প্রবলেম LIS এর উপর । এইখানে আমাদের LIS sequence ও  print করতে হবে , যদি কোন কারনে টাই হয়ে যায় তাহলে আমারা সব সময় left পজিশন এর ভ্যালু নিব । টাই প্রিন্ট এর ব্যাপারটা যদি না থাকত তাহলে আমরা খুব সহজেই হয়তো stack বা list বা vector কোন কিছুতে ভ্যালুগুলো রেখে তা প্রিন্ট করে ফেলতে পারতাম । একটা মজার ব্যাপার দেখি যেকোন LIS sequnce এ যদি আমরা value invert করে দেই তা LDS হয়ে যায় ( Longest decreasing sequence ) যদি LDS কে reverse order represent করি তাহলে কিন্ত্ আমরা আমার LIS order পেয়ে যাই । এইটা একটা fact .যেমন মাইনাস মাইনাস গুন করলে আমরা পজিটিভ কিছু পাব । আমরা তাই reverse order এ LDS করব যা আমাদের প্রতিটা পজিশন এর জন্য LIS এর ভ্যালু দিবে ( অবশ্যই reverse order এ ) । যা থেকে খুব সহজেই আমরা আমাদের sequence print করতে পারি বা দেখতে পারি এমন কোন sequence possible কিনা ।

	//BISMILLAHIRRAHMANIRRAHIM
	/*
	manus tar shopner soman boro
	all my suceesses are dedicated to my parents
	Author :: Shakil Ahmed
	.............AUST_CSE27.........
	prob ::
	Type ::
	verdict::
	*/
	#include <bits/stdc++.h>
	#define pb push_back
	#define mp make_pair
	#define pi acos(-1.0)
	#define ff first
	#define ss second
	#define re return
	#define QI queue<int>
	#define SI stack<int>
	#define SZ(x) ((int) (x).size())
	#define all(x) (x).begin(), (x).end()
	#define sqr(x) ((x) * (x))
	#define ms(a,b) memset((a),(b),sizeof(a))
	#define G() getchar()
	#define MAX3(a,b,c) max(a,max(b,c))
	#define II ( { int a ; read(a) ; a; } )
	#define LL ( { Long a ; read(a) ; a; } )
	#define DD ({double a; scanf("%lf", &a); a;})
	double const EPS=3e-8;
	using namespace std;
	#define FI freopen ("input.txt", "r", stdin)
	#define FO freopen ("output.txt", "w", stdout)
	typedef long long Long;
	typedef long long int64;
	typedef unsigned long long ull;
	typedef vector<int> vi ;
	typedef set<int> si;
	typedef vector<Long>vl;
	typedef pair<int,int>pii;
	typedef pair<string,int>psi;
	typedef pair<Long,Long>pll;
	typedef pair<double,double>pdd;
	typedef vector<pii> vpii;
	// For loop
	#define forab(i, a, b) for (__typeof (b) i = (a) ; i <= b ; ++i)
	#define rep(i, n) forab (i, 0, (n) - 1)
	#define For(i, n) forab (i, 1, n)
	#define rofba(i, a, b) for (__typeof (b)i = (b) ; i >= a ; --i)
	#define per(i, n) rofba (i, 0, (n) - 1)
	#define rof(i, n) rofba (i, 1, n)
	#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
	template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
	template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
	//Fast Reader
	template<class T>inline bool read(T &x){int c=getchar();int sgn=1;while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; x*=sgn; return ~c;}
	//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
	//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
	//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
	//int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction
	/* ************************************** My code start here ****************************************** */
	const int NX = 2e5 + 10 ;
	const Long INF = 2e18 + 10 ;
	const Long add = 1e9 + 10 ;
	Long inp[NX] , dp[NX] , L[NX] ;
	vector < int > pos[NX] ;
	int n , q ;
	int query[20];
	int vis[20];
	vector < Long > ans[20];
	bool solve( int lim )
	{
	bool ok = 0 ;
	Long prv ;
	rep( i , n )
	{
	if( L[i] >= lim )
	{
	if( ok && inp[i] <= prv ) continue ;
	if( ok ) printf(" ");
	printf("%lld",inp[i]);
	prv = inp[i] ;
	ok = 1 ;
	lim--;
	}
	if(lim == 0 ) break ;
	}
	if( ok == 0 ) return 0 ;
	puts("");
	return 1 ;
	}
	int main()
	{
	// I will always use scanf and printf
	// May be i won't be a good programmer but i will be a good human being
	// ms( vis , -1 );
	int cs , t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	n = II , q = II ;
	rep( i , n )
	{
	inp[i] = LL ;
	dp[i] = INF ;
	}
	int low , i , j ;
	dp[0] = -INF ;
	dp[n] = INF ;
	for ( i = n - 1 ; i >= 0 ; i-- )
	{
	low = lower_bound( dp , dp + n + 1 , -inp[i] ) - dp ;
	dp[low] = -inp[i];
	L[i] = low ;
	}
	printf("Case %d:\n",cs);
	rep( i , q )
	{
	int x = II ;
	if( solve(x) == 0 ) printf("Impossible\n");
	}
	}
	return 0;
	}

view raw subsequence.cpp hosted with ❤ by GitHub

এই লিখাটা এইখানেই শেষ । কোন প্রশ্ন থাকলে কমেন্ট সেকশনে বা আমাকে সরারসি ফেসবুক , ইমেল এ যোগাযোগ করলেই হবে :)