DP on Tree

ফেসবুক এ ব্লগ লিখা বা কনটেস্ট করার সুবিধার্থে অনেকের সাথে কথা হয় । অনেকবারই অনুরোধ ছিল DP on tree নিয়ে যেন লিখি । Quora তে অনেক ভাল একটা পোস্ট আছে IIT Haydrabad এর ( লিঙ্ক ) যেইটা পড়লেই আসলে হয় , এইখানে অনেক variation নিয়ে লিখা হয়েছে । শুধু এই পোস্ট না উনাদের Data Structure এবং Graph Theory এর উপর অনেক ভাল কিছু পোস্ট আছে যা ফলো করা উচিত যারা সিরিয়াস কনটেস্ট করছে বা করতে চায় । IIT এর Threads এর পোস্ট এর পর আসলে DP on Tree এর উপর কিছু লিখার থাকে না তবুও অনেকের এর অনুরোধ ছিল যেন লিখি তাই আমার মত করে আমি বাংলায় একটা লিখার চেস্টা করছি।

DP on tree এই নামই বা কেন ? আসলে tree উপর ডিপি চালানো হয় বলে এই নাম । এইটা কোন ক্যাসিক্যাল প্রবলেম না মানে প্রবলেম এর উপর এর সল্ভ ট্যাকনিক ভিন্ন হইতে পারে ( একই রকম সল্যুশন প্যাটান নাই তবে কমন কিছু বৈশিষ্ট্য অবশ্যই আছে ) । যেহেতু ট্রি এর উপর ডিপি , লিফ নোড থেকে সহজেই ডিপেন্ডেন্সি মেইনট্যান্ট করা সম্ভব । প্রবলেমগুলার সলুশ্যন ম্যাক্সিমাম ক্ষেত্রেই রিকাশন রিলেশনের মাধ্যমে বের করতে সুবিধা হয় । ট্রি এবং রিকারশন ডিপি এইখানে ৩টা কমন জিনিস দেখা যায় ।

     ( ১ ) Base Case , leaf node এ থেকে কিছু হয় ।
     ( ২ ) parent node এর dp value তার child node or grand-child corresponding grand-child এর উপর নির্ভর করে ।
    ( ৩ ) রিকারশন ডিপি হওয়ার পরও যেহেতু ট্রি একটা নোড এর কল একবারই হয় , অনেক ক্ষেত্রেই memorization লাগে না ( yes !!! you read it right !!! ) normal dfs call এর মাধ্যমেই হয়ে যায় ।কারণ ট্রি বলে পার নোড এ একবারই কল হয় । দরকারে binary-search করা লাগতে পারে । তবে ডিপি মানেই সাব-প্রবলেম টাস্ক , এক নোডের রেজাল্ট তার চাইল্ড এবং গ্রেন্ড চাইল্ডের উপর নির্ভর করে ।

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

PT07X - Vertex Cover :

DP on Tree এর ব্যাসিক প্রবলেম হিসাবে বুঝার জন্য কিভাবে tree dp গুলা কাজ করে এইটা খুবই ভাল একটা প্রবলেম । এই প্রবলেম এ আমাদের বলছে আমাদের একটা ট্রি এর edge list দেওয়া হবে আমাদের minimum node set নিতে হবে যাতে সবগুল edge এর কোন না কোন একটা end point থাকে , দুইটা end point থাকলে প্রবলেম নাই কিন্তু একটা অবশ্যই থাকতে হবে ।

প্রবলেম সল্ভ এর সব থেকে একটা key point হইল এইটা ট্রি , মানে যে কোন নোডই কোন না কোন একটা edge এর end point হবে । অর্থাৎ যদি আমরা কোন নোডকে না নিতে চাই তাহলে অবশ্যই আমরা এর সাথে যত নোড কোন একটা edge connection এ আছে তাদেরকে অবশ্যই নিতে হবে না হইলে আমাদের শর্ত মানা হবে না । যদি নেই তাহলে তার সাথে যে যে সব নোড edge connection এ আছে তাদেরকে নিতেই হবে এমন শর্ত আর থাকে না তাই তাদের কোনটি নিয়ে বা না নিয়ে minimum set টাই আমারা নিব ।

	//BISMILLAHIRRAHMANIRRAHIM
	/*
	manus tar shopner soman boro
	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 ("t.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 MX = 100000 + 10 ;
	vector < int > adj[MX];
	int dp[MX][2];
	void dfs(int x , int par)
	{
	dp[x][0] = 0 ;
	dp[x][1] = 1 ;
	int sz = adj[x].size();
	rep ( i , sz )
	{
	int v = adj[x][i];
	if ( v == par ) continue ;
	dfs(v,x);
	dp[x][0] += dp[v][1];
	dp[x][1] += min(dp[v][1] , dp[v][0]);
	}
	}
	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
	//FI ;
	// FO ;
	int n = II ;
	rep ( i , n - 1 )
	{
	int x = II ;
	int y = II ;
	adj[x].pb(y);
	adj[y].pb(x);
	}
	dfs(1,-1);
	printf("%d\n",min(dp[1][0] , dp[1][1] ) );
	return 0;
	}

view raw dp_on_tree_one.cpp hosted with ❤ by GitHub

উপরের কোন এ dp[ ( node_number ) ][ 0 ] means করে এই নোডটা না নিয়ে এবং dp[ ( node_number ) ][ 1 ] means করে এই নোডটা নিয়ে কি কি পাওয়া হচ্ছে সেট ।

Anniversary party :

এই প্রবলেমটা অনেক মজার এবং  basic DP on tree বুঝার জন্য অনেক ভাল একটা প্রবলেম । এইখানে n জন মানুষকে একটা পার্টিতে দাওয়াত দিতে  হবে , এবং প্রতিটা মানুষ এর পার্টিটা জমাইয়া রাখার কিছু রেটিং পয়েন্ট আছে । আমাদের নরমাল লাইফে এ দেখা যায় কিছু মানুষ জন আছে যারা অনেক মজা করতে পারে , তারা কোন অনুষ্ঠানে থাকলে সবাই অনেক মজা পায় আবার কেউ কেউ অনেক গম্ভীর তাদের থাকা না থাকা একই ব্যাপার , আবার কেউ কেউ অনেক রাগী তারা না থাকলেই ভাল ।  এইখানে আরো একটা শর্ত দেওয়া আছে । যেহেতু এইটা একটা প্রতিষ্ঠানের পার্টি  এইখানে কোন বস তার ইমেডিয়েট জুনিওর থাকলে ঐ পার্টিতে যায় না , জুনিওর এর ক্ষেত্রেও একই । মানে হইল হয় বস থাকবে না হয় জুনিওর থাকবে বা কেউই থাকবে না । আমাদের এমনভাবে পার্টি করার জন্য সবাইকে দাওয়াত দিতে হবে যেন পার্টিটা সব থেকে বেশী মজার হয় ।

উপরের প্রবলেমটার মত এই প্রবলেমও বেস কেইজ দুইটা । dp[ employee_number ][ 2 ] ;

dp[ employe_number ][ 0 ] ; // যদি কারেন্ট ইমপ্লোয়ি প্রেজেন্ট থাকে , তাহলে পার্টিতে হাইস্ট 'conviviality rating' কত হইতে পারে , dp[ employee ][ 1 ] ; // যদি তিনি না থাকেন তাহলে কি হইতে পারে।

এইখানে যখন আমরা dp[ employee_number ][ 0 ] নিয়ে নিব তখন অবশ্যই তার ইমেডিয়েন্ট জুনিওর 'U' হলে ও অবশ্যই নেওয়া যাবে না , কিন্তু ইমেডিয়েন্ট জুনিওর 'U' না নিয়ে যা পাওয়া গেছে তা এড হবে । কারণ এতে কোন প্রবলেম নাই ।
যদি আমরা current employee কে না নেই তাহলে আমরা অবশ্যই জুনিওর কে নিয়ে বা না নিয়ে যেইটা সবথেকে বেশী হয় এইটা এড করব ।

	//BISMILLAHIRRAHMANIRRAHIM
	/*
	manus tar shopner soman boro
	all my suceesses are dedicated to my parents
	The true test of a man's character is what he does when no one is watching.
	Don't let your dreams be dreams.
	Author :: Shakil Ahmed
	.............AUST_CSE27.........
	prob ::
	Type ::
	verdict::
	*/
	#include <bits/stdc++.h>
	#define pb push_back
	#define mp make_pair
	// Macro
	#define eps 1e-9
	#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 sq(a) ((a)*(a))
	#define distance(a,b) (sq(a.x-b.x) + sq(a.y-b.y))
	#define iseq(a,b) (fabs(a-b)<eps)
	#define eq(a,b) iseq(a,b)
	#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 ("1.txt", "r", stdin)
	#define FO freopen ("2.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); }
	#define __(args...) {dbg,args; cerr<<endl;}
	struct debugger{template<typename T> debugger& operator , (const T& v){cerr<<v<<"\t"; return *this; }}dbg;
	#define __1D(a,n) rep(i,n) { if(i) printf(" ") ; cout << a[i] ; }
	#define __2D(a,r,c,f) forab(i,f,r-!f){forab(j,f,c-!f){if(j!=f)printf(" ");cout<<a[i][j];}cout<<endl;}
	template<class A, class B> ostream &operator<<(ostream& o, const pair<A,B>& p){ return o<<"("<<p.ff<<", "<<p.ss<<")";} //Pair print
	template<class T> ostream& operator<<(ostream& o, const vector<T>& v){ o<<"[";forstl(it,v)o<<*it<<", ";return o<<"]";} //Vector print
	template<class T> ostream& operator<<(ostream& o, const set<T>& v){ o<<"[";forstl(it,v)o<<*it<<", ";return o<<"]";} //Set print
	//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 = 1e6 ;
	int dp[2][ NX ] , n , inp[NX] , parnt[NX];
	vector < int > adj[ NX ];
	void ini()
	{
	for( int i = 0 ; i <= n + 1 ; i++ )
	{
	adj[i].clear();
	dp[0][i] = dp[1][i] = 0;
	parnt[i] = -1 ;
	}
	}
	void dfs( int x )
	{
	int sz = adj[x].size();
	dp[0][x] = max( 0 , inp[x] ) ;
	for( int i = 0 ; i < sz ; i++ )
	{
	int u = adj[x][i];
	dfs(u);
	dp[0][x] += max( 0 , dp[1][u] ); // from his grand child
	dp[1][x] += max( 0 , max( dp[1][u] , dp[0][u] ) );
	}
	}
	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
	while( scanf("%d",&n) == 1 )
	{
	ini();
	for( int i = 1 ; i <= n ; i++ ) inp[i] = II ;
	int x , y ;
	while( scanf("%d %d",&x,&y) == 2 )
	{
	if( x == 0 && y == 0 ) break ;
	adj[y].pb(x);
	parnt[x] = y ;
	}
	int root ;
	int ans = 0 ;
	for( int i = 1 ; i <= n ; i++ )
	{
	if( parnt[i] == -1 )
	{
	dfs( i );
	ans += max( dp[0][i] , dp[1][i] );
	}
	}
	printf("%d\n",ans);
	}
	return 0;
	}

view raw dp_on_tree_two.cpp hosted with ❤ by GitHub

এই প্রবলেম দুইটা DP on tree বুঝার জন্য অনেক ভাল প্রবলেম । সামনে আরো লিখার মোটিভেশন পাইলে কিছু hard dp on tree নিয়ে লিখার ইচ্চা আছে । 

0/1 BFS

shortest path বের করার গ্রাফ এর আল্গরিথম গুলোকে দুই ভাবে ভাগ করা যায় ।

   ১। এক নোড থেকে অন্য নোডে যাবার cost ১ ।
   ২। এক নোড থেকে অন্য নোডে যাবার cost যে কোন কিছু হইতে পারে।

যদি এক নোড থেকে অন্য নোডে যাবার cost ১ হয় তাহলে  এই প্রবলেম গুলা bfs বা dfs দিয়ে সল্ভ করা হয় যদি cost যে কোন কিছু হয় তাহলে floyd-warshal , Dijkstra বা Bellmanford ব্যাবহার করা হয় , যদি নেগেটিভ হয় cost তাহলে Bellmanford ব্যাবহার করা ।

bfs এর একটা ভ্যারিয়েশন হচ্ছে 0/1 bfs .  এইখানে এক নোড থেকে অন্য নোডে যাবার cost 0 বা ১ হতে পারে ।সচরাচর আমরা bfs এর প্রবলেম  এ queue ব্যাবহার করি , এইখানে আমরা করব deque .  যদি current node থেকে আমরা next node এ ০ cost এর কোন edge দ্বারা যুক্ত থাকি যা মানে হচ্ছে current node এ থাকা আর next node এ থাকা একই ব্যাপার তাহলে next_node কে deque এর front এ পুশ করব । যদি দেখা যায় current node থেকে next node এ যাবার cost ১ তাহলে আমরা deque এর back এ next_node কে পুশ করব । আর একটা ব্যাপার রয়েছে , bfs এ আমরা একটা নোড একবার আসা মানেই এতে minimum cost এ এসে গেছি এইখানে কিন্তু তা হয় , তাই নোড cost update এর কাজটা আমরা dijkstra এর মত করব , dijkstra তে প্রতি পুশ এর জন্য priority_queue বা sorting_order কাজ করতে হয় এতে push এর জন্য টাইম লাগে প্রায় logN এর মত , o/1 bfs তা o(1) এ হবে । বাকি সব কিছু আগের মতই হবে ।

practice problem : 1 

Programming Interview Tanvir Hasan Anick

ইন্টারভিউ সিরিজের আগের লিখাগুলা এই লিঙ্কে পাওয়া যাবে ।

প্রশ্ন ঃ প্রোগ্রামিং কন্টেস্ট এর ব্যাপারে প্রথম কিভাবে জানছিলা মনে আছে ? উত্তরঃ হুম। ভার্সিটিতে ভর্তি হবার আগে হালকা প্রোগ্রামিং শিখে ছিলাম। আমি একটু দেরিতে ভর্তি হবার কারণে আমার অন্যান্য ফ্রেন্ডরা একটু এগিয়ে ছিল। ওইসময় সাস্টের এক ফ্রেন্ড ইভান, (স্কুল ফ্রেন্ড মূলত) ওর কাছ থেকে প্রথম "uva peter smoke" প্রবলেমটার লিঙ্ক পাই।

সেইদিন থেকেই মূলত প্রোগ্রামিং কন্টেস্ট নাম এ কিছু একটা আছে। এই জিনিসটা জানা হয়েছিল।  প্রশ্নঃ প্রথম অনসাইট কনটেস্ট কথা মনে আছে ? 
উত্তরঃ হ্যাঁ ২০১২ সালে। আমার প্রথম অনসাইট ছিল ICPC-2012। ড্যাফোডিল ইউনির্ভাসিটিতে। কোনকিছুই তেমন করি নাই, শুধু এদিক ওদিক তাকিয়ে ছিলাম আর একটা চাইনিজ টিমের সল্ভ করার আনন্দ দেখেছি। প্রশ্নঃ কি টাইপের প্রবলেম সল্ভ করতে বেশি ভাল লাগে ? উত্তরঃ নাম্বার থিউরি আর ডিপি। প্রশ্নঃ কোন প্রবলেম সল্ভ এর সময় "Thinking Process" কি থাকে প্রবলেম পড়ার পর ? উত্তরঃ প্রবলেম পড়ার পরেই প্রথমে আগে ছোট ছোট কেস খাতায় লিখে একটা বেসিক আইডিয়া দাঁড় করানোর চেষ্টা করি। যদি দেখি যে ঠিকঠাক আছে তখন কোড করা শুরু করি। আর যেসব প্রবলেম মনে হয় প্যার্টান আছে, সেইগুলার জন্য আগেই একটা ব্রুটফোর্স কোড লিখে র্স্কিনে কিছু কেস রান করিয়ে খাতা কলম নিয়ে বসি প্যার্টান বের করার চেষ্টায়। প্রশ্নঃ UAP এর এসিএম ট্রনিং কিভাবে হয় ? উত্তরঃ Uap সাম্প্রতি সময়ে কন্টেস্ট এর রেজাল্ট ভাল করার জন্য অনেক আগ্রহী। সেইজন্য বর্তমানে সিনিয়র ও জুনিয়র দুই লেভেলের জন্য আলাদা আলাদা ট্রেইনার নিয়োগ দেয়া হয়েছে। সিনিয়রদের এখন শিপলু স্যার আর জুনিয়রদের সুপ্ত ভাই ট্রেইনিং করাচ্ছে। আর যেহেতু ভার্সিটি এখন পার্মানেন্ট ক্যাম্পাসে আছে, তাই সুযোগ সুবিধা আগে থেকেও এখন অনেক বেশি। প্রশ্নঃ আইওআই যারা না করে ভার্সিটি থেকে কনটেস্ট করে তারা দেখা যায় আইওআই যারা করেছেন তাদের থেকে পিছাইয়া থাকে , অনেক সময়ই পিছাইয়াই থাকে । যারা ভার্সিটি তে মাত্র কনটেস্ট নিয়ে জানল তাদের কি করা উচিত এই দুরুত্ব কমানোর জন্য ? উত্তরঃ যারা ioi করে তাদের জন্য অনেক স্পেশাল ট্রেইনিং হয় যার ফলে তারা স্বাভাবিকভাবে ভার্সিটিতে কন্টেস্ট করে তাদের থেকে অনেক এগিয়ে থাকে। সেই হিসেবে দেখা যায় ভার্সিটির সেই স্টুডেন্টকে তাদের লেভেল এ আসতে আসতে অনেক সময় লেগে যায়। সেই সময়ে হয়ত তাদের ভার্সিটি লাইফও শেষ হয়ে যায়। যেমনঃ আমি tongue emoticon:p আর আমি প্রাইভেট ভার্সিটিতে পড়তে গিয়ে একটা জিনিস দেখেছি, বেশিরভাগ স্টুডেন্ট ভর্তি হয় এখানে একটা হতাশা নিয়ে। তাদের সব-সময় এমন একটা মেন্টালিটি সেট করা থাকে যে আমি পাবলিক ভাল কোথায়ও চান্স পাই নাই তাই আমাকে নিয়ে এইসব কন্টেস্ট টাইপ জিনিস কোনদিন হবে না। তাই যারা ভার্সিটি ভর্তি হয়ে কন্টেস্ট সম্মন্ধে জানল বা কন্টেস্ট করার আগ্রহ আছে, তাদের প্রথমেই সকল হতাশা ঝেড়ে ফেলা উচিত। আর এমন একটা মনোভাব থাকা উচিত আমি পারবই। আর নিয়মিত প্র্যাকটিস। যেটা একটা ফরজ জিনিস কন্টেস্ট এর জন্য। তবে আমার ভার্সিটির অভিজ্ঞতা বলে নতুন যারাই আসে ভার্সিটির প্রথম সেমিস্টারে তারা কিভাবে কিভাবে যেন html css দিয়ে সাইট ডেভেলাপ করা যায় আর তা দিয়ে টাকা আর্জন করা যায় এমন একটা ধারনা পায়। আর পথে হাঁটতে গিয়ে বেশির ভাগ স্টুডেন্ট না শিখে প্রোগ্রামিং না হয় ভাল ডেভেলপার। প্রশ্নঃ tanvir002700.wordpress.com শুরু করার কথা কিভাবে ভাবলা , বাংলায় ব্লগ প্রোগ্রামিং নিয়ে খুব একটা নেই এখন যারা কনটেস্ট করে তাদের ব্লগিং কিভাবে তাদের হ্যাল্প করতে পারে , নতুন যারা ব্লগ লিখছে তাদের জন্য কোন সাজেশন ? উত্তর : tanvir002700.wordpress.com এইটা প্রথমে তেমন মহৎ চিন্তা নিয়ে শুরু করি নাই। প্রথম যখন python শেখা শুরু করি, দেখলাম যে আমরা কন্টেস্ট এ যেসব algorithm ব্যবহার করি সেইগুলা পাইথনে তেমন নেই, বা সহজে পাওয়া যায়। তারপর আমি কিছু algorithm পাইথনে লিখে ফেসবুকে একটা পোষ্ট আঁকারে দেই। ফেসবুক পোস্টে কোড দেয়া অনেক ঝামেলা। তারপর তখন মনে হল ব্লগে লিখি এইগুলা পরে আমি ভুলে গেলে নিজেও দেখতে পারব। তারপর ব্লগ খুলি। তারপর যখন শিপলু স্যারের কাছ থেকে suffix array শিখলাম তখন চিন্তা করলাম এই জিনিসত বাংলায় কোথায়ও ভাল রিসোর্স পাই নাই। এইটা সবার সাথে শেয়ার করি, নিজেও ভুলে গেলে আবার এইখান থেকে দেখে নেয়া যাবে আর অন্যরাও একটু হেল্প পাবে। এইভাবেই ব্লগ লেখা শুরু। যারা নতুন নতুন ব্লগ লেখছ, তাদের জন্য একটা উপদেশ প্রথম প্রথম হয়ত অনেকের কাছ থেকে অনেক কথা শুনবা। অনেকে হয়ত বলবে ফেমাস হওয়ার জন্য করছ। (আমি যে প্রবলেম ফেস করেছিলাম আরকি ) এইসব কান না দিয়ে নিজের মত করে লিখে যাও, কেউ কমেন্টে কোন সাজেশন দিয়ে সেইগুলা গ্রহণ করে লেখা উন্নত কর। জ্ঞান সবার মাঝে ছড়িয়ে দেয়ায় ক্ষতির কিছু নেই। প্রশ্নঃ Quora , Codefight এইসবগুলাতেও তুমি অনেক একটিভ । বাংলাদেশ এর এখনও এইসব সাইট এতটা জনপ্রিয়তা পায় নাই , এইগুলো তোমাকে কোন হ্যাল্প করতেছে ? উত্তরঃ Quora নিয়ে তেমন বিশেষ কিছু বলার নেই। খুব সম্প্রতি Quora তে একটিভ আমি। বাসায় বেকার বসে আছিতো, তাই অলস সময় একটু ইফেকটিভ কিছু করে কাটানোর একটা ছোট চেষ্টা মাত্র।
tongue emoticon আর Codefight, হ্যাঁ এই জিনিসটা আমার কোডের ডিবাগিং এবিলিটি অনেক বাড়িয়ে দিয়েছে। তবে মাঝে দিয়ে এই জিনিসের চরম নেশায় পড়ে গিয়েছিলাম। কোডফাইটের কয়েন দিয়ে টি-শার্ট কেনা যায় সেই টি-শার্টের লোভে সারাদিন ফাইট দিতাম। tongue emoticon তবে Codefight অনেক ভাল একটা জিনিস, যারা সারাদিন ক্ল্যাশ অফ ক্ল্যানে এটাক দাও তারা কিছুদিন Codefight এ ফাইট দিয়ে দেখতে পার, কোডিং ভাল লাগলে এই জিনিসের নেশায় পরে যাবা। আর এই জিনিস রিটার্নে তোমাকে ডিবাগিং এর কিছু এবিলিটি দিবে যেটা হয়ত অন্য গেম দেয় না। সব মিলিয়ে আমার কাছে খুবই ভাল একটা সাইট। প্রশ্নঃ অনেকেই ভার্সিটি লাইফে প্রোগ্রামিং কনটেস্ট এর চেয়ে freelancing এ জোর দেয় অনেক , এইটা আমি খারাপ বলছি না , এতে অনেক টাকাও পাওয়া যায় কিন্ত্ শিখার টাইমটা অনেক নস্ট হয় , এই ব্যাপারে তুমি কি বলবা ? উত্তরঃ freelancing!!! এই ব্যাপারে আমার মতামত খুবই নেগিটিভ। আমার ভার্সিটে দেখা অভিজ্ঞতা যদি বলি, বেশিরভাগ স্টুডেন্ট প্রথমেই সিএসইতে ভর্তি হয়ে যে জিনিসটা যানে সেইটা হল freelancing নামে একটা জিনিস আছে যেটা দিয়ে অর্থ উপার্জন করা যায়। সেই জিনিসের সুবাধে বেশিরভাগ স্টুডেন্ট ভার্সিটির প্রথম সেমিস্টার থেকেই হালকা html css শিখে টাকা কামায়ের ধান্দায় পরে যায়। এইভাবে করে দেখা যায় সে প্রোগ্রামিং এর বেসিক জিনিস ও এ্যালগরিদম ডাটাস্ট্রাকচার এইগুলা কিছুই শেখে না। সুতরাং আমার তবে freelancing করতে হলে ভার্সিটির প্রথম ৩ বছর নয়। ভার্সিটির প্রথম ৩ বছর শুধু cse রিলেটেড জিনিস পত্র শেখায় সময় দেয়া উচিত। প্রশ্নঃ প্রোগ্রামিং কনটেস্ট এ ইন্সপারেশন এর কেউ আছে , কাউকে ফলো করতে ? উত্তরঃ প্রোগ্রামিং কন্টেস্ট এর ইন্সপারেশন হল শিপলু স্যার। আমার ৪ বছরের পুরাটা সময় ধরতে গেলে স্যারের হাত ধরে চলতে শেখা। প্রোগ্রামিং কন্টেস্ট এর বেশিরভাগ জিনিস শিখেছি স্যারের কাছ থেকে। আর সবসময় স্যারকে ফলো করার চেষ্টা করতাম। স্যারের একটা জিনিস ভাল লাগে সেইটা হল কত স্টুপিডের মত কত উল্টাপাল্টা কাজ করেছি, কোনদিন বকা দেয় নাই:P :P প্রশ্নঃ নতুন যারা কনটেস্ট শুরু করতেছে তাদের কোন সাজেশন ? কিভাবে ভাল করবে ? উত্তরঃ যারা নতুন কন্টেস্ট করতেছে, তাদের জন্য সাজেশন হল লেগে থাক। প্র্যাকটিস বন্ধ করিও না, সফলতা আসবেই। প্রশ্নঃ অনেক সময় দেখা যায় কয়েকদিন কারো কনটেস্ট ভাল না হইলে অনেক এ হতাশ হয়ে কনটেস্ট ছেড়ে দেয় বা অন্যভাবেও বলা হয় সব কনটেস্টেন এর লাইফে হতাশার একটা পিরিয়ড থাকে , এই সময় কিভাবে নিজেকে মোটিভেট করা উচিত ? উত্তরঃ কন্টেস্ট ভাল না হওয়া/ আমি যেটাকে বাঁশ বলি tongue emoticon tongue emoticon:P সেইটা কি জিনিস আমার cf আইডি দেখলে বুঝা যায়। তারপর এত এত বাঁশ খাওয়ার পরেও কন্টেস্ট করা বন্ধ করি নাই। হতাশ হওয়া যাবে না। হতাশ হলে উল্টো বিপদ। হতাশ হলে পার্ফমেন্স দিন দিন আরও খারাপ হতে থাকে। যদি কোন কন্টেস্ট খারাপ হয় সেইটায় কি ভুল করেছ, বা যেগুলা সল্ভ হয় নাই সেইগুলা সল্ভ করার চেষ্টা কর। শিপলু স্যার সব সময় একটা কথা বলতেন আমি যখন cf শুরু করি, র‍্যাঙ্ক লিস্ট দেখ না, কন্টেস্ট শেষে তোমার লেভেলের যেসব প্রবলেম ছিল সেইগুলা সল্ভ করতে পেরেছ কিনা সেইটা দেখ। আর আমার মতে একটা অনেক গুলা অনলাইন কন্টেস্ট খারাপ হওয়া মানে, অফলাইন প্র্যাকটিসের অভাব। সুতরাং হতাশ হয়ে কন্টেস্ট অফ করে দিয়ে সেলেন্ডার করার চেয়ে, ভুল খুঁজে বের করে কাম ব্যাক করাই বুদ্ধিমানের কাজ। প্রশ্নঃ প্রোগ্রামিং বাদে কোন হবি ? ফ্রি টাইমে কি কর ? উত্তরঃ প্রোগ্রামিং বাদে আর যদি শখের কিছু থেকে থাকে সেইটা হল সাইক্লিং করা :P tongue emotico আর অবসর সময় দেখা যায় কখনও কোন ব্লগ/বই পড়ি অথবা টিভি সিরিজ দেখি।

Greedy Part - 3

greedy Algorithm এর উপর লিখা আমার আগের  পোষ্টগুলা এই লিঙ্ক এ পাওয়া যাবে ।

এই post এও কিছু interesting greedy problem নিয়ে  আলোচনা করর ।


Eternal Victory ::

এই প্রবলেমটাতে আসলে যা বলা হইছে আমাদের একটা ট্রি দেওয়া আছে (বিভিন্ন সিটি নিজেদের মধ্যে কনেক্টেড হয়ে ট্রি করছে ) । এই ট্রি এর সবগুলো নোডে আমরা মিনিমাম কত cost এ visit করতে পারি । আমরা ১ নাম্বার নোড থেকে যাত্রা স্টার্ট করব এবং যেকোন নোড এই থামতে পারব ।

যেহেতু এইটা ট্রি এর মানে হইল আমাদের কোন লুপ নেই । লুপ না থাকার কারণে আমরা জানি যে যেকোন একটা লিফ নোড এ আমরা থামব এবং  এইখানে কতগুলো রাস্তা আমাদের দুইবার যাতায়াত করতে হবে । যেহেতু আমরা সব থেকে মিনিমাম cost বের করছি আমরা চাব ১ নাম্বার নোড থেকে এর সব থেকে দুরের নোডে যেতে যে যে রাস্তা দিয়ে যাইতে হয় তারা যেন একবারই ভিজিট হয় আর বাকি সব নোড হবে দুইবার করে ।

	const int NX = 1e5 + 10 ;
	Long dis[ NX ] ;
	vector < int > adj[ NX ] , cost[ NX ] ;
	int n ;
	void solve()
	{
	cin >> n ;
	Long ans = 0 ;
	rep ( i , n - 1)
	{
	int x , y , c ;
	cin >> x >> y >> c ;
	adj[x].pb( y );
	adj[y].pb( x );
	cost[x].pb( c );
	cost[y].pb( c );
	ans += ( c + c );
	}
	For( i , n ) dis[i] = ( 1e12 );
	dis[1] = 0 ;
	priority_queue < pair < Long , int > > pq ;
	pq.push( mp( 0 , 1 ) ) ;
	while( !pq.empty() )
	{
	pair < Long , int > now = pq.top();
	pq.pop();
	int x = now.ss ;
	Long c = now.ff * -1 ;
	int sz = adj[x].size();
	rep( i , sz )
	{
	int u = adj[x][i];
	Long cc = cost[x][i];
	if( dis[u] > dis[x] + cc )
	{
	dis[u] = dis[x] + cc ;
	pq.push( mp( -dis[u] , u ) );
	}
	}
	}
	Long mx = 0 ;
	for ( int i = 1 ; i <= n ; i++ ) mx = max( mx , dis[i] );
	ans -= mx ;
	cout << ans << endl ;
	}

view raw Greedy31.cpp hosted with ❤ by GitHub

ReplacingDigit ::
টপ কোডারের এই প্রবলেম এ বলা হয়েছে আমাদের কিছু product এর প্রাইজ ট্যাগ দেওয়া হবে এবং সাথে কিছু এক্সট্রা ডিজিট ও দেওয়া হবে আমারা চাইলে আমাদের কোন প্রোডাক্টের প্রাইজ ট্যাগর কোন ডিজিটকে বদলাতে পারি কিন্ত্ আমাদের কোন এক্সট্রা ডিজিট আমরা আমাদের প্রোডাক্টের প্রাইজ ট্যাগর সাথে যোগ করতে পারব না ।আমাদেরকে বলতে হবে হাইস্ট কত আমরা এই প্রোডাক্টগুলো থেকে পেতে পারি । লিমিট এ একটা জিনিস বলা আছে হাইস্ট 10^6 প্রোডাক্টের প্রাইজ হতে পারে ।
যদি ধরে নেই আমরা গ্রিডি সল্ভ করব তাহলে গ্রিডি সলুশ্যন এর সব থেকে গুরুত্বপূর্ণ পয়েন্ট হচ্ছে current stage এর highest possible gain । কি কি ফ্যাক্টর তা আমাদের দিবে এইটা আমাদের বের করতে হবে ।

১। most right digit থেকে আমরা দেখব আমরা কোন নাম্বার চ্যাঞ্জ করে বেশি লাভ করতে পারি কিনা ।
২। যদি পারি তাহলে সবথেকে smallest most right digit কে আমরা all possible extra digit থেকে highest possible value digit দ্বারা replace করব যা আমাদের highest profit ensure করবে ।
৩। একই প্রসেস আমরা সব ডিজিট এর জন্য ব্যাবহার করব ।

এখন আমাদের এই ব্যাপারগুলাকে  একসাথে merge করে answer বের করতে হবে ।

	class ReplacingDigit
	{
	public:
	int getMaximumStockWorth(vector <int>, vector <int>);
	};
	int mul[ 10 ];
	vector < int > digit[ 10 ];
	int ReplacingDigit::getMaximumStockWorth(vector <int> A, vector <int> D)
	{
	int m = 1 ;
	for( int i = 0 ; i < 8 ; i++ )
	{
	mul[i] = m ;
	m *= 10 ;
	}
	int sz = A.size();
	for( int x = 0 ; x < sz ; x++ )
	{
	int num = A[x];
	int idx = 0 ;
	while( num > 0 )
	{
	digit[idx++].pb( num % 10 );
	num /= 10 ;
	}
	}
	int total = 0 ;
	int idx = 8 , add = 9 ;
	for( int i = 7 ; i >= 0 ; i-- )
	{
	sz = digit[i].size();
	if( sz == 0 ) continue ;
	sort( digit[i].begin() , digit[i].end());
	while( idx >= 0 && D[idx] == 0 )
	{
	idx--;
	add--;
	}
	for( int j = 0 ; j < sz ; j++ )
	{
	if( idx == -1 || digit[i][j] >= add )
	{
	total += ( mul[i] * digit[i][j]);
	}
	else
	{
	total += ( mul[i] * add );
	D[idx] -= 1 ;
	while( idx >= 0 && D[idx] == 0 )
	{
	idx--;
	add--;
	}
	}
	}
	}
	return total;
	}

view raw greedy_3_2.cpp hosted with ❤ by GitHub

To Add or Not to Add::
কোডফরসেস এর এই প্রবলেম এ বলা হয়েছে আমাদের একটা N সংখ্যক number এর array দেওয়া আছে এবং সাথে একটা নাম্বার K ও দেওয়া আছে । K এর কাজ হল , আমরা K সংখ্যকবার চাইলে array এর কিছু element ( যদি খালি একটাও হয় ) ১ করে বাড়াতে পারি । আমাদেরকে এই array থেকে highest frequency এর নাম্বার প্রিন্ট করতে হবে , যদি একাধিক থাকে তাওলে সবচেয়ে ছোট নাম্বার প্রিন্ট করতে হবে ।

এই প্রবলেমটা অনেকভাবে সল্ভ করা যেতে পারে  এর মধ্যে two pointer technique use করে আমরা খুব সহজে করতে পারি ( two pointer technique কি এইটা জানা থাকলে এই ব্লগটা আগে পড়ে আসতে হবে ) । এরপর range এর মধ্যে commutative sum এর মাধ্যমে কোন নাম্বার এর জন্য হাইস্ট কতবার নাম্বারটা হতে পারে তা আমরা বের করতে পারি ।

প্রথমে আমরা sort করে নিব array টাকে , sort করাটা important কারন আমরা এর উপর range উপর কোন নাম্বার নিয়ে তা কতটা বানানো সম্ভব query করব , যা শুধু মাত্র একটা নাম্বার বানানোর জন্য এর সমান এবং সামান্য ছোট নাম্বারগুলাকে এর সমান বানাতে minimum কতটা adding দরকার হবে যা sorting sequence থেকেই আমরা পাই ।

	const int NX = 1e6 + 10 ;
	Long inp[ NX ] , sum[ NX ] ;
	int n , m ;
	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
	n = II , m = II ;
	rep ( i , n )
	{
	inp[ i ] = LL ;
	}
	sort ( inp , inp + n );
	Long freq = -1 , ans , tmp ;
	int p = 0 ;
	rep ( i , n )
	{
	sum [ i + 1 ] = inp[ i ] + sum [ i ] ;
	while( (( inp[i] * (Long) ( i - p + 1 ) ) - ( sum [ i + 1 ] - sum[ p ] ) )> m ) p++;
	if( freq == -1 || freq < ( i - p + 1 ) )
	{
	ans = inp[ i ] ;
	freq = i - p + 1 ;
	}
	}
	cout << freq << " " << ans << endl ;
	return 0;
	}

view raw greedy_3_3.cpp hosted with ❤ by GitHub

two pointer এর মাধ্যমে প্রবলেম সল্ভ এর জন্য আমাদের দুইটা range পয়েন্ট থাকে , starting point and end point . আমরা যেহেতু iterative করে array এর প্রতিটি ভ্যালু নিয়ে দেখছি আমাদের উপরের কোডের 'i' হচ্ছে end point এবং 'p' হচ্ছে আমাদের starting পয়েন্ট । এখন p পয়েন্ট থেকে i পয়েন্ট পর্যন্ত যে নাম্বারগুলা আছে তাদের যদি আমরা 'i' পয়েন্ট এ যে নাম্বারটার সমান করতে চাই তাহলে যতবার adding operation লাগবে তা K( কোডে m ) এর ছোট বা সমান হচ্ছে কিনা তা 26 number লাইনের while loop দিয়ে চেক করা হচ্ছে , পরে answer update করা যায় কিনা check করা হচ্ছে ।

উপরের কোডের একটা মাত্র সাইন চ্যাঞ্জ করলে তা minimum number থেকে maximum number পাওয়া যাবে highest frequency এর জন্য , কোন সাইনটা চ্যাঞ্জ করতে হবে তা পাঠকদের খুঁজে বের করার জন্য ছেড়ে দিলাম ।

এই লিখাটা আর বড় করছি না , আমার মনে হয় প্রোগ্রামিং কনটেস্ট এ আগ্রহ থাকার পরও প্রোগ্রামিং কনটেস্ট এ অনেক এর ভাল করা সম্ভব হয় না quality problem solve না করার কারনে । ১০০টা same logic এর প্রবলেম সল্ভ করে যে লাভ টা হয় না , তার চেয়ে ৫টা different logic এর প্রবলেম সল্ভ করে অনেক কিছু জানা হয় । এখন একজনের পক্ষে হয়তো এই ৫টা different problem এর আইডি জানা কস্টকর , যে কাজটা একজন কোচ হয়তো করে দেন বা কোন সিনিয়র বড় ভাই ভার্সিটির যিনি নিজে অনেক টাইম দিছেন এইসব এর পিছনে । ভাল প্রবলেম এর আইডি মনে রাখা এমন মাঝে মধ্যেই এই প্রবলেম গুলার সল্যুশন লজিক দেখা important . যেইটা আমি নিজে অনেক পরে বুঝেছি বলে এখনও মাঝে মধ্যে আফসোস হয় । সব ভার্সিটির ট্রেনিং প্রসেস এক হওয়া সম্ভব না , এখন আমারা যারা নিজেরা সাফার করছি বা করিও নেই ( অনেক ভাল যারা করেছেন এবং করছেন ) তাদের দায়িত্ব হল এই প্রবলেম গুলার আইডিয়া বলে দেওয়া , সম্ভব হলে কিছু সল্ভ লজিক সহ যেন অন্য যে কেউ তা থেকে নিজে নিজে একটা শিখতে পারে । চীনা এবং রাশিয়ানরা কেন প্রোগ্রামিং কনটেস্ট এ এত ভাল করে তা একটা ভাল কারন ট্রেনিং ম্যাটেরিয়াল নিজেদের ভাষায় অনেক বেশি তাদের , যেইটা এখনও বাংলাতে নেই । যদি আমি গত ৪ বছর যাবত অনেক চ্যাঞ্জ দেখছি , আমি যখন স্টার্ট করি এক ফাহিম ভাইয়া এর ব্লগ বাদে কিছু ছিল না , পরে সাফায়াত ভাইয়া এখন প্রায় ব্যাসিক সব কিছু নিয়ে লিখে ফেলেছেন কিন্ত্ এখনো প্রবলেম ম্যাটেরিয়াল নিয়ে সবাই আগ্রহী না । আমার ব্লগের মাধ্যমে কারো কোন উপকার হইতে এইটা অনুরোধ থাকবে আপনিও বাংলাতে প্রবলেম সল্ভিং নিয়ে লিখা শুরু করুন । ইনশাল্লাহ আইওআই এবং এসিএম এর গোল্ড খুব একটা বেশি দূরে নয় :) 

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

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

Programming Interview with A Asif Khan Chowdhury

ইন্টারভিউ সিরিজের আগের লিখাগুলা এই লিঙ্কে পাওয়া যাবে । প্রোগ্রামিং কন্টেস্ট এর ব্যাপারে প্রথম কিভাবে জানছিলা মনে আছে ?

প্রোগ্রামিং কনটেস্টের ব্যাপারে শুনছি প্রথম রুয়েটে এসেই। কিন্তু প্রোগ্রামিং ল্যাংগুয়েজ ব্যবহার করে প্রবলেম সলভিং করার ব্যাপারটা জানছিলাম HSC এর প্রথম বর্ষেই। আমার একটা ফ্রেন্ড শুভর মাধ্যমে। সেই প্রথম আমাকে কম্পিউটার সায়েন্সের মজাটা বুঝিয়েছিলো। তার সাথে থেকেই বিভিন্ন ছোটখাটো প্রবলেম সলভ করছিলাম, যদিও তখন competitive programming এর বিশাল জগৎ সম্পর্কে কিছুই জানতাম না। DOS স্ক্রীনে C দিয়ে “Hello World” লিখেই বুঝতে পারছিলাম যে এটা নিয়েই পড়াশুনা করতে চাই।

প্রথম অনসাইট কনটেস্ট কথা মনে আছে ?

আসলে জীবনের প্রথম কনটেস্টই ছিলো ICPC. তখন রুয়েট থেকে আসার মত টীম ছিলো না খুব বেশি। তাই সুযোগ পেয়ে গেছিলাম। ওই সময় কনটেস্ট PC^2 এ হতো। মজার বিষয় হলো আমরা আগে কখনও PC^2 দেখিও না। অনেক সময় গেছিলো PC^2 এ সাবমিট কিভাবে করে সেটা বুঝতে। :D

প্রোগ্রামিং কনটেস্ট এ কোন মজার কোন স্মৃতি আছে যেইটা মনে করলে এখনো হাঁসি পায় ?

মজার একটা স্মৃতি ছিলো ICPC-2013 তে। ঢাবির শাফায়েত ভাইয়াদের টীম কনটেস্ট শেষ হওয়ার এক ঘন্টা আগে ৬ প্রবলেম সলভ করে সবার আগে ছিলো। ভাইয়া আমাদের সামনেই বসেছিলেন, আমি উনাকে উঠে দাড়িয়ে তখনই কংগ্রাচুলেট করা শুরু করছিলাম। ভাইয়া রীতিমত লজ্জায় পড়ে গেছিলেন এটা দেখে। কনটেস্ট শেষ হওয়ার পর দেখি ভাইয়াদের টীম আর একটা সলভ করতে পারে নাই, SUST_Attoprottoyee ৭ টা প্রবলেম সলভ করে চ্যাম্পিওন হয়েছিলো। কনটেস্ট শেষে শাফায়েত ভাই আমার দিকে একটা দৃষ্টি নিয়ে তাকিয়েছিলো সেটা দেখে খুব লজ্জায় পড়ছিলাম। তারপর ভাইয়ার সাথে লজ্জায় আর কখনও কথা বলতে পারি না। কথাগুলো মনে পড়লে এখনও খুব মজা (এবং লজ্জাও) পাই।

কি টাইপের প্রবলেম সল্ভ করতে বেশি  ভাল লাগে ?

DP এবং algorithmic প্রবলেম সলভ করতে খুব বেশি ভালো লাগে। তবে যেকোন টপিকেই নতুন কিছু শিখে ম্যারাথন দিয়ে প্রবলেম সলভ করতে পছন্দ করি।

কোন প্রবলেম সল্ভ এর সময় "Thinking Process" কি থাকে প্রবলেম পড়ার পর ?

শাহরিয়ার মঞ্জুর ভাইয়ের কাছ থেকে প্রবলেম সলভ করার একটা পদ্ধতি শিখছিলাম, LDC (Learn, Divide, Convert). Basically এই পদ্ধতির প্রথম ধাপে প্রবলেমটা ভাল ভাবে শেখা, testcases নিয়ে নড়াচড়া করে দেখা হয় কিভাবে সলুশন আসতেছে। দ্বিতীয় ধাপে প্রবলেমটাকে ছোট ছোট sub-problem এ ভাগ করা হয়। কোন একটা sub-problem যদি মনে হয় সলভ করার আইডিয়া নাই তাইলে প্রবলেম skip করা। তৃতীয় ধাপে আছে convert, এটার মানে হলো sub-problem গুলো known বিভিন্ন প্রবলেমের সাথে মিল রেখে step-by-step সলভ করার চেষ্টা করা।

কোন প্রবলেম Accepted না হলে কি কি ব্যাপার দেখেন ?    

কয়েকটা কাজ করে দেখি যেমন, প্রথমে type check করি, overflow হয় কিনা দেখি, constrains গুলো ভাল ভাবে চেক করি। যদি তাতেও কাজ না হয় তখন প্রবলেমটাতে খুটিনাটি বিষয়গুলো ঘেটে দেখি। তারপর brute force কোড করি তারপর random case এর জন্য brute force আর আমার সুলশনের সাথে মিলিয়ে পার্থক্যগুলো দেখি।

অনেক সময় দেখা যায় কয়েকদিন কারো কনটেস্ট ভাল না হইলে অনেক এ হতাশ হয়ে কনটেস্ট ছেড়ে দেয় বা অন্যভাবেও বলা হয় সব কনটেস্টেন এর লাইফে হতাশার একটা পিরিয়ড থাকে , এই সময় কিভাবে নিজেকে মোটিভেট করা উচিত ?

আমার পরিচিত এমন কোন প্রবলেম সলভার দেখি নাই যারা প্রবলেম সলভিং করতে গিয়ে মাঝপথে হতাশ হয় নাই। Competitive programming এবং হতাশা হাতে হাত রেখে চলে। এই সময় যারা ছেড়ে দিয়েছে তাদের অনেকের সাথে কথা বলে দেখেছি, সবারই একটাই মন্তব্য থাকে তারা এটা ছেড়ে দিয়ে ভুল কাজ করেছে, এই ব্যাপারটা মাথায় রাখলে মনে হয় মোটিভেটেড থাকা যাবে। আবার যারা ফলাফলের আশায় প্রবলেম সলভিং করে তারা আরও বেশি হতাশ হয়। প্রবলেম সলভিং ক্রিকেট-ফুটবল-টেবিল টেনিস ইত্যাদি খেলার মত করেই দেখা উচিৎ। তুমি মজা পাও বলে প্রবলেম সলভিং করো, রেজাল্টের আশায় না। :)

আইওআই যারা না করে ভার্সিটি থেকে কনটেস্ট করে তারা দেখা যায় আইওআই যারা করেছেন তাদের থেকে পিছাইয়া থাকে , অনেক সময়ই পিছাইয়াই থাকে । যারা ভার্সিটি তে মাত্র কনটেস্ট নিয়ে জানল তাদের কি করা উচিত এই দুরুত্ব কমানোর জন্য ?

এটা ঠিক যে তারা পিছিয়ে থাকে। তবে এই পিছিয়ে থাকাটা রিকভার যায় না এটা ভাবাটা ভুল হবে, শুধু dedication টা বেশি থাকতে হবে অন্যদের চেয়ে। বাংলাদেশের competitive programming এ যত কিংবদন্তি আছে তাদের সিংহভাগই তো IOI করেন নাই।

বাংলায় ব্লগ প্রোগ্রামিং নিয়ে খুব একটা নেই , আসিফের হজবরল কিভাবে শুরু করার চিন্তা করলা ? যারা কনটেস্ট করে তাদের ব্লগিং কিভাবে তাদের হ্যাল্প করতে পারে , নতুন যারা ব্লগ লিখছে তাদের জন্য কোন সাজেশন ?

প্রবলেম হলো আমি নতুন কিছু শিখলে সেটা অন্য কাওকে না জানায়ে থাকতে পারি না। :P রুয়েটে তখন খুব বেশি প্রবলেম সলভার ছিলো না এ সব বিষয়ে আলাপ-আলোচনা করার জন্য। তাই কিভাবে জানাবো কি শিখছি? তখন মাথায় আসলো ব্লগিং করার কথা। ব্লগিং করার শুরুটা করি শাফায়েত ভাই, জুবায়ের ভাই এবং ফাহিম ভাইয়ের  ব্লগপোস্টগুলো পড়ার পর। খুবই ভালো লাগতো লিখতে, এবং অন্যদের প্রশ্নের উত্তর দিতে। ব্লগিং করে অনেক ফ্রেন্ড পেয়েছি ভাল ভাল, শিখতে পারছি অনেক কিছু। :)

বাংলায় ভাল ব্লগের খুবই অভাব। তোমরা যারা ব্লগিং শুরু করছো তারা সব সময় মাথায় রেখো যে তোমরা হাতে গোণা কয়েকজন প্রোগ্রামারদের মধ্যে একজন যে নিজেদের জ্ঞান সবার মাঝে ছড়িয়ে দিতে প্রস্তুত আছো। সব থেকে বড় কথা তোমরা যে টপিক নিয়েই লিখ না কেন, লিখলে তোমার জ্ঞান সাধারনের চেয়ে অনেক বেশি বাড়বে কম সময়ে।

প্রোগ্রামিং কনটেস্ট এ ইন্সপারেশন এর কেউ আছে , কাউকে ফলো করতে ?

আমি মোটামুটি সবাইকেই, যারা প্রবলেম সলভ করতে পছন্দ করেন তাদেরকে, ইন্সপারেশন হিসেবে দেখি। তবে তালিকায় প্রথমে যারা আছেন তারা হলেন শান্ত ভাইয়া, শাহরিয়ার মঞ্জুর ভাইয়া, রুয়েটের সামাদ ভাইয়া (তাকে ছাড়া হয়তো আমরা কেও competitive programming জড়িত হইতেই পারতাম না), মইনুল শাওন, সাকিব, মারুফ, ধনঞ্জয়, শাকিল ( :) ), শাফায়েত ভাইয়া, জুবায়ের ভাইয়া, নাফিস এবং আরও অনেককেই।

নতুন যারা কনটেস্ট শুরু করতেছে তাদের কোন সাজেশন ? কিভাবে ভাল করবে ?

আসলে কনটেস্টে ভাল করার কোন শর্টকাট কেও দেখাতে মনে হয় পারবে না। প্রচুর প্রবলেম সলভ করতে হবে ভাল করতে হলে। অনেক টেকনিক আর অ্যালগরিদম শিখতে হবে। আর অবশ্যই যেটা মাথায় রাখতে হবে প্রবলেম সলভাররা অন্যদেরকে সাহায্য করতে সব সময় প্রস্তুত থাকে। একা একা কোন জিনিস শিখতে অনেক সময় লাগতে পারে, সেখানে যারা আরও বেশি এক্সপেরিয়েন্সড তাদের কাছ থেকে শিখে নিলে সময়টা অনেক কম লাগবে। এমনকি প্রবলেম সলভারদের জীবনে করা ভুলগুলো শুনলেও অনেক কিছু শিখতে পারবে, অনেক ভুল আগে থেকেই শুধরে নিতে পারবে। সুতরাং সব সময় শেখার জন্য open mind রাখা উচিৎ।

রুয়েট এর কনটেস্ট কালচার তৈরির জন্য অনেক কষ্ট করছ এবং করে যাচ্ছ। আগামী ২/৩ বছর পর রুয়েটকে কোথায় দেখতে চাও ?

রুয়েট থেকে অনেক কিছু পেয়েছি, শিখতে পারছি। স্বপ্ন ছিল একদিনের যেদিন দেখবো আমারই ছোট ভাইগুলো WF করতেছে। এই স্বপ্নের জন্য যতটুকু করতে পেরেছি ততটুকু করেছি। তবে আরও অনেক কিছু করার ইচ্ছা ছিলো যেগুলো করে যেতে পারি নাই।

রুয়েটের জুনিয়ররা এখন অনেক আগ্রহী কনটেস্ট করতে। এত বিশাল সংখ্যক কনটেস্টেন্ট রুয়েট কখনও দেখে নাই এর আগে। তাদের পরিশ্রম দেখে অনেক ভালই লাগে। ইনশা’আল্লাহ সামনে ১-২ বছরের মধ্যে অনেক ভাল একটা পজিশনে দেখতে পারবো রুয়েটকে। :)

প্রোগ্রামিং বাদে কোন হবি ? ফ্রি টাইমে কি করেন ? 

আমি প্রচুর মুভি আর টিভি সিরিজ দেখি ফাকা সময়ে। ইদানিং youtube এ মুভি ট্রেইলারস, টেক, সায়েন্স videos ইত্যাদি দেখে ফাকা সময় কাটাচ্ছি। :P

Programming Interview with Ahmad Faiyaz

ইন্টারভিউ সিরিজের আগের লিখাগুলা এই লিঙ্কে পাওয়া যাবে ।

প্রশ্ন ঃ ভাইয়া প্রোগ্রামিং কনটেস্ট এর ব্যাপারে প্রথম কিভাবে জানছিলেন মনে আছে ?

উত্তর ঃ ভার্সিটিতে যখন এডমিট হইছি তখনও জানতাম না । এমনকি এক বছর ধরে ক্লাস করছি তখনও জানতাম না । একদিন নতুন এক ফ্যাকাল্টি আসল , নোভা আহমেদ উনি বললেন যে নর্থ সাউথ এ এসিএম এর ক্লাস শুরু হবে । তখন জানলাম এসিএম আইসিপি কি জিনিস । আমি তখন দ্বিতীয় বর্ষে ।

প্রশ্নঃ প্রথম অনসাইট এর কথা মনে আছে ?

উত্তরঃ হাঁ , অবশ্যই । প্রথম কনটেস্ট ছিল সাস্ট সিএসই ফিস্টা - ২০১১ , এনএসইউ থেকে ৫টা টিম গেছিল । আমার টিমের নাম ছিল , NSU strikers. আমাদের কনটেস্ট ভাল হয় নাই , একটা মিলাইছিলাম মনে হয় । তবে এক্সপেরিয়ান্স অসাধারণ ছিল , ৫ ঘণ্টা ক্যামনে গেছিল মনে নাই ।

প্রশ্ন ঃ ভাইয়া ভার্সিটির সেকেন্ড ইয়ারে এসে কনটেস্ট এর ব্যাপারে জানা কি আপনার মনে হয় আপনি অনেক দেরি করে ফেলছিলেন ? সচরাচর আইওআই যারা করে থাকে তাদের সাথে সব সময় একটা দূরত্ব থেকে যায় ?

উত্তর ঃ  হাঁ হাঁ , I regret . ঐসময় আমি রিজুল ( DU ) এবং BUET এর সাকিবকে চিনতাম । তাদের দুইজনই Uva তে ব্যাপক সল্ভ করে ফেলছিল আর আমি মাত্র 3N + 1 সাবমিট করছি । যদিও সাকিব IOI গেছিলাম , তখন ব্যাপারটা জানতাম না আর রিজুল অনেক সল্ভ করে ফেলছিল Uva তে । ওদের হারানো জন্য অনেক সল্ভ করা লাগত তাই Uva বেশি সল্ভ করি নাই :p তারপর লাকি ভাবে লাইট ওজি এসে গেল , এইখানে সল্ভ স্টার্ট করে দিলাম । অনেক ইন্টারেস্ট ছিল এই ব্যাপারে তাই গ্যাপ আছে এইটা নিয়ে চিন্তা করতাম না । জাস্ট সল্ভ করে গেছি ।

প্রশ্নঃ লাইট ওজির শুরুর দিকে যখন ফোরাম অনেক এক্টিভ ছিল আপনি অনেক টেস্ট কেইজ দিতেন ? এবং আপনি ব্লগ ও লিখতেন যাতে অন্যদের সুবিধা হয় । আমি অনেক উপকৃত হইছিলাম যখন আমি লাইট ওজি সল্ভ করতাম । অনেকে এইসব আগ্রহী হয় না , ব্লগ লিখা বা ফোরামে পোস্ট । এই ব্যাপারগুলা ভাইয়া কিভাবে দেখেন ?ভার্সিটিতে এসে শুরু করে ?

উত্তরঃ টেস্ট কেইজ করা অনেক মজার ব্যাপার আর মানুষ এর কোড থেকে নতুন অনেক কিছু শিখা যায় , কি ভুল করতেছে ধরতে পারলে নেক্সড টাইম আমি হয়তো এই ভুল করব না । অনেক কর্নার কেইজ চিন্তা করা যায় । আর ব্লগ লিখা হচ্ছে নিজের জন্য । যখন তুমি কাউকে কিছু বুঝাইতে যাবা  you need to know that topic very well , আমি একটা ব্লগ লিখছিলাম বাই কানেক্টেড কম্পোনেন্ট নিয়ে , লিখতে গিয়ে আরো ভালমত বুঝছি জিনিসটা । মানুষ question করবে তুমি নতুন আরো কিছু জানবা এইসব থেকে , আমি হয়তো আগে ভাবি নাই । অনেক এ ব্লগ এ কোড দিয়ে দেয় । আমি এইটা discourage করব । এতে অনেক এ ব্লগ না বুঝে কোড কপি পেস্ট করে ।

প্রশ্ন ঃ কি টাইপের প্রবলেম সল্ভ করতে ভাইয়া বেশী ভাল লাগে ?

উত্তর ঃ Data Structure, String, Graph ( BCC, SCC )।

প্রশ্ন: ভাইয়া   কোন প্রবলেম সল্ভ এর সময় "Thinking Process" কি থাকে প্রবলেম ?

উত্তর ঃ ক্যাটেগরিতে ফালানোর ট্রাই করি কি টাইপের প্রবলেম । এরপর দেখি এইরকম কিছু আগে করছি কিনা । CF এ দেখছি অনেক এই বলছে ম্যাক্সিমাম প্রবলেম অন্য কোন প্রবলেম এর ভ্যারিয়েশন । যদিও তাও না বের করতে পারি তাহলে প্রবলেমটা আরো সিমপ্লিফাই করতে পারি কিনা তা দেখি , ছোট ছোট টাস্ক এ ভাগ করে তারপর এইগুলাকে দিয়ে কিভাবে সল্যুশন করা যায় - যা আসলে শিখছিলাম ফাহিম ভাইয়ার ( Iqram Mahmud - Smilitude ) কাছ থেকে ।

প্রশ্নঃ কোন প্রবলেম Accepted না হলে কি কি ব্যাপার দেখেন ?
উত্তরঃ ঐ যে কর্নার কেইজ গুলা চিন্তা করি , অনেক রকম ভ্যালু নেই দেখি কি হবার কথা কি হচ্ছে। মাঝে মধ্যে সময় থাকলে brute force করি । দেখি কেন ভুল হচ্ছে । যদিও তাও ভুল না পাই , এল্গো রিভাইস দেই । ইমপ্লিমেন্টেশন চেক করি । ও হাঁ অবশ্যই প্রবলেম আবার পড়ি ।

প্রশ্ন ঃ অনেক সময় দেখা যায় কয়েকদিন কারো কনটেস্ট ভাল না হইলে অনেক এ হতাশ হয়ে কনটেস্ট ছেড়ে দেয় বা অন্যভাবেও বলা হয় সব কনটেস্টেন এর লাইফে হতাশার একটা পিরিয়ড থাকে , এই সময় কিভাবে নিজেকে মোটিভেট করা উচিত ?

উত্তর ঃ ও হাঁ , আমিও দুইবার ছেড়ে দিছিলাম । একবার ন্যাশনাল কনটেস্ট মিস করছিলাম কনটেস্ট ছেড়ে দেবার কারনে । যাই হোক মোটিভেশন এর কিছু নাই , আমার কাছে মনে হইছে তোমার চান্স ৫বার , নিতে সমস্যা কি ? আর এই জিনিসটা হ্যাম্পার করতেছে না আমার ডেইলি লাইফ বা  একাডেমিক এ । যদিও একটু সিজিপিএ কমছে এইটা আমার দোষেই । এই তো জাস্ট ট্রাই করে যাওয়া যাতে কখনো মনে না হয় আরো একবার চান্স ছিল নেই নাই , নিলে হয়তো ভাল করতে পারতাম ।

প্রশ্ন ঃ প্রোগ্রামিং কনটেস্ট এ ইন্সপারেশন এর কেউ আছে , কাউকে ফলো  করতেন ?

উত্তর ঃ হা .. Iqram Mahmud (Fahim ভাই), Mahmud Ridwan ভাই ।

প্রশ্নঃ প্রোগ্রামিং কনটেস্ট এ কোন মজার কোন স্মৃতি আছে যেইটা মনে করলে এখনো হাঁসি পায় ?

উত্তরঃ হাঁ , এইটা ডেফোডিল এর কনটেস্ট ২০১১ এ ছিল । আমরা দুইটা করছিলাম বা একটা প্রবলেম আর মিলাইতে পারতেছিলাম না । আমাদের বাম পাশে ছিল DU এর জুবায়ের ভাইদের টিম । উনারা বলতে ছিল যে একটা প্রবলেম কিভাবে মিলাইছে । আমি পাশে ছিলাম , হাল্কা শুনছি সিমুলেশন করে দেখলেই হয় । তখন মাথায় ঢুকছে সিমুলেশন করে কিভাবে হবে , পরে কনটেস্ট শেষ এর ৫মিনিট আগে এসি :p এইজন্যই আমি আমার টিমমেটদের সবসময় বলি আস্তে ডিসকাস করতে ।

প্রশ্ন ঃ এই বছর ওয়াল্ড ফাইনালের জন্য আপনাদের টিম এর প্রিপারেশন ক্যামন ?

উত্তর ঃ এই তো চলতেছে , ওয়াল্ড ফাইনাল এর সেটগুলা practice করা হইছে । নতুন অনেককিছু শিখতেছি , জানতেছি । hopefully world final ভাল হবে ।

 প্রশ্ন ঃ যদিও এখনও অনেক টাইম বাকি আছে , যারা এই বছর রিজিওনাল করবে সেই টিমগুলার জন্য ভাইয়া কোন সাজেশন ?

উত্তর ঃ আমি কি বলব । সাজেশন এর কিছু নাই । just don't lose the hope . solvable problem solve করাই আসল ।

প্রশ্ন: নতুন যারা কনটেস্ট শুরু করতেছে তাদের কোন সাজেশন ? কিভাবে ভাল করবে ?

উত্তর ঃ মেইন সাজেশন হইল টাইম মেনেজম্যান্ট করা । ভার্সিটি এর ক্লাস এর পর যে টাইম পাওয়া যায় তা দিয়ে study , movie দেখা , আড্ডা মারা , ডেভেলপমেন্ট এর কাজ করা , প্রবলেম সল্ভ করা সবই সম্ভব । এই স্কিলটাই ডেভেলপ করাই আসল , কেউ করলে ও সবকিছুতেই ভাল করবে । এখন নেট এ অনেক রিসোর্স আছে । সার্চ করলেই পাওয়া যায় , কারো ইচ্ছা থাকলেই হবে । খালি ইন্টারেস্ট গ্রো করতে হবে আর practice করতে হবে ।

প্রশ্ন ঃ প্রোগ্রামিং বাদে কোন হবি ? ফ্রি টাইমে কি করেন ?

উত্তরঃ software development, graphics design, photography.. আর ফ্রি টাইমে মুভি দেখি , সিরিয়াল দেখি , আড্ডা মারি , গেইম খেলি , টিউটোরিয়াল পড়ি ।

Dp part - 4

DP নিয়ে আমার আগের লিখাগুলা পাওয়া যাবে এই লিঙ্ক এ । এই পোস্টে কিছু কমন ডিপি সল্যুশন নিয়ে আলোচনা করছি ।


nth premutation :

এই প্রবলেম এ বলা হয়েছে আমাদের একটা string দেওয়া হবে আমাদের এই string এর nth permutation ভ্যালু কত হবে তা বলতে হবে । যদি তা সম্ভব না হয় আমাদের "impossible" প্রিন্ট করতে হবে । এইখানে n এর ভ্যালু হতে পারে ২^৩১ । এইখানে একটা জিনিস দেখি আমরা string এর সাইজ হতে পারে হাইস্ট ২০ লেটারে এবং সব যদি ভিন্ন ভিন্ন লেটার হয় তাহলে পারমুটাশেন সম্ভব হত n! বা ২০! । যা অনেক বড় মান , আমরা যদি built in function,  next_premutation ব্যাবহার করে যাই তাহলে এইটা সম্ভব হবে না । এখন প্রবলেমটাকে ছোট করার জন্য আমরা corner-case চিন্তা করতে পারি । প্রথম এ আছি impossible case এ , কখন কখন impossible হবে । আমরা সহজেই লেটার ফ্রিকিউয়েন্সি কাউন্ট করে দেখতে পারি আমাদের দেওয়া string থেকে কতটা permutation possible , যদি এর মান আমাদের nth value এর মান এর থেকে কম হয় আমরা সহজেই  বলে দিতে পারি যে nth-value string পসিবল না পাওয়া । এইটা আমরা permutation এর ব্যাসিক ফরমুলা থেকে পেতে পারি ।

         ( size_of_the_string ) ! / ( frequency_of_every_letter_in_that_string ) ! ......... ( 1 )

এখন মেইন পার্ট । আমারা এখন nth-value পসিবল string এর কিভাবে আমরা এই  ভ্যালুটা পাব দেখব । আমরা কোন পজিশনে কোন লেটার বসিয়ে , এই লেটার এই পজিশনে বসবে এবং  এর জন্য কতটা permutation হতে পারে তা আমরা সহজেই ( ১ ) ইকুয়েশন থেকে পেয়ে যেতে পারি । যদি এর মান আমাদের nth_value এর চেয়ে কম হয় তাহলে আমরা বুঝব আসলে এই লেটার টা এইপজিশনে বসবে না আমাদের ফাইনাল string এর যদি বসত তা হলে এর জন্য মান nth_value এর সমান বা বেশি হত । কথাগুলা অসংলগ্ন লাগতে পারে একবারে পড়লে । একটা example এর মাধ্যমে দেখলে সহজ হয়ে যাবে  ।

Say string : abc , আমাদের বলতে হবে  এর ৬ষ্ঠ পারমুটেশনের স্ট্রিংটা কি ?

যদি 'a' final string এর ফাস্ট লেটার হত তাহলে আমরা 'a' কে প্রথম পজিশনে বসিয়ে b এবং c থেকে আরো 2টা পারমুটেশন পেতে পারতাম । ( abc , acb ) , কিন্তু তা ৬ এর চেয়ে কম অর্থাৎ আমরা বলতে পারি 'a' প্রথম পজিশনে বসিয়ে আমরা আমাদের ফাইনাল string পাব না । এখন 'b' কে যদি প্রথম পজিশনে বসাই তাহলে আমরা 'b' কে বসিয়ে আরো দুইটা পারমুটেশন পাব a and c এর জন্য । ( bac , bca ) , যেহেতু 'a' এর পর 'b' আসে তাই 'a' জন্য ও মানগুলা এইখানে যুক্ত হবে । টোটাল ২ + ২ = ৪ < ৬ অর্থাৎ 'b' বসিয়েও আমরা আমাদের ফাইনাল string টা পাব না । এখন 'c' এর জন্য দেখা যাবে একই ভাবে ৪ + ২ >= ৬ তাই ফাইনাল string এর প্রথম লেটার আমরা নিশ্চিত ভাবে বলতে পারি 'c' বসবে ,  এবং 'c' বসানোর মাধ্যমে আমরা 'a' এবং 'b' বসানোর জন্য মান গুলা আমাদের ফাইনাল স্ট্রিং থেকে বাদ দিয়ে পারি । এইভাবে প্রতিটা পজিশনের জন্য আমাদের ক্যালকুলেশন করে বুঝতে হবে কোন লেটারটা বসবে ।

কোড

	//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 = 30 ;
	Long fact[NX] , nth_value ;
	int freq[NX] ;
	char inp[NX];
	void ini()
	{
	fact[0] = 1 ;
	Long i ;
	for( i = 1 ; i <= 25 ; i++ ) fact[i] = ( fact[i-1]* i);
	}
	Long occurence( int len)
	{
	Long now = fact[len];
	int i ;
	for( i = 0 ; i < 26 ; i++ ) now /= fact[freq[i]];
	return now ;
	}
	void solve(int sz)
	{
	while(sz)
	{
	Long upto = 0 ;
	bool found = 0 ;
	int i ;
	for ( i = 0 ; i < 26 && !found; i++ )
	{
	if( freq[i] == 0 ) continue ;
	freq[i]--;
	Long now = occurence(sz-1);
	if( now + upto >= nth_value)
	{
	nth_value -= upto;
	found = 1 ;
	printf("%c",i+'a');
	sz--;
	}
	else
	{
	upto += now ;
	freq[i]++;
	}
	// printf("i :: %c sz :: %d now :: %lld upto :: %lld nth :: %lld \n",i+'a',sz,now,upto,nth_value);
	}
	if( !found ) break;
	}
	puts("");
	}
	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
	int cs , t = II ;
	ini();
	for( cs = 1 ; cs <= t ; cs++ )
	{
	scanf("%s %lld",inp,&nth_value);
	// printf("hello\n");
	ms( freq , 0 );
	int sz = strlen(inp);
	// rep( i , sz ) printf(" integer :: %d \n",inp[i]-'a');
	rep( i , sz ) freq[inp[i]-'a']++;
	Long need = occurence(sz);
	printf("Case %d: ",cs);
	if( need < nth_value ) puts("Impossible");
	else solve(sz);
	}
	return 0;
	}

view raw DP441,cpp hosted with ❤ by GitHub

Be Efficient :

এই প্রবলেম এ বলা হয়েছে আমাদের n টা নাম্বার এবং আরো একটা নাম্বার m দেওয়া হবে । আমাদের বলতে হবে এই nটা নাম্বার এর মধ্যে কতগুলা নাম্বার consecutive sequence  m দ্বারা বিভাজ্য । যেমন যদি n = 3 এবং m = 3 হয় এবং n sequence numbers :  3 , 6 , 9 তাহলে মোট ..
{ 3 } , { 3 , 6 } , { 3 , 6 , 9 } , { 6 } , { 6 , 9 } , { 9 } এই  ছয়টি নাম্বার m = 3 দ্বারা বিভাজ্য ।

এইখানে একটা important point হচ্ছে m <= 10^5 . এইটা এইজন্য important আমরা তাহলে নিশ্চিতভাবে বলতে পারব যে consecutive number এর sequence এর mod value কখনই 10^5 থেকে বড় হবে না , যা আমরা কোন array তেও store করে রাখতে পারি । এইখানে কিছু key observation আছে এই consecutive mod value নিয়ে । যদি প্রথম নাম্বার এর জন্য mod value আসল ১ , আবার দেখা গেল প্রথম ৩টা নাম্বার নিয়ে mod value হচ্ছে ১ এবং আমারা যদি  প্রথম ৫টা নাম্বার নিয়েও একই ১ পাই  তাহলে আমরা দেখব যে প্রথম ২ - ৩ নাম্বার অবশ্যই m দ্বারা এবং একই ভাবে ২-৫ এবং ৪-৫ consecutive number গুলা m দ্বারা বিভাজ্য হবে । এইটা একটা example এর মাধ্যমে দেখলে ক্লিয়ার হবে ।

say n = 5 , m = 3 , n sequence numbers are : 1 , 2 , 1 , 1 , 2 । তাহলে { 2 , 1 } , { 2 , 1 , 1 , 2 } , { 1 , 2 } m = 3 দ্বারা ভাগ হবে । consecutive result এর জন্য mod value এর সাথে সাথে আমরা এড ভ্যালু বাড়িয়া আমাদের answer এর সাথে যোগ করব , কোন নাম্বার নিজেও একা m দ্বারা বিভাজ্য হতে পারে বলে mod = 0 , এর নাম প্রথমে ১ করে রাখব ।

কোড ঃ

	#include <stdio.h>
	#define rep(i,n) for(i=0;i<n;i++)
	#define MAX 100005
	int dp[MAX],a[MAX] ,n,m,cs,t,i;;
	long long int sum=0,ans=0;
	int main()
	{
	scanf("%d",&t);
	for(cs=1;cs<=t;cs++)
	{
	scanf("%d %d",&n,&m);
	rep(i,m) dp[i]=0;
	dp[0]=1;
	sum=ans=0;
	rep(i,n)
	{ scanf("%d",&a[i]);
	sum=(sum+a[i])%m;
	ans+=dp[sum];
	dp[sum]++;
	}
	printf("Case %d: %lld\n",cs,ans);
	}
	}

view raw dp442.cpp hosted with ❤ by GitHub

Coding Interview question - 1

ফেসবুক এ কিছু অনুরোধ ছিল আমি যেন ইন্টারভিউ এর প্রশ্ন নিয়ে কিছু লিখি । অনেকদিন অপারগতা জানাইয়া শেষ পর্যন্ত এই সিরিজটা লিখা শুরু করলাম । জব ইন্টারভিউ নিয়ে অনেক সাইট আছে । গুগল এ সার্চ করলেই আসে । কোডিং ইন্টাভিউ নিয়েও আছে । বাংলাতেও থাকবে । তারপরও যেহেতু অনুরোধ ছিল আমি যেন লিখি এবং আমার এখন কোন কাম কাজ নাই তাই আমি লিখতেছি :p এই লিখাটা পড়ে কারো কোন উপকার হবে কিনা আমি জানি না । যদি নাও হয় আমার কি আমার ব্লগ আমার যা মন চায় আমি লিখতে পারি :D


প্রথমে শিরোনাম কোডিং ইন্টারভিউ কেন দিলাম বলি । সফটওয়্যার ইঞ্জিনিয়ার ইন্টাভিউ  এর জন্য প্রায় সবখানেই একাধিক ইন্টাভিউ প্রসেস দিয়ে যেতে হয় । যেখানে নরমাল কোন বোর্ড এর সামনে প্রশ্ন-উত্তর বাদেও একটা ইন্টাভিউ সেকশন থাকে যেখানে আপনাকে একটা ল্যাপটপ/পিসি দিবে । ৩০মিনিট/১ ঘণ্টার মধ্যে ১/২টা প্রবলেম সল্ভ এর কোড করতে বলবে । এইগুলার জন্য ল্যাঙ্গুয়েজ আপনার পচ্ছন্দের বা উনারা স্পেসেফিক করে দিতে পারে । আমার ব্লগ পোস্টটা আসলে সেই একটা ইন্টারভিউ সেকশনকে নিয়ে ।

কোডিং ইন্টাভিউ কোশ্চেন ক্যামন হয় ? এইটা সম্পূর্ণভাবেই যে কোম্পানির ইন্টারভিউ দিচ্ছেন তার উপর নির্ভর করে । আমি এবং আমার অনেক ফ্রেন্ড যেহেতু এই প্রসেস এর মধ্যে দিয়ে গিয়েছি আমার দেখা এবং শুনা সচরাচর আন্ডার গ্রেডুয়েশন এর ইন্টাভিউতে দুই ধরণের ব্যাপার দেখা যায় । এক আপনি যে কোম্পানিতে জব এর এপ্লাই করেছেন তাদের কোন প্রোজেক্ট এর কোড আপনাকে দিয়ে বলবে এর কোন পার্ট চ্যাঞ্জ করে দিয়ে এইকাজ টা করে দেও অথবা এইখানে আসলে কি হচ্ছে  এইটা বল , কোন ভুল থাকলে পয়েন্ট আউট কর । দ্বিতীয় আপনাকে ডাটা স্ট্রাকচার বা আল্গরিথম এর কোন প্রবলেম দিয়ে এর কোড করতে বলবে ।

সব কোম্পানিতেই কি জবের জন্য কোডিং ইন্টাভিউ দিয়ে যেতে হয় ? এইটা ঠিকঠাক উত্তর দেবার মত আমার এখনও এক্সপেরিয়ান্স কিছুই হয় নাই । তবে বাংলাদেশ এর যেসব কোম্পানি প্রপার ইন্টাভিউ প্রসেস ফলো করে employee hire করে তারা নেন । বাহিরে আমার দেখা ইন্ডিয়াতে অনেক কোম্পানি এর হায়ারিং প্রসেস এর প্রথমেই একটা কোডিং টেস্ট থাকে । যেইটা হ্যাকারর‍্যাঙ্ক বা হ্যাকারআর্থ সাইট এর বিভিন্ন ইন্টাভিউ কনটেস্ট এ অংশগ্রহণ করলেই দেখা যায় । গুগোল এর একটা ইন্টাভিউ দেওয়া হয়েছিল আমার সেখানে দেখছি পুরা প্রসেসটাই আসলে কোডিং ইন্টাভিউ এর উপর । আপনাকে প্রবলেম দিবে যা সল্যুশন আপনাকে কোড এর মাধ্যমে দেখাতে হবে । অনলাইনে স্কাইপি বা গুগোল হ্যাংআউট এর মাধ্যমে যাদের ইন্টাভিউ হয় সবারই কোডিং ইন্টাভিউ প্রসেস দিয়ে যেতে হয় ।  

আমার কাছে মনে হয় স্টাটিক প্রশ্ন-উত্তর থেকে কোডিং ইন্টাভিউ অনেক সহজ একটা ব্যাপার । নরমাল প্রশ্ন-উত্তর পর্বে কোন প্রশ্নের জন্য হয়তো ৩০সেকেন্ড থেকে ১ মিনিট সময় থাকে এইখানে অনেক সময় থাকে চিন্তা করার । তবে প্রথম জবের জন্য অনেক এর মধ্যে ভয় কাজ করে । অনেক সময় জানা জিনিস তো বলা সম্ভব হয় না । এইদিকে কোড করে কিছু করতে বলা অনেক সেফ সাইট সবার জন্য । যেখানে সবকিছু ঠিক না হইলেও একজন এর কোড দেখে বুঝা সম্ভব তার চিন্তার প্রসেসটা কি ছিল  । তবে এর জন্য আগে থেকে কিছু মক ইন্টাভিউ করে নেওয়া এবং অনলাইন থেকে ইন্টাভিউ এর প্রিপারেশন নেওয়া ভাল । যারা ইন্টাভিউ নিবেন তারাও এইসব জিনিস অনেক আগে করে এসেছেন এবং স্বাভাবিক ভাবেও নেট থেকে প্রশ্ন ক্যালেক্ট করতে পারেন তারা। হয়তো সবাই না কিন্ত অনেকেই করবেন । এই পোস্ট আর বড় করতেছি না । সামনের সিরিজের লিখা গুলাতে বিভিন্ন সাইট এ দেখা কিছু ইন্টারিস্টিং প্রবলেম এর সল্যুশন নিয়ে লিখব ।

Programming Interview - Rajon Bardhan

প্রোগ্রামিং ইন্টাভিউ সিরিজের আজকের অতিথি আমাদের আহসানউল্লাহ সব থেকে কপাল খারাপ কনটেস্টেইন আবার একই সাথে সবচেয়ে ইন্সপাইরিং ক্যারেক্টার রাজন । আশারাখি সবার ভাল লাগবে ।

প্রশ্ন ঃ কমন প্রশ্ন ফাস্টে কিভাবে জানছিলা প্রোগ্রামিং কনটেস্ট এর ব্যাপারে ?
উত্তর ঃ প্রথম জানি যখন ফাস্ট সেমিস্টার ছিল তখন । ভার্সিটিতে বড় ভাইরা একটা কনটেস্ট দেন । এইটা করতে হবে । তখন আমি আমার দুই ফ্রেন্ড প্রেমা আর মাইসার সাথে টিম দেই । কিন্তু কনটেস্ট এর দিন ওরা আর আসে না পরে বড় ভাইয়ারা ১/২  এর দুইজন বড় ভাই  এর সাথে টিম করে দেন । তখন তো কিছু করতাম না , কিছু সল্ভ করতে পারি নাই ওইদিন । এমনে পরে আর করা হয় নাই কনটেস্ট । ২/২ এ এসে রিমি আমাকে বলে Uva সল্ভ করতে বলে প্রতিদিন । রিমি , হিমেল অনেক উৎসাহ দিত তখন শুরু করে দেই , প্রথম সল্ভ করছিলাম পারমুটেশন  এর একটা প্রবলেম । অনেক ভাল লাগছিল এসি হবার পর । তারপর আমি করতেই থাকি । তুমি প্রোগ্রামিং গ্রুপ এ একটা পোস্ট দিছিলা শাফায়াত এর ব্লগ নিয়ে কিভাবে কি করতে হবে জুনিওরদের জন্য। ঐটা পড়া শুরু করি । যখনই টাইম পাইতাম প্রবলেম সল্ভ করতাম , আমার মনে আছে আমি ২/২ এর পিএল এ ১৫০/২০০ টা Uva সল্ভ করি ।  পরীক্ষার আগে ২-৩ দিন এর গ্যাপ পাইতাম , আমি দেখা যাইত ১দিন খালি পড়তাম আর বাকি দিন প্রবলেম সল্ভ করতাম ।

প্রশ্নঃ আহসানউল্লাহ এতে একটা জিনিস দেখা যায় যাদের সিজিপি ভাল করার ইচ্ছা থাকে তারা কনটেস্ট এমন করতে চায় না , অনেক এর কাছে টাইম নস্ট । তুমি দুইটা জিনিস মেইন্টেইন করছ । ক্যামনে করলা বা যারা এইসব ভাবে তারা কি ঠিক ?

উত্তর ঃ কনটেস্ট শুরু করার আগে আমার ২/১ পর্যন্ত গ্রেড ছিল ৩.৬২ কিন্তু পরে ২/২ থেকে যখন কনটেস্ট শুরু করি বা প্রবলেম সল্ভ করি তখন কিন্তু প্রায় ৩.৯০ এর মত পাইতাম প্রতি সেমিস্টারে । আসলে এইটা পুরাই ভুল ধারনা । কনটেস্ট শুরু করার আগে আমি অনেক কিছুতে অনেক স্লো ছিলাম , আমার অনেক কিছু বুঝতে , পড়তে অনেক টাইম লাগত । কনটেস্ট শুরু করার পর আমার ব্রেন অনেক ফাস্ট চিন্তা করা শুরু করে , আগে যে জিনিস আমি সারাদিন লাগায়ে  হয়তো পড়তাম এইটা আমার ১ ঘণ্টার মত লাগত । আগে অনেক কিছু আমি হয়তো মুখুস্ত করতাম , আমি কনটেস্ট শুরু করার পর সব কিছু বুঝার ট্রাই করতাম , আমার ১/২ এ জাভাতে কিন্ত্ এ প্লাস ও আসে নাই কারন একটাই আমি বুঝতাম না খুব একটা । পরে ২/২ এর এলগরিদম , ডিএলডি সবকিছুতে এ প্লাস পাইতাম । নরমাল স্টুডেন্ট থেকে যারা কনটেস্ট করে তারা অনেক দ্রুত চিন্তা করতে পারে , অনেক কম সময় এ চিন্তা করতে পারে বা কোন কিছু বুঝতে পারে এইটা আমি নিজেকে দেখে বুঝছি ।


প্রশ্ন ঃ প্রথম কনটেস্ট কবে করছিলা মনে আছে ?

উত্তর ঃ ১/১ এর কনটেস্টটা বাদে প্রথম করি মারুফ ভাইদের টাইমে । ভাইরা যখন ৪/১ এ কনটেস্ট করল । আমি , রিমি আর হিমেল টিম দেই নাম ছিল প্রভাতরবি ।

-- তোমার ব্লগের নামে

হুম ।  ঐটা ভাল হইছি ৩টা সল্ভ করে ৪র্থ হই আমরা । পরে অনসাইট করি ২০১৩ এ আইইউটিতে আমি , মাহির আর অর্ণব । ঐখানে ২টা সল্ভ করছিলাম ।

প্রশ্নঃ তুমি অনেক কমটাইমে অনেক সল্ভ করছিলা বা অনেক কম সময়ে অনেক ইম্প্রুভমেন্ট করছ এইটা কিভাবে করলা ?

উত্তর ঃ  কই কি করলাম ।

-- মানে অনেক সল্ভ তো করছিলা , আমি দুইবছর আগে Uva শুরু করে যা সল্ভ করি নাই , তুমি একবছরের মধ্যে আমারে ক্রস করে গেছিলা ।

আমি খালি অফলাইন সল্ভ করতে চাইতাম , এমনে টার্গেট নিতাম ৬মাসে ৫০০ সল্ভ করতে হবে । টার্গেট ধরে সল্ভ করতে চাইতাম । যদিও অনেক ক্ষেত্রেই হয় নাই কিন্তু চেস্টাটা সব সময় ছিল । যখন কোন প্রবলেম এ আটকাইতাম নেট এ দেখতাম , যদি বুঝতাম এইটা এমন কিছু দিয়ে সল্ভ করতে হবে যেইটা আমি জানি না এইটা দেখে , শিখে আবার সল্ভ করতে চাইতাম ।

প্রশ্ন ঃ কি টাইপের প্রবলেম সল্ভ করতে বেশি ভাল লাগত ?

উত্তরঃ আমার ডাটা স্ট্রাকচার প্রবলেম গুলা , সেগমেন্ট ট্রি , বাইনারি ট্রি , বিআইটি এর প্রবলেম গুলা ভাল লাগত । সাফিক্স এরে এর প্রবলেম ও ভাল লাগত । তবে আমি জিওমেট্রি , ডিপি এর প্রবলেম অনেক পরে শুরু করি , এইটা একটা ভুল ছিল । ঐগুলা একদমই ভাল করতে পারি নাই ।

প্রশ্নঃ ক্যামনে ডাটা স্ট্রাকচার প্রবলেম এ  এত বস হইলা , কিভাবে ভাল হওয়া যায় ডাটা স্ট্রাকচার প্রবলেমগুলাতে ?

উত্তর ঃ কিসের বস ,

--- মজা নেও । সাব এর কনটেস্ট এ বাংলাদেশ এর মধ্যে ফাস্ট MO সল্ভ করে দিছিলা

ঝড়ে বক ভাই একদিনই মরে ভাই ( হাঁ হাঁ ) । এমনে বিভিন্ন ব্লগ পড়ছি । প্রবলেম সল্ভ করতাম আমি অনেক । এইভাবেই তো ।


প্রশ্ন ঃ কোন প্রবলেম সল্ভ এর জন্য তোমার Thinking Process ক্যামন থাকে ?

উত্তরঃ আমি ফাস্ট এ দেখি Brute process এ করা যাবে কিনা । যদি দেখি করা যাবে না তাইলে দেখি অন্য কোন  এল্গো এর মাধ্যমে করা যাবে কিনা । এমনে খুব একটা কিছু পারি ও না যা পারি তার মধ্যে দেখি করতে পারব কিনা।

প্রশ্ন ঃ কোন প্রবলেম এ WA পাইলে কিভাবে ঠিক কর , কি কি জিনিস দেখ ?

উত্তরঃ আমি অনেক টেস্ট কেইস তৈরি করি , বাউন্ডারি কেইজ গুলা দেখি ভুল হচ্ছে কিনা । প্রবলেমটা আমি আবার পড়ি কোন কিছু মিস করলাম কিনা । এইটাও দেখি প্রবলেমটা ভুল বুঝছি কিনা , টাইম লিমিট গুলা দেখি । আমি brute force সল্ভ করে টেস্ট কেইস করে চেক করি পরে ।



প্রশ্ন ঃ আহসানউল্লাহতে আমার নিজের দেখা আমি বলতে শুনছি অনেক জুনিওরকে তোমার মত হইতে চায় বা এখন তুমি তো ভার্সিটি এর শিক্ষক । যারা তোমারকে ফলো করে তুমি তাদের কিছু বলবা ?

উত্তর ঃ আমার মতে যার যেই জিনিসটা ভাল লাগে সেইটা করা উচিত । অবশ্যই ভাল খারাপ ব্যাপার তো দেখেই । কোনটা ভাল কোনটা খারাপ এইটা  ভার্সিটিতে কেউ উঠলে অবশ্যই বুঝা উচিত । কনটেস্ট এর ব্যাপারে হইল যদি কনটেস্ট ভাল লাগে তাইলেই করা উচিত । জোর করে কনটেস্ট করা যাবে না । জোর করে কিছু করলে তাতে ভাল রেজাল্ট ও আসবে না । মন থেকে কিছু করা হইলে অবশ্যই অবশ্যই তুমি একদিন না একদিন সেরা হইবাই । কনটেস্ট এর ব্যাপার হইলে টার্গেট নিয়ে চেস্টা করে যাওয়া উচিত । প্রতি ৬মাসে কোডফরসেস এ আমার রেটিং +২০০/৩০০ বাড়বে , ১ বছর এ আমি Uva ৫০০ নতুন প্রবলেম সল্ভ করব , লাইট ওজিতে ৩০০+ করব এমন ।

প্রশ্নঃ প্রোগ্রামিং কনটেস্ট এর ব্যাপারে কাউকে ফলো কর বা ইন্সপাইরেশন এর কেউ আছে ?

উত্তর ঃ আমি ভাই বাহিরের কাউকে দেখতাম না , আমাদের ভার্সিটি এর মধ্যে যারা আছে তাদেরই ফলো করতাম । যাদের দেখতাম । মারুফ অনেক কস্ট করতেন মারুফ ভাই এর মত কস্ট করতে চাইতাম । ভাইয়ার অনেক সল্ভ করতেন আমি চাইতাম ভাইয়াকে ক্রস করতে Uva তে । এমনে হাসিব , তুসার কনটেস্ট করত । সবাই বলতো ওরা অনেক বস কোডার আমি ওদের মত হইতে চাইতাম । আমার ফ্রেন্ডরা অনেক মোটিভেশন দিত , তুমি দিতা । আমার মনে হইত আমিও পারব । রিমি , হিমেল , তুষার অনেক বেশি পজিটিভ কথা বলত ।  এমনে ভার্সিটিতে ট্রনিং এর অনেক প্রবলেম ছিল । সিনিয়র লেভেল আর একদম জুনিয়রদের ক্লাস হইত , যারা মিড লেভেল এ ছিল তাদের কিছু হইত না । এইগুলার জন্য আমি ক্লাস নিতাম ভার্সিটিতে । আমি একটা জিনিস দেখছি নিজে কিছু করার চেয়ে অন্যকে বুঝানোর টাইমে অনেক ভাল মত শিখা যায় ব্যাপারগুলা। পরে অনেক রেড কোডার দের কথা ব্লগে পড়ে মোটিভেশন নিতাম ।

প্রশ্ন ঃ জুনিওর যারা কনটেস্ট স্টার্ট করতেছে তাদের ব্যাপারে কোন সাজেশন ? আহসানউল্লাহ এর যারা শুরু করতেছে তাদের ব্যাপারে বলার কিছু আছে ?

উত্তরঃ অফলাইন অনেক সল্ভ করা উচিত । কোন কিছু খারাপ হইলে মন খারাপ না করে বাস্তবতা চিন্তা করা উচিত কেন পারতেছ না , তার উপর কাজ করা উচিত । আহসানউল্লাহ এর রেজাল্ট এখন তো অনেক ভাল হইতেছে এইটার পিছনে দেখা উচিত কেন এখন ভাল হইতেছে । AUST এর সবথেকে ব্যালেন্স টিম ছিল সানিম , হাসিব আর মারুফ ভাই এর টিমটা কিন্তু তারা কিন্তু এমন ভাল করতে পারে নাই , অনেক খারাপ কনটেস্ট গেছে তাদের । তারপর কত কত চেস্টা করছে । টিম কনটেস্ট করছে । অনেক এ দেখে ফাস্ট ইয়ার বা সেকেন্ড ইয়ারের টিম বুয়েট , জাবি এর টপ ৫ এ চলে এসে গেছে । কিন্তু কিভাবে আসছে এইটা দেখতে হবে । ওদের কালচারটা কি । আমাদের এইখানে সবাই ভার্সিটি এসে কনটেস্ট করে , ম্যাথ , আইওআই করে আসে না । কিন্তু ওদের তো অনেক এ করে । তাই ওদের সাথে ফাইট করার জন্য প্রথম থেকেই অনেক কস্ট করতে হবে । AUST এ অনেক এ রেজাল্ট চায় , কনটেস্ট করে না । রেজাল্ট না হইলে ফেসবুক এ স্ট্যাটাস দেয় । কিন্ত্ চেস্টা করে না । তুমি কনটেস্ট এর জন্য যে লাইফে এত সেক্রিফাইজ করলা কিন্ত্ বলার মত তো কিছু পাও নাই কিন্ত্ করে গেছ এমন হার্ড সেক্রিফাইজ করতে হবে লাইফে কিছু পাইতে চাইলে ।  বিশ্বাস ও রাখতে হবে কস্ট করে গেলে কিছু পাব । আর এইখানে তো হারানোর কিছু নাই । তুমি যা  শিখবা এইটা কেউ নিয়ে যাবে না ।

প্রশ্ন ঃ এমনে প্রোগ্রামিং বাদে কোন হবি ?

উত্তর ঃ আমি খেলা দেখি অনেক । বন্ধুদের সাথে আড্ডা দেই ।

Programming Interview - Sheikh Moinul Hasan

এইটা প্রোগ্রামিং ইন্টাভিউ সিরিজের দ্বিতীয় লিখা , আজকের অতিথি বুয়েটের পরিচিত মুখ মইনুল । যারা নতুন নতুন প্রোগ্রামিং স্টার্ট করতেছে , কনটেস্ট এ আগ্রহী হচ্ছে তাদের অনেক উপকারে আসবে আশা রাখি :)
প্রশ্নঃ  প্রোগ্রামিং প্রোগ্রামিং কনটেস্ট এর ব্যাপারে কিভাবে জানছ প্রথমে ?

-- প্রথম প্রোগ্রামিং কনটেস্ট এর ব্যাপারে জানসি, বুয়েট এ ভর্তি হবার পর. অনেক বন্ধুরাই আগে থেকেই কন্টেস্ট এর বাপারে জানত. ওদের মাধ্যমেই জানতে পারি. আমারও কৌতূহল জাগল. এছাড়াও সিনিওর অনেক ভাই দের সাথেও কথা হয় এ ব্যাপারে. এভাবেই আস্তে আস্তে কন্টেস্ট এর জগতে এসে যাই.

প্রশ্নঃ  লাইফের প্রথম কনটেস্ট কবে করছিলা মনে আছে ? কোথায় করছ ?

-- প্রথম কন্টেস্ট করসিলাম বুয়েট এর একটা প্রাকটিস কন্টেস্ট এ. শান্ত ভাই অ্যারেঞ্জ করসিলেন কন্টেস্ট টা. আর ন্যাশনাল লেভেল এর প্রথম কন্টেস্ট করসিলাম হল ঢাকা রেজিওনাল ২০১২, ড্যাফোডিল ইউনিভার্সিটি এর আন্ডার এ, অ্যাট রেডিসন.

প্রশ্নঃ  কি টাইপের প্রবলেম সল্ভ করতে বেশি ভাল লাগে ?

-- নতুন কিছু, সেটা যতই সিম্পল হোক না কেন. কিন্তু ক্যাটাগরি যদি বলতে হয় তাহলে তো ডিপি কেই ফেবারেট বলতে হয়. কারন এই ক্যাটাগরিতেই সবচেয়ে ভ্যারিড প্রবলেম থাকে.

প্রশ্নঃ  সবার একটা সাধারন প্রশ্ন থাকে কিভাবে ডিপি প্রবলেম এ ভাল সল্ভ করা যায় , তুমি ডিপি অনেক ভাল সল্ভ কর এইটা কিভাবে এর ইম্প্রুভ করলা ?

-- ডিপি তে ভাল করার ওয়ে হোলও বেশি ডিপি প্রবলেম সল্ভ করা এবং রিকারেন্স রিলেশান বুঝা. বেশির ভাগ সময় এ ডিপি এর প্রবলেম ইউনিক থাকে. তোমাকে ওটাকেই চিন্তা করে রিকারেন্স রিলেশান বের করতে হবে. প্রাকটিস এর জন্য আমি বরাবর এ সাজেস্ট করি LOJ এর ডিপি প্রবলেম সল্ভ করতে.

প্রশ্নঃ  কোন প্রবলেম সল্ভ এর সময় "Thinking Process" কি থাকে প্রবলেম পড়ার পর ? কিভাবে প্রবেলম সল্ভ কর ?

-- প্রবলেম পরার সময় mindset ওপেন থাকা উচিত. আগে থেকেই ডিসাইড করা উচিত না এটা কোন ক্যাটাগরির অথবা এটা segment tree এর প্রবলেম, হয়ত এটা আরও সহজে করা যাবে. প্রবলেম পড়ার পর প্রথম চিন্তা থাকে আমি এই রকম প্রবলেম আগে করসি নাকি. আর বড় কোড করার আগে অবশ্যই খেয়াল করে নেয়া উচিত যে এটা আরও সহজে হয় কিনা এই প্রবলেম লিমিট এ. প্রব্লেম অ্যাপ্রচ করার সময় অবশ্যই লিমিট এর দিকে খেয়াল রাখা উচিত. অনেক সময় লিমিট এর উপর বেইস করেই বুঝা যায় কোন ক্যাটাগরি.

প্রশ্নঃ  WA হইলে কোন প্রবলেম এ কিভাবে attempt নেও ? 

-- WA হলে প্রথম কাজ হল কোড recheck করা, overflow, case printing, type casting, faulty or implicit double comparison, logical etc. কোড এ ভুল না হলে, চেক করতে হবে corner case and special case. তারপর কিছু নিজের নরমাল case এ সিমুলেট করে দেখতে হবে ঠিক রেসাল্ট আশে নাকি. কিছুই না হলে Idea  ঠিক আসে নাকি আবার দেখতে হবে. 

প্রশ্নঃ   প্রোগ্রামিং কনটেস্ট এ কাউকে ফলো কর বা ইন্সপারেশন এর কেউ আছে ?

-- ফলো তো অনেকেই করি, শান্ত ভাই, রিয়াদ ভাই, জেহাদ ভাই, লিন্‌কিন ভাই, সাকিব ভাই, সাদিয়া আপু, কায়সার ভাই, কিন্তু শেষ পর্যন্ত আসলে নিজেকেই decide করতে হয় যে কার কোনটা ফলো করব.

প্রশ্নঃ  অনেক সময় দেখা যায় কয়েকদিন কারো কনটেস্ট ভাল না হইলে অনেক এ হতাশ হয়ে কনটেস্ট ছেড়ে দেয় বা অন্যভাবেও বলা হয় সব কনটেস্টেন এর লাইফে হতাশার একটা পিরিয়ড থাকে , এই সময় কিভাবে নিজেকে মোটিভেট করা উচিত ?

-- কনটেস্ট জগতে টিকে থাকতে হলে সবাইকেই এই হতাশার পিরিয়ড দিয়ে  যেতে হয়. এই সময় push through করা উচিত, বেশি চিন্তা না করে, just দিন রাত practice করা উচিত. সবাই এই পিরিয়ড দিয়ে গেসে, যারা push through করতে পারসে তারাই ভাল করতে পারসে। success এর দিকে না তাকিয়ে নিজের improvement করার জন্য practice করে জেতে হবে.  

প্রশ্নঃ জুনিওরদের জন্য কোন সাজেশন , কিভাবে ভাল হওয়া যাবে ?

-- প্রোগ্রামিং কনটেস্ট এ ভাল করার কোনও shortcut নাই। practice ছাড়া কিছুই হবে না. প্রাকটিস চালায়ে যাও, দেখবা তুমিও এই রকম সাজেশান দিতেসো একদিন :p.

প্রশ্নঃ   প্রোগ্রামিং বাদে কোন হবি আছে ?

-- আমি প্রচুর পিসি গেমস খেলি mostly role playing games. এছারাও আনিমে দেখি, টিভি সিরিজ দেখি অ্যান্ড মুভি দেখি. অনেকের ই প্রশ্ন থাকতে পারে প্রোগ্রামিং কনটেস্ট এর টাইম পাই কাম্নে তাইলে. আমার মনে হয়, কোনও কিসুতে নেশা না হইলে তেমন কোনও প্রবলেম ই হয় না.
বিদ্রঃ মইনুল আমার ব্যাচম্যাট । অনেক প্রবলেম ও সবসময়ই ওর কাছ থেকে অনেক কিছু শিখার সুযোগ হইছিল আমার । নিজের টাইম নস্ট করে প্রশ্নগুলার উত্তর দেওয়ার জন্য অনেক ধন্যবাদ :)