Greedy Part - 2

Greedy Problem নিয়ে এইটা আমার দ্বিতীয় ব্লগ । কেউ প্রথমটা দেখতে চাইলে এই লিঙ্ক  পাওয়া যাবে । এইখানে ইচ্ছা আছে কিছু ভাল greedy problem solution নিয়ে কথা বলার ।

The Double HeLiX :::

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

এইখানে সিকুয়েন্স এর লিমিট বলা হইছে <= ১০০০০ । আমরা এখন যদি চাই কোন কোন পয়েন্ট এ তারা ইন্টারসেকশন করছে তাহলে Naive process এ দুইটা ফর লুপ চালাইয়া পেয়ে যাব । রান টাইম O( n * m ) ( যেখানে 'n' একটা সিকুয়েন্স এর লেন্থ আর 'm' অন্য একটা সিকুয়েন্স এর লেন্থ ) । যদি A[] , B[] দুইটা সিকুয়েন্স নাম্বার হয় তাহলে A[n-1] & B[m-1] ইন্টারসেকশন করুক আর না করুক আমরা ধরে নিব এরা ইন্টারসেক্ট করছে ।  এখন কিছু Observation থেকে আমরা Greedy solution টা develop করতে পারি ।

 1. প্রথম এ লক্ষ্য করি কেন এইটা greedy process এ solve হবে । ধরি array A[] এর ইনডেক্স 'i' এবং array B[] এর ইনডেক্স 'j' intersect করছে । তাহলে অবশ্যই যদি A[0] - A[i] এর sum value B[0] - B[j] এর sum value থেকে বড় হয় তাহলে আমাদের সব সময়ই A সিকুয়েন্স থেকে যাত্রা করা লাভ যখন হবে । এবং এইভাবে যদি দেখি আমাদের প্রত্যকটা ইন্টারসেকশন independently এই ভাবে কাজ করতে পারে ।
২। এইখানে সব সময়ই এখন যেখানে আসি ( মানে ইন্টারসেকশন ইনডেক্স , যদি কোন ইন্টারসেকশন নাও থেকে থাকে আমরা n-1 , m-1 এর একটা dummy intersection করেছি বলে কম্পেয়ার করতে পারব ।
৩। রান টাইম কি হবে ? আমরা এইখানে যদি A[] array এর  ইনডেক্স ফিক্সকড করে ক্যালকুলেশন করি তাহলে m টা ইন্টারসেকশন পেতে পারি , যেখানে আমরা লিনিয়ার ভাবে মারজ করে ভ্যালু চেক করছি । মানে এই চ্যাকিং এবং কম্পায়ের কাজে আমাদের O(n+m) টাইম লাগবে । আমাদের ইন্টারসেকশন পয়েন্ট গুলা বের এর জন্য লাগছে O(n*m) . অর্থাৎ আমরা O(n*m) ( কোন কোডে যত অপারেশন হয় এর হাইস্ট যেটাতে টাইম লাগে ঐটাই কোন কোড এর রান টাইম ) greedy solution develop করতে পারি ।

কোড

	const int MX = 1e5 + 100 ; // limit
	Long a[MX] , b[MX] ; // two sequence
	int n , m , x[MX] , y[MX] ; // intersection point
	typedef long long int Long ;
	void solve()
	{
	scanf("%d",&n);
	for ( int i = 0 ; i < n ; i++ ) scanf("%d",&a[i]);
	scanf("%d",&m);
	for( int i = 0 ; i < m ; i++ ) scanf("%d",&b[i]);
	int cs = 0 , i = 0 , j = 0 ;
	for ( i = 0 ; i < n ; i++ )
	{
	for ( j = 0 ; j < m ; j++ )
	{
	if( a[i] == b[j] )
	{
	x[cs] = i ;
	y[cs] = j ;
	cs++;
	break ; // ব্রেক করা অনেক দরকারি
	}
	}
	}
	x[cs] = n - 1 ;
	y[cs] = m - 1 ;
	Long ans = 0 ;
	i = 0 , j = 0 ;
	for ( int k = 0 ; k <= cs ; k++ )
	{
	Long sum1 = 0 , sum2 = 0 ;
	for ( ; i <= x[k] ; i++ ) sum1 += a[i];
	for ( ; j <= y[k] ; j++ ) sum2 += b[j];
	ans += max(sum1,sum2); // compare the value , always chose the best value
	}
	printf("%I64d\n",ans);
	}

view raw Greedy1.cpp hosted with ❤ by GitHub

Expedition :

এইটা খুব সুন্দর একটা প্রবলেম । priority_queue use কেন অনেক প্রবলেম solve সহজ করে দেয় , তা বুঝা যায় এই প্রবলেমটা করলে । এইখানে বলা হইছে গরু গাড়ি চালাইতে পারে :P ওরা একটা ট্রাক দখল করছে ,  এই ট্রাক এ করে নিকটবর্তী শহরে যাবে । যার দূরত্ব দেওয়া আছে । কিন্তু যেহেতু তারা ভাল মত গাড়ি চালাতে পারে না তারা গাড়ির ফুয়েল লিক করে ফেলছে , এখন কারেন্ট ফুয়েল দিলে ১ unit যাওয়া যায় । শহর আছে ট্রাকের অবস্থা থেকে d unit দূরে , এবং তাদের গাড়িতে ফুয়েল আছে f unit . এখন আরোও কিছু রিফ্রাইনিং স্টেশনের ইনফরমেশন দেওয়া আছে , এইটা কত দূরে ( শহর থেকে গাড়ি থেকে নয় , আমাদের এদের দূরত্ব গাড়ি থেকে প্রথমে বের করে নিতে হবে ) এবং কতটুকু ফুয়েল আছে ( গরুতে মেলা টাকা পয়সা :p তারা কতটা ফুয়েল করবে এইটা ব্যাপার না ) । এই প্রবলেম এ এই ইনফরমেশন গুলা নিয়ে বলা হইছে মিনিমাম কতটা ফুয়েল স্টেশনে থেমে গরুর দল নিকটবর্তী শহরে যাবে বা আদ্যও যাবে কিনা ।

• আচ্ছা স্বাভাবিক ভাবেই আমরা ফাস্ট এ যে যে স্টেশনে আছে তাদের দূরত্ব দিয়ে সর্ট করে নিব । ক্যালকুলেশন এর সুবিধার জন্য আমরা শহরকে এড দিব যেন দেখতে পারি শহরে পৌঁছাতে পারছি কিনা । 
• এইখানে অবশ্যই অবশ্যই যে যে স্টেশনে আমাদের কাছে এখন যা ফুয়েল আছে তা দিয়ে যাওয়া যায় তাদের মধ্যে থেকে ম্যাক্সিমাম যে যে স্টেশনে আছে তাদের থেকে ফুয়েল নিব ( যা না নিলেই নয় )  । এই কাজটা আমাদের priority_queue অনেক সহজে করে দেয় । 
• আমরা যদি কোন স্টেশনে না যেতে পারি মানে হইল আমাদের পক্ষে  শহরে যাওয়া পসিবল না । 
কোড :

	const int NX = 1e6 + 10 ;
	priority_queue < int > pq ; // as input is huge it better not to declear it local
	pii inp[NX];
	int d , f , n ;
	void solve()
	{
	int cs , t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	n = II ;
	rep( i , n )
	{
	int x = II , y = II ;
	inp[i] = mp( x , y );
	}
	d = II , f = II ;
	rep ( i , n )
	{
	inp[i].ff = d - inp[i].ff ; // adjust distance from truck
	}
	inp[n++] = mp( d , 0 );
	sort ( inp , inp + n ); // distance wise sort
	int i , ans = 0 ;
	while( !pq.empty() ) pq.pop();
	for ( i = 0 ; i < n ; i++ )
	{
	if( inp[i].ff > f )
	{
	while( !pq.empty() && f < inp[i].ff )
	{
	f += pq.top();
	pq.pop();
	ans++;
	}
	if( f < inp[i].ff ) break ; // we are not able to make it so break
	}
	pq.push( inp[i].ss );
	}
	printf("%d\n", i == n ? ans : -1 );
	}
	}

view raw greedy2.cpp hosted with ❤ by GitHub

এই কোডের রান টাইম হবে O( nlg(n) ) .

GERGOVIA :

এই প্রবলেমটা অনেক সহজ একটা প্রবলেম , একই প্রবলেম আমি Uva তেও দেখছি । এমন কি codechef , hacckerrank এর কনটেস্ট এও আসতে দেখছি । তাই এইখানে include করলাম ।

খুবই simple idea এর প্রবলেম । solution টাই হইল 'Think simple" । এই প্রবলেম এ একটা city এর সামগ্রিক অবস্থা তুলে ধরা হইছে । এইখানে একজন salesman বিভিন্ন বাড়িতে ওয়াইন দেয় বা কিনে , যদি ইনপুট '-' হয় তাহলে কিনবে যদি '+' হয় তাহলে কিনে ঐখানে  বিক্রি করবেন । এক বাড়ি থেকে অন্য বাড়ি যতটা ওয়াইন সরবরাহ করতে তার মিনিমাম কত unit কাজ করতে হবে ।

এই প্রবলেম এ বলাই আছে চাহিদা এবং  যোগান সমান থাকবে । এইটাই আমাদের ক্লু । একটা সাম ভ্যারিএবল নিব । এখন প্রথম বাড়িথেকে শেষ বাড়িতে ক্রমানয়ে যাব সাথে সাথে তাদের যা লাগবে ( কেউ কিনবে বা কেউ বিক্রি করবে টা যোগ করতে থাকব ) সাথে সাথে আমরা আমাদের ans current sum value এর absolute value add করতে থাকব । এইটাই আমাদের আন্সার হবে ।

আমরা চাইলে এইটা প্রুভ করতে পারি কেন কাজ করে । ধরে নেই শুধু মাত্র দুইটা বাড়ি আছে  তাহলে কি হবে
 5 -5 তাহলে এক বাড়ি থেকে অন্যবাড়িতে শুধু 5 unit কাজ করলেই হবে ।  consecutive sum করার ফলে ফাস্ট এ 5 পরের বার ০ এড হবে । এখন যদি আরো একটু বড় কেইজ নেই । 3 2 -5 . এইখানে আমাদের 7 unit কাজ করতে হয় , আমরা যে খান থেকে শুরু করি প্রথম থেকে বা শেষ থেকে consecutive sum করে যেতে থাকলেই আমরা রেজাল্টটা পাই । এই অবজারবেশন থেকে আমরা প্রবলেমটা সল্ভ করতে পারি ।

	void solve()
	{
	int n ;
	while( n = II )
	{
	if( !n ) break ;
	Long sum = 0 , ans = 0 ;
	rep ( i , n )
	{
	Long x = LL ;
	sum += x ;
	ans += abs( sum );
	}
	cout << ans << endl ;
	}
	}

view raw greedy3.cpp hosted with ❤ by GitHub

এই প্রবলেম Uva এবং codechef এ ছিল । এখন আইডি আমার মনে আসতেছে না । আমি চেস্টা করব আইডি গুলা এড করে দেবার জন্য পরে ।

এই লিখাগুলা লিখার পিছনে অনেকে কস্ট করে কমেন্ট করতেছে , ভাল ভাল কথা লিখতেছে :p যেইটা শুনতে তো ভালই লাগে । তাই লিখা ভাল লাগলে অবশ্যই জানাইতে ভুলবেন না :D আরো কিভাবে লিখাগুলাকে ভাল করা যায় বলবেন । আশারাখি সামনেই তৃতীয় পর্বটা আসবে ।  

Z Algorithm

Z algorithm এবং KMP দুইটাই prefix match store করে রাখে তাই kmp পারি মানেই এইটা আর লাগবে না , শিক্ষার ও দরকার নাই , রান টাইম ও একই ( pattern match খুঁজার জন্য কোন string এ ) । কিন্তু কিছু প্রবলেম আসলেই kmp থেকে Z algorithm করা সহজ এবং বুঝাও যায় অনেক ভাল । এই প্রবলেমটা দেখার পর আবার নতুন করে অনুপ্রেরণা পাই Z Algorithm শিখার :D তাই শিখতে তো কোন দোষ নাই । এইখানে আমরা AC code এর link । তবে এইটা পুরা লিখাটা পরে তারপর দেখার অনুরোধ করা হল ।

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

Z algorithm এ কি থাকে বলি । Z algorithm এ একটা array থাকে যেখানে পার পজিশনে i > 0 to size_of_length ,  longest prefix এর length store থাকে । by default index 0 মানে Z[0] = length_of_string .

Say
String t = ABCABCABC
Z[] = 900600300

এইখানে index 0 স্বাভাবিক ভাবেই পুরা string টাই match আছে তাই Z[0] = lenght_of_string .
Z[1] = 0 কারণ , BCABCABC এর সাথে ABCABCABC এর ০ পজিশন থেকে কোন match নাই ।
Z[2] = 0
Z[3] = 6 কারণ ABCABC এর সাথে ABCABCABC match করছে ।

ঠিক একই কারণে Z[6] = 3

আমরা trivial process দেখি কিভাবে করা যেতে পারে ।

	const int NX = 1e5 + 10 ; // length of string
	char text[NX] ;
	int Z[NX] ;
	void Z_Algorithm( )
	{
	int sz = strlen(text);
	Z[0] = sz ; // always
	for ( int i = 1 ; i < sz ; i++ )
	{
	while( i + Z[i] < sz && text[Z[i]] == text[ i + Z[i]] ) ++Z[i];
	}
	}

view raw Z1.cpp hosted with ❤ by GitHub

এইখানে O(n^2) রান টাইম লাগছে , আমরা এইটাকে চাইলে O(n) এ নিয়ে আসতে পারি । কিভাবে এইটা এখন দেখব ।

আমরা i থেকে n - 1 পর্যন্ত Z[i] এর ভ্যালু ক্যালকুলেশন করে যাচ্ছি । আমরা যখন 'i' position এর value এর কাজ করব তখন কোন ভাবে 1 - ( i - 1 ) এ আগে ক্যালকুলেট করা ভ্যালুগুলা ব্যাবহার করার চেস্টা করব । যেন আমরা আমাদের কাজটাকে সহজ করে ফেলতে পারি ।

আমরা কিছু segment এ আমাদের স্ট্রিংটার match বের করতে পারি । প্রত্যেকটা segment কে একটা Z Box ভাবতে পারি , যেমন আগের example এ Z[3] = 6 এইখানে starting point 3 থেকে ending point 9 এ একটা segment আছে মানে S[0 - ( ending ( 9 ) - starting ( 3 ) ] == S[ starting ( 3 ) - ending ( 9 ) ] মানে আমরা বলতে চাচ্ছি ABCABCABC এর 0 to ( 9 - 3 ) == 6 মানে ABCABC == 3 to 9 মানে ABCABC ।
এখন আমরা যখন এই segment টা পেয়ে গেলাম যখন আমরা সামনে অন্যকোন পজিশনের জন্য Z[] এর ভ্যালু ক্যালকুলেট করব তখন আমরা চাব যেন এই ইনফরমেশনটা আমরা use করতে পারি । এতে আমাদের অনেক ক্যালকুলেশন তো কমবেই সেই সাথে আমাদের code এর run time almost O(n) এ চলে আসবে । এইখানে এই অবজারবেশন থেকে দুইটা Case আমরা পাই ।

1.  position > ending_point : এই অবস্থায় আমাদের trivial প্রসেস এ ক্যালকুলেশন করে দেখতে হবে আমরা কয়টা ম্যাচ পাচ্ছি । যদি নতুন কোন ম্যাচ আমরা পাই সেই সাথ আমাদের starting_point and ending_point update হবে । 
2. position <= ending_point এর মানে হচ্ছে আমরা আগে এমন একটা segment পেয়ে এসেছি যার মধ্যে আমাদের current_position টা পরে গেছে । এখন আমাদের এই আগের ক্যালকুলেশন এ Z[] এর যে মানগুলা আমাদের কাছে আছে (  1 to position - 1 )  এইগুলাকে আমাদের কাছে লাগাতে হবে । আমরা surely একটা জিনিস বলতে পারি । Z[position] = min ( ending_point - position + 1 , Z[ position - starting_point ] ) ;
   এইটা কেন কাজ করে এই জিনিসটা সম্পূর্ণ কোডটা দেখা হলে বুঝা যাবে ।

কোড :

	const int NX = 1e5 + 10 ; // string size
	char text[NX] ;
	int Z[NX];
	void Z_Algorithm()
	{
	int position , starting_point , ending_point ;
	int sz = strlen( text );
	Z[0] = sz ; // always ;
	for ( position = 1 , starting_point = 0 , ending_point = 0 ; position < sz ; position++ )
	{
	if( position <= ending_point ) Z[position] = min( ending_point - position + 1 , Z[position-starting_point] );
	while( position + Z[position] < sz && text[Z[position]] == text[ position + Z[position] ] ) ++Z[position] ;
	if ( position + Z[position] - 1 > ending_point ) // need to update
	starting_point = position , ending_point = position + Z[position] - 1 ;
	}
	}

view raw Z2.cpp hosted with ❤ by GitHub

যেহেতু starting_point and ending_point এর কখনও কমবে না তাই এই কোডটার running time হয় O(n) .
একটা ছোট্ট example দেই ।
Say
S = AAAA
Z[] = 4321

এখন position = 1 , position <= ending_point is n't true .
তাই নিচে while_loop এ ভ্যালু update hobe . ফলে next iterration এর সময় starting_point = 1 , ending_point  = 3 . position ( 2 ) <= ending_point ( 3 ) so Z[position]  = min ( ending_point - position + 1 , Z[ position - strating_point ] )
Z [ 2 ] = min ( 3 - 2 + 1 , Z[ 2 - 1 ] ) ;
Z[ 2]  = min ( 2 ,  Z[1] ) ;
Z[ 2 ] = min ( 2 , 3 ) ;
Z[2] = 2 আমরা বলতে পারি ।
এখন প্রশ্ন হইল কেন Z[1] এ খালি বসল না , কারণ Z[1] এর ক্যালকুলেশন আমরা ending_point ( 3 ) পর্যন্ত রেজাল্ট জানি যদি আমাদের কারেক্ট সেভ করা রেজাল্ট আমাদের ending_point cross করে ঐখানে কি আদ্য আছে বা নাই আমরা জানি না ।

প্রায় সব kmp এর প্রবলেম Z algorithm এ করা পসিবল ।

Light OJ ( DP part - 2 )

এইটা এই সিরিজের দ্বিতীয় লিখা । এই পর্বে কিছু  interesting problem এর solution process নিয়ে লিখার চেস্টা করতেছি ।

Lighted Panels :::

এই প্রবলেম এ আমাদের একটা লাইট প্যানেল এর অবস্থা দেওয়া  হয়েছে , কোন অবস্থার '*' এর মানে হচ্ছে লাইট জ্বলে আছে , '.' মানে হচ্ছে লাইটা নিভে আছে । আমাদেরকে মিনিমাম মুভে প্যানেল এর সবগুলা লাইট জ্বালাতে হবে । এইখানে যখন কোন পয়েন্ট  toggle করা হয় ( মানে এইটা যে অবস্থায় আছে জ্বলা থাকলে নিভা , নিভা থাকলে জ্বলে উঠবে ) ঐ পয়েন্ট এর সাথে adjacent যে পয়েন্টগুলা থাকে ( diagonal সহ ) তারাও toggle করবে। 

• যে কোন প্রবলেম solution process বের করার একটা way হচ্ছে constrain গুলা চেক করা । শুধু মাত্র ইনপুট এর লিমিট দেখেই আমরা কোন সল্যুশন প্রসেস চিন্তা করা শুরু করব আবার কোন প্রসেস চিন্তা করা বাদ দিব ।  এইখানে Row <= 8 and Column <= 8 দেওয়া আছে । স্বাভাবিক ভাবেই  লিমিট কম হলে আমাদের জন্য ভাল । আমরা যদি dp solution develop করতে চাই তাইলে মনের খুশী মত state ও বাড়াইয়া ফেলতে পারব যেটা লিমিট অনেক বড় হইলে সম্ভব হইত না । 
• এই প্রবলেমটা যদি দেখি আমরা যখন কোন পয়েন্ট toggle করি তাহলে কি হবে আমরা যে row তে আছি তার আগের row এবং পরের row এর আমরা যে column এ আছি তার আগের column এবং পরের column নিয়ে কাজ করব । অর্থাৎ আমরা যদি row wise করে লাইটগুলা জ্বালাতে থাকি তাহলে আমাদের main concern হইল আগের column , এখন যে column এ আসি এ column এবং পরের column নিয়ে । একই জিনিস column wise করে এগানোর জন্য প্রযোজ্য । তবে আমরা row wise solution process টা দেখব । 
• আমারা আমাদের solution process develop করব row wise , একটা জিনিস দেখি আমরা যখন যে row নিয়ে কাজ করছি এই row এর information তার আগের row এবং পরের row এর উপর নির্ভর করে । তাই কোনভাবে আমি এখন যে row তে আসি তার কিঅবস্থা ( মানে কোন কোন পয়েন্ট জ্বলে আসে কি নিভে আসে ) যে row থেকে আসলাম তার কি অবস্থা ছিল এবং যে row তে যাব তার কি অবস্থা আছে আমাদের তা জানা থাকা দরকার । 
• এই প্রবলেম এর একটা ভাল দিক ছিল এইখানে লিমিট অনেক কম । লিমিট কম থাকলে আমরা অনেক state নিয়ে ভাবতে পারি খুব একটা difference হয় না । যেহেতু আমরা row wise কাজ করতেছি অবশ্যই আমরা কোন row তে আসি তা একটা state , আমরা যে row থেকে আসলাম তার কি অবস্থা ( কোন কিছু যার মাধ্যমে আমরা বুঝতে পারি কোন কোন পজিশনের লাইট কি অবস্থায় আছে ) , এবং এখন যে অবস্থায় আসি তার কি অবস্থা আমাদের জানা থাকতে হবে । মানে এই ইনফরমেশনগুলা আমাদের state এ থাকা লাগবে । এখন কোন লাইট জ্বলে আসে কি নিভে আসে তা আমরা খুব সহজেই বিট  দিয়ে বুঝতে পারি , যেহেতু column highest হতে পারে ৮টা তাই আমাদের শুধুমাত্র ( ১ << ৮ ) সাইজের কোন state থাকলেই আমরা বুঝে যাব কোন  কোন পজিশনে কি কি আছে । তাই আমাদের dp table হবে । dp [ number_of_row ] [ bit_position_of_previous_row] [ bit_position_of_current_row ] অর্থাৎ dp[ 8 ] [ ( 1 << 8 ) ] [ ( 1 << 8 ) ] . আসলে তাইলে আমাদের লাগতেছে  8 * ( 1 << 8 ) * ( 1 << 8 ) == 524288 size এর dp array । 
• আমাদের ক্যালকুলেশন এর জন্য আমাদের পরের row ও দরকার হবে এইটা আমরা কোথায় পাব । আমরা প্রথমেই ইনপুট নেওয়ার সময় একটা array তে রেখে দিতে পারি কোন কোন লাইট এখন জ্বলে আসে ।  
• যে  row তে আসি এর প্রতিটা combination করে আমরা আমাদের store value গুলা change করে দেখব । এর জন্য আমরা subset mask use করতে পারি । যেহেতু column এর highest limit 8 .তাই ( 1 << 8 ) == 256 খুব সহজেই আমরা আমাদের dp এর ভিতর তা চালাতে পারি । 
• যখন আমরা নেক্সড row তে যাব যদি না আমরা প্রথম কলামে থাকি তাহলে অবশ্যই আমাদের sure করতে হবে আমাদের আগের row এর সবগুলা লাইটা জ্বালানো আছে ( যদি না থাকে তাহলে আর কোন ভাবেই ঐ লাইটাকে আর জ্বালানো সম্ভব হবে না  কিন্তু প্রথম রো থেকে এই জন্যই যাব কারণ আমি দ্বিতীয় রো থেকেও প্রথম রো এর সব লাইট নিভাতে পারি । ) ।
  
  কোড :

	const int INF = 1 << 29 ;
	int vis[9][ ( 1 << 8 ) + 10 ][ ( 1 << 8 ) + 10 ] , cs ;
	int dp[9][ ( 1 << 8 ) + 10 ][ ( 1 << 8 ) + 10 ];
	int sv[9] , r , c ;
	char str[10];
	int DP( int idx , int curmask , int prvmask )
	{
	if( idx >= r )
	{
	if( prvmask == ( 1 << c ) - 1 ) return 0 ;
	else return INF ;
	}
	int &v = vis[idx][curmask][prvmask];
	int &ret = dp[idx][curmask][prvmask];
	if( v == cs ) return ret ;
	// printf(" here \n");
	ret = INF ;
	for( int i = 0 ; i < ( 1 << c ); i++ )
	{
	int cnt = 0 ;
	int row[3] = {prvmask , curmask , sv[idx+1] }; // আগে রো , এখন যে রোতে আছি , যে রো তে যাব
	for ( int j = 0 ; j < c ; j++ ) // সাবসেট মাস্ক দিয়ে all combination নিয়ে দেখছি
	{
	if( !(i & ( 1 << j )) ) continue ; // no need for toggle
	// need to toggle
	cnt++;
	rep( k , 3 ) row[k] ^= ( 1 << j );
	if( j + 1 < c ) rep ( k , 3 ) row[k] ^= ( 1 << ( j + 1 ) );
	if( j - 1 >= 0 ) rep ( k , 3 ) row[k] ^= ( 1 << ( j - 1 ) );
	}
	if( idx == 0 ) ret = min( ret , cnt + DP( idx + 1 , row[2] , row[1] ) );
	else if( row[0] == ( 1 << c ) - 1 ) // only if there is all light open in our previous row
	ret = min( ret , cnt + DP( idx + 1 , row[2] , row[1] ) );
	}
	return ret ;
	}
	int main()
	{
	int t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	r = II , c = II ;
	ms( sv , 0 );
	rep( i , r )
	{
	scanf("%s",str);
	int mask = 0 ;
	rep( j , c )
	{
	if( str[j] == '*' ) mask |= ( 1 << j );
	}
	sv[i] = mask ; // save the current condition
	}
	int ans = DP( 0 , sv[0] , 0 );
	if( ans == INF ) printf("Case %d: impossible\n",cs);
	else printf("Case %d: %d\n",cs,ans);
	}
	return 0;
	}

view raw dp1.cpp hosted with ❤ by GitHub

এই প্রবলেমটা আমরা itterative ভাবেও  করতে পারি , subset mask এর মাধ্যমে ।

Tiles (II) :
এইটা একটু বিরক্তি কর bitmask প্রবলেম । আমাদের ছয়টা বিভিন্ন সাইজের টাইলস দেওয়া আছে । আমাদের বলতে হবে এই বিভিন্ন টাইলজ দিয়ে ( n x m ) সাইজের একটা গ্রীড কতভাবে পূরণ করা যাবে । দুইটা বোর্ড different হবে যদি এদের মধ্যে কোন cell এর কালার different হয় ।

• ইনপুট লিমিট এ দেওয়া দেওয়া আছে ( 1 <= n , m <= 100 but min( n , m ) <= 8 ) । এর মানে হইল row , column এর মধ্য যে কোন একটা 8 এর চেয়ে কম হবে । এইটার একটা ব্যাপার হইল আমরা চাইলে এই কম পার্টটাকে বিট করে ফেলতে পারি । এইখানে Row/Column দুইটার যে কোনটাই হইতে পারে । যেহেতু আমরা জানি না কোনটা হবে আমরা ধরে নেই column এর পার্টটাতে আমরা বিটমাস্ক করব কিন্তু Row ও হইতে পারে । যদি Row <= 8 হয় তাহলে আমরা given array এর Row এবং Column part টা swap করে দিব । মানে যা input এ ছিল আমাদের column এইটা কে আমরা Row ভ্যালু করে ফেলব  । মানে যদি Row = 8 , Column = 100 হয় তাহলে আমাদের Row হয়ে যাবে ১০০ এবং column হয়ে যাবে ৮ । 
•  এই প্রবলেমটার সাথে আগের প্রবলেম এর মিল আছে । আমরা যদি given tiles গুলা দেখি প্রতিটাই দুইটা row করে নিয়ে হচ্ছে । অর্থাৎ কোন tiles বসবে কি বসবে না এই জন্য আমাদের কাছে কমপক্ষে দুইটা row এর ইনফরমেশন থাকতে যাবে । 
• আমরা যখন কোন tiles বসাতে যাব আমাদের দেখতে হবে আমরা এখন যে Row তে আসি তার পরের Row এর যে সব column নিতে টাইলসটা হবে তা খালি আছে কিনা । 
• আমরা column ফিল করতে করতে next column এ আগাব এবং যেহেতু দুইটা curmask ও nextmask নিয়ে কাজ করছি অবশ্যই আমরা যখন সব Row ফিল করে ফেলব তখন nextmask অবশ্যই ০ থাকবে । 
• এই কাজটা একটু বিরক্তিকর কারণ আমাদের অনেক চেক রাখতে হবে । সবগুলা tiles নিয়ে ফিল করার জিনিসটা আমরা একটা backtrack function এর মাধ্যমে করতে পারি । এইখানে যেহেতু আমরা column এর basis এ ফিল করব ( backtrack এ ) আর লিমিট যেহেতু কম আমাদের খুব একটা বেশী কল হবে না ।
• এইখানে রেজাল্ট কে 2^64 mod করে দিতে বলা হইছে তাই আমরা unsigned long long int use করব ।  

কোড :

	//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 = ( 1 << 8 ) + 10 ;
	const int MX = 105 ;
	ull dp[MX][NX] ;
	int vis[MX][NX] , cs , row , col ;
	char inp[MX][MX] , grid[MX][MX] ;
	ull DP(int , int) ;
	ull gen( int r , int c , int curmask , int nxtmask )
	{
	if( c == col ) return DP( r + 1 , nxtmask );
	int cc = ( curmask >> c ) & 1 ;
	int cnc = ( curmask >> ( c + 1 ) ) & 1 ;
	int nc = ( nxtmask >> ( c ) ) & 1 ;
	int nnc = ( nxtmask >> ( c + 1 ) ) & 1 ;
	int npc = ( nxtmask >> max( 0 , c -1 ) ) & 1 ;
	if( cc ) return gen( r , c + 1 , curmask , nxtmask );
	if( grid[r][c] == '#' ) return gen( r , c + 1 , curmask , nxtmask );
	ull ret = 0 ;
	// title one
	if( r + 1 < row )
	{
	if( grid[r][c] == '.' && grid[r+1][c] == '.' && !cc && !nc )
	{
	ret += gen( r , c + 1 , curmask | ( 1 << c ) , nxtmask | ( 1 << c ) );
	}
	}
	// tile two
	if( c + 1 < col )
	{
	if( grid[r][c] == '.' && grid[r][c+1] == '.' && !cc && !cnc )
	{
	ret += gen( r , c + 2 , curmask | ( 1 << c ) | ( 1 << ( c + 1 ) ) , nxtmask );
	}
	}
	// tile five
	if( c - 1 >= 0 && r + 1 < row )
	{
	if( grid[r][c] == '.' && grid[r+1][c] == '.' && grid[r+1][c-1] == '.' && !cc && !nc && !npc )
	{
	ret += gen( r , c + 1 , curmask | ( 1 << c ) , nxtmask | ( 1 << c) | ( 1 << ( c - 1 ) ) );
	}
	}
	if( r + 1 < row && c + 1 < col )
	{
	// tile 4
	if( grid[r][c] == '.' && grid[r][c+1] == '.' && grid[r+1][c] == '.' && !cc && !cnc && !nc )
	{
	ret += gen( r , c + 1 , curmask | ( 1 << c ) | ( 1 << ( c + 1 ) ), nxtmask | ( 1 << c) );
	}
	// tile 3
	if( grid[r][c] == '.' && grid[r+1][c] == '.' && grid[r+1][c+1] == '.' && !cc && !nc && !nnc )
	{
	ret += gen( r , c + 1 , curmask | ( 1 << c ) , nxtmask | ( 1 << c) | ( 1 << ( c + 1 ) ) );
	}
	// tile 6
	if( grid[r][c] == '.' && grid[r][c+1] == '.' && grid[r+1][c+1] == '.' && !cc && !cnc && !nnc )
	{
	ret += gen( r , c + 1 , curmask | ( 1 << c ) | ( 1 << ( c + 1 ) ) , nxtmask | ( 1 << ( c + 1 ) ) );
	}
	}
	return ret ;
	}
	ull DP(int r , int mask)
	{
	if( r == row ) return mask == 0 ;
	ull &ret = dp[r][mask];
	int &v = vis[r][mask];
	if( v == cs ) return ret ;
	v = cs ;
	ret = gen(r , 0 , mask , 0 );
	return ret ;
	}
	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 t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	row = II , col = II ;
	rep( i , row ) scanf("%s",inp[i]);
	if( row < col )
	{
	rep( i , row ) rep ( j , col ) grid[j][i] = inp[i][j];
	swap( row , col );
	}
	else
	{
	rep( i , row ) rep ( j , col ) grid[i][j] = inp[i][j];
	}
	printf("Case %d: %llu\n",cs,DP(0,0));
	}
	return 0;
	}

view raw DP2.cpp hosted with ❤ by GitHub

Software Company :
এই প্রবলেমটা binary search + dp এর । এইখানে একটা software company এর কথা বলা হইছে । তারা দুইটা প্রোজেক্ট শেষ করবে । n জন employee এর ইনফমেশনে দেওয়া আছে তাদের কত মিনিট করে নেয় দুইটা প্রোজেক্ট এর এক unit কাজ করতে । কোন প্রোজেক্ট সম্পূর্ণ শেষ করতে m unit কাজ কমপ্লিট করতে হবে ।

• এই প্রবলেমটা খুব সম্ভত বুঝাটা এইটা binary search এ হবে এইটাই সব থেকে কঠিন পার্ট । তারপরের কাজ খুব সহজ । আমরা যেকোন একটা employee নিয়ে ও যদি একা দুইটা কাজ করত তাহলে কত সময় লাগতকে high ধরে lower_bound binary seach করব । দেখব lowest কত value এর জন্য আমাদের কাজ দুইটি সম্পূর্ণ করা যাবে । 
• 3 state এর normal dp , current_employee_number , work_left_for_first_one , work_left_for_second_one . এইখানে লিমিট দেওয়া আছে ( 1 <= n , m <= 100 ) তাই আমাদের dp[101][101][101] size এর dp দিয়েই হয়ে যাবে । 
কোড

	const int NX = 102 ;
	int loop , vis[NX][NX][NX] ;
	bool dp[NX][NX][NX] ;
	pii inp[NX];
	int low , high , mid , ans , n , m ;
	bool DP( int idx , int need1 , int need2 )
	{
	if( need1 + need2 == 0 ) return true ;
	if( idx == n ) return false ;
	int &v = vis[idx][need1][need2];
	bool &ret = dp[idx][need1][need2];
	if( v == loop ) return ret ;
	v = loop ;
	ret = false ;
	int i ;
	for ( i = 0 ; i <= need1 && i * inp[idx].ff <= mid ; i++ )
	{
	int k = ( mid - ( i * inp[idx].ff ) )/ inp[idx].ss ;
	if( k > need2 ) k = need2 ;
	if( DP( idx + 1 , need1 - i , need2 - k ) ) return ret = true ;
	}
	return ret ;
	}
	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 ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	n = II , m = II ;
	rep( i , n )
	{
	int x = II , y = II ;
	inp[i] = mp( x , y );
	}
	low = 0 , high = inp[0].ff * m + inp[0].ss * m ;
	while( low <= high )
	{
	mid = ( low + high )/2 ;
	loop++;
	if( DP( 0 , m , m ) )
	{
	ans = mid ;
	high = mid - 1 ;
	}
	else low = mid + 1 ;
	}
	printf("Case %d: %d\n",cs,ans);
	}

view raw dp3.cpp hosted with ❤ by GitHub

এই সিরিজের আরো কয়েকটা লিখা ইচ্ছা আছে , যদি লিখার মোটিভেশন বজায় থাকে । ধন্যবাদ পড়ার জন্য ।

Segment tree/ BIT part - 1

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

•  সেগমেন্ট ট্রি - ১ 
•  সেগমেন্ট ট্রি - ২ 
•  বাইনারি ইনডেক্সড ট্রি 

এইখানে কিছু ভাল প্রবলেম কিভাবে আমরা উপরের দুইটা প্রসেস এর মাধ্যমে করতে পারি তা লিখার ইচ্ছা আছে । অনেক ভাল ভাল প্রবলেম আছে এই দুইটা টপিক এর । কয়েকটা সিরিজ লিখার ইচ্ছা আছে ( যদি কোনভাবে লিখার মোটিভেশন পাওয়া যায় :p ) ।

Calculate The Cost

আমাদের এইখানে বিভিন্ন গাছে পজিশন দেওয়া হবে তাদের ভ্যালু সহ তারপর আমাদের কিছু কুয়েরি করতে হবে যে ইনফরমেশন দেওয়া আছে তাদের উপর । আমাদের এই সব কুয়েরি তে  বলতে হবে যে এরিয়া ( x1 , y1 to x2 ,y2 ) এর মধ্যে কত ভ্যালু এর ট্রি আছে । এইখানে একটা জিনিস লক্ষ্য করার ব্যাপার হইল যদি আমাদের ইন্ডেক্স এর ( X , Y <= 10^3 ) এর মত হইত তাহলে আমরা খুব সহজে 2D Bit এর মাধ্যমে রেজাল্ট পেয়ে যাইতাম কিন্ত্ এইখানে দেওয়া আছে ( X , Y <= 10^7 ) । লিমিট অনেক বেশি বড় হওয়ায় আমরা কোন ভাবেই এত বড় সাইজের Array declear করতে পারি না । আমাদের এই প্রবলেমটাকে তাই কোন ভাবে 2D থেকে 1D তে নিয়ে এসে সল্ভ করতে হবে ।

আমি ধরে নিচ্ছি 2D solution কিভাবে হয় তা সবার জানা আছে । যদি না থাকে তাহলে index ( x1 , y1 ) to index ( x2 , y2 ) এর  মধ্যের ভ্যালু গুলার সাম হইল

Ans  =   BIT[x2][y2] - BIT[x1-1][y2] - BIT[x2][y1-1] + BIT[x1-1][y1-1] ;

এইটা কিভাবে আন্সার দিচ্ছে এইটা খাতায় একটা 2D grid একে , ইনডেক্স এর ভ্যালু বসিয়ে দেখলে বুঝে ফেলার কথা ।

এখন আমরা অফলাইন সল্যুশন কিভাবে হতে পারে তা দেখব ।

1. উপরের ফর্মুলাটা যদি লক্ষ্য করি তাহলে একটা জিনিস দেখি x1 row তে ( +Bit[x1-1][y1-1] - BIT[x1-1][y2] ) হচ্ছে । আবার x2 row ( + BIT[x2][y2] - BIT[x2][y1-1] ) হচ্ছে । 
2. অর্থাৎ আমরা যদি আমাদের দেওয়া ভ্যালু গুলাকে ( অবশ্যই কুয়েরি সহ ) row এর ব্যাসিস এ সর্ট করি তাহলে আমি column value ( y ইনডেক্স এর মান এর পজিশন ) তে 1D BIT চালাইয়া মান পেয়ে যেতে পারি । 
3. এইখানে একটা গুরুত্বপূর্ণ ব্যাপার হচ্ছে tree_point এর priority , opening point এর priority , closing_point এর priority যখন কিছু ভ্যালু সমান হয়ে যাবে । স্বাভাবিক ভাবেই পয়েক্ট এর  priority সব থেকে বেশি হবে । 

কোড ::

	const int MX = 1e7 + 10 ;
	const int XX = 50000 + 10 ;
	const int open = 1 ;
	const int point = 2 ;
	const int close = 3 ;
	struct abc
	{
	int x , y , val , priority , lim ;
	};
	abc inp[MX];
	Long tree[MX];
	Long ans[XX];
	bool cmp( abc A , abc B )
	{
	if( A.x == B.x )
	{
	return A.priority < B.priority ;
	}
	return A.x < B.x ;
	}
	void add( int x , int v )
	{
	while( x < MX )
	{
	tree[x] += v ;
	x += ( x & -x );
	}
	}
	Long sum( int x )
	{
	Long ans = 0 ;
	while( x )
	{
	ans += tree[x];
	x -= ( x & -x );
	}
	return ans ;
	}
	void solve()
	{
	// 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 ;
	scanf("%d",&t);
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	int n ;
	scanf("%d",&n);
	rep( i , n )
	{
	scanf("%d %d %d",&inp[i].x,&inp[i].y,&inp[i].val);
	inp[i].x++;
	inp[i].y++;
	inp[i].priority = point ;
	}
	int idx = n ;
	int r = II ;
	rep( i , r )
	{
	scanf("%d %d",&inp[i].x,&inp[i].y);
	inp[idx].x++;
	inp[idx].y++;
	inp[idx].priority = open ;
	inp[idx].val = i ;
	idx++;
	scanf("%d %d",&inp[i].x,&inp[i].y);
	inp[idx].x++;
	inp[idx].y++;
	inp[idx].priority = close ;
	inp[idx].val = i ;
	inp[idx-1].lim = inp[idx].y ;
	inp[idx].lim = inp[idx-1].y ;
	idx++;
	}
	sort ( inp , inp + idx , cmp );
	ms( tree , 0 );
	ms( ans , 0 );
	rep( i , idx )
	{
	if(inp[i].priority == point ) add( inp[i].y , inp[i].val );
	else if( inp[i].priority == open ) ans[inp[i].val] -= ( sum( inp[i].lim ) - sum( inp[i].y - 1 ) );
	else ans[inp[i].val] += ( sum(inp[i].y ) - sum( inp[i].lim - 1 ) );
	}
	rep( i , r ) printf("%lld\n",ans[i]);
	}
	}

view raw segone.cpp hosted with ❤ by GitHub

রান  টাইম হচ্ছে O( lim * log ( n + q ) )

New Land :::

সহজ কথায় আমাদের এই প্রবলেম এ বলছে আমরা হাইস্ট কত এরিয়ার একটা rectangle পাইতে পারি যেখানে কোন ১ নাই । এইখানে লিমিট অনেক বেশি row <= 2000 & column <= 2000 .যদি কম হইত ১০০ এর মত তাহলে আমরা Maximum SUM 2D এর মত করে সল্যুশন করে ফেলতে পারতাম । যেইটা এখন সম্ভব না । এই ধরনের প্রবলেম গুলার জন একটা অফ লাইন ট্যাকনিক আছে Stack use করে করা হয় । Histogram technique । যেটা আমরা এই প্রবলেমটা সমাধান করার জন্য ব্যাবহার করব । আগেই ক্ষমা চাইয়া নেই এই ধরনের কিছু বুঝানো জন্য ভাল ছবি দেওয়া দরকার , যেইটা রেডি করা একটু কস্টকর আমি নিজে অনেক অলস হওয়ায় এইটা করছি না । আমি যা লিখার চেস্টা করছি সব কিছুই পড়ার সাথে সাথে খাতায় ছবি এঁকে করলে ক্লিয়ার হবে ।

আমরা প্রবলেমটাকে কয়েকটা ভাগ এ সল্ভ করি ।

1.  commutative sum ( column wise ) । মানে আমরা যখন ১ পাব তখন ০ দিব যদি ০ পাই তাহলে ১ এড করে আগের row এর ভ্যালুর সাথে এড করে দিব । 
2. প্রতিটা পজিশন এর জন্য ডানে এবং বামে আমার কাছে এখন যে সাইজের Histogram আছে এর থেকে বড় বা সমান কতটা width এর বড় বিলিং করা যায় ( কথাগুলা না বুঝলে ভয় পাওয়ার কিছু নাই কোড দেখলেই বুঝা যাবে ) । 

কোড

	const int MX = 2005 ;
	int height[MX][MX] ;
	char str[MX][MX];
	int n , m , lft[MX] ;
	void solve()
	{
	int cs , t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	n = II , m = II ; // ইনপুট নেওয়া হচ্ছে
	rep(i,n) scanf("%s",str[i]);
	rep(j,m) if( str[0][j] == '1' ) height[0][j] = 0 ; // প্রাথমিক ভাবে ফাস্ট রো এর জন্য করছি
	else height[0][j] = 1 ;
	For(i , n-1 ) rep( j , m ) if( str[i][j] == '1' ) height[i][j] = 0 ;
	else height[i][j] = height[i-1][j] + 1 ; // আমরা এর সাথে আগের রো এর সেভ করা ভ্যালু এড করে commutative sum current
	// position এর জন্য পাচ্ছি
	Long ans = 0 ;
	stack < int > st ;
	int j , r;
	rep(i,n) // 0 to n - 1
	{
	while( !st.empty() ) st.pop();
	rep(j,m) // o to m - 1
	{
	while( !st.empty() && height[i][st.top()] >= height[i][j] ) st.pop(); // maximum কত লেফট এ যাইতে পারি
	if( st.empty() ) lft[j] = 0 ; // একদম শুরুতেই চলে এসেছি
	else lft[j] = st.top() + 1 ; // আমাদের লেফট পজিশন
	st.push(j);
	}
	while( !st.empty() ) st.pop(); // এইটা করা অনেক ইম্পরট্যান্ট
	for ( j = m - 1 ; j >= 0 ; j-- )
	{
	while( !st.empty() && height[i][st.top()] >= height[i][j] ) st.pop(); // ম্যাক্সিমাম কত রাইটে যেতে পারি
	if( st.empty() ) r = m - 1 ; // একদমই শেষ এ চলে এসেছি
	else r = st.top() - 1 ; // আমার j পজিশন এর রাইট পজিশন
	if( (Long) ( r - lft[j] + 1 ) * height[i][j] > ans )
	ans =(Long) ( r - lft[j] + 1 ) * height[i][j]; // আন্সার আপডেট করছি
	st.push(j);
	}
	}
	printf("Case %d: %lld\n",cs,ans);
	}
	}

view raw segment2.cpp hosted with ❤ by GitHub

প্রুভ করি এইভাবে কেন কাজ করবে ।

1. আমরা যেহেতু column wise commutative sum রাখছি । তাহলে আমাদের প্রতিটা পজিশন এর জন্য ম্যাক্সিমাম হাইটের এবং Width এর বিলিং কত সাইজের পসিবল পাচ্ছি যাই আমাদের Ans এর সাথে চেক হচ্ছে । 
2. একটু ডিবাগ করলেই দেখব যে 0 height এর জন্য always left = 0 , right = m - 1 হইলেই যেহেতু হাইট দিয়ে গুণ হচ্ছে ঐ পজিশন এর জন্য আমার ০ এই পাওয়া যাচ্ছে ।

এইখানে run time O( n * m ) যেখানে আমরা যদি maximum sum 2D তে করতাম আমাদের লাগত O( n * m ^ 2 ) . 

একদমই একই রকমের একটা প্রবলেম হচ্ছে CTGAME ।

POSTERS :::

এই প্রবলেম এ আমাদের 1D কোন প্যানেল এ ইলেকশন পোস্টারের start position আর end position দেওয়া থাকবে । সিরিয়ালি যদি আমরা পোষ্টারগুলো লাগাই তাহলে শেষ পর্যন্ত কয়টি পোস্টার ভিজিবল থাকবে । এই প্রবলেমটা line sweep technique use করেও সল্ভ করা যায় । তবে segment tree তেও solution possible . আমরা segment tree solution process টা দেখব ।

segment tree এর অনেক প্রবলেম  Data compression করার প্রয়োজন হয় কারণ না হলে রেঞ্জ অনেক বড় হয়ে যায় , প্রথমত এতে segment tree slow হয়ে যাবে যেহেতু অনেক huge range এর মধ্যে কাজ করতে হবে আবার এমনও হতে পারে range এত বড় হয়ে গেল যে ( array size )  আর segment tree develop করা গেল না । Data compression ব্যাপারটা হচ্ছে কোন ভ্যালুকে অন্য কোন ভ্যালু দিয়ে replace করা । ধরি আমাদের দেওয়া আছে  4 , 5 , 101 ৩টা নাম্বার । এখন আমরা যে কাজই করি এই তিনটা নাম্বার দিয়ে করব । এইগুলা কে যদি ইনডেক্স হিসাবে কল্পনা করি তাহলে আমাদের 101 পর্যন্ত নাম্বার access করতে মিনিমাম 101 টা জিনিস লাগবে , কিন্ত্ এইখানে 1-101 এর মধ্যে অনেক কিছুই no use . এখন যদি আমরা 4কে 1 , 5কে 2 , 101 কে 3
দ্বারা কমপ্রেস করি মানে যাই ১ তাই ৪ , যাই ২ তাই ৫ , যাই ৩ তাই ১০১ তাহলে আমরা অপারেশন এবং স্টোরেজ সাইজ দুইটাই কমাইয়া ফেলতে পারছি ।

1. এই প্রবলেমটা জন্য তাই আমরা প্রথমেই  data compression করে নিব । set , map even normal array দিয়েও এই কাজটা সহজেই করা যায় । আমাদের প্রবলেম এর লিমিট থেকে সিন্ধান্ত নিতে হবে আমরা কিভাবে কাজটা করব । 
2. একটা জিনিস খেয়াল করি যদি আমরা শুরু থেকে চিন্তা না করি লাস্ট থেকে চিন্তা করি তাহলে দেখব শেষ এ যে পোস্টারটা লাগানো হয়েছে তা অবশ্যই অবশ্যই দেখা যাবে । এখন শেষ এর দিক দিয়ে সেকেন্ড পোস্টারটা তখনই দেখা যাবে যদি না শেষ পোস্টারটা এসে এইটাকে সম্পূর্ণভাবে কভার করে দেয় । 
3. আমরা তাই শেষ থেকে কাজ করে প্রথমে যাব । segment tree এর সব কিছু true রাখি ( মানে সব পজিশন এখন ভিজিবল ) । তারপর আসতে আসতে প্রতিটা অপারেশন এর সময় শুধু চেক করব যে রেঞ্জ এর মধ্যে এখন পোস্টারটা লাগাব তার কোন একটা পজিশন কি কোন না কোন ভাবে দেখা যায় কিনা , দেখে গেলেই লাস্ট এও এইটা দেখা যাবে কারণ এর পরের পোস্টার গুলা আমরা আগেই লাগাইয়া আসসি ।

কোড 

	const int MX = 1e7 + 10 ;
	const int NX = 40000 + 10 ;
	bool seg[ 8 * NX ] , lazy [ 8 * NX ] ;
	int num[ MX ] , inp[MX][2] , n;
	set < int > s ;
	int lc( int x )
	{
	return 2*x ;
	}
	int rc( int x)
	{
	return ( 2 * x ) + 1 ;
	}
	bool query( int node , int x , int y , int lft , int rgt )
	{
	if( lazy[node] )
	{
	seg[node] = 1;
	lazy[lc(node)] = lazy[node];
	lazy[rc(node)] = lazy[node];
	lazy[node] = 0 ;
	}
	if( x >= lft && y <= rgt ) return seg[node];
	if( x > rgt || y < lft ) return 1 ;
	bool ret = 1 ;
	int mid = ( x + y )/2 ;
	ret &= query( lc(node) , x , mid , lft , rgt );
	ret &= query( rc(node) , mid + 1 , y , lft , rgt );
	return ret ;
	}
	void update( int node , int x , int y , int lft , int rgt )
	{
	if( lazy[node] )
	{
	seg[node] = 1;
	lazy[lc(node)] = lazy[node];
	lazy[rc(node)] = lazy[node];
	lazy[node] = 0 ;
	}
	if( x > rgt || y < lft ) return ;
	if( x >= lft && y <= rgt )
	{
	seg[node] = 1 ;
	if( x != y )
	{
	lazy[lc(node)] = lazy[rc(node)] = 1 ;
	}
	lazy[node] = 0 ;
	return ;
	}
	int mid = ( x + y )/2 ;
	update( lc(node) , x , mid , lft , rgt );
	update( rc(node) , mid + 1 , y , lft , rgt );
	int xx = seg[lc(node)];
	int yx = seg[rc(node)];
	seg[node] = (xx & yx);
	}
	void solve()
	{
	int cs , t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	s.clear();
	n = II ;
	rep ( i , n )
	{
	int x = II , y = II ;
	s.insert( x ); // ডাটা কমপ্রেশন এর জন্য স্টোর করছি
	s.insert( y ); // ডাটা কমপ্রেশন এর জন্য স্টোর
	inp[i][0] = x ;
	inp[i][1] = y ;
	}
	int idx = 1 ;
	forstl( it , s )
	{
	num[*it] = idx++; // ডামি ভ্যালুগুলা দেওয়া হচ্ছে
	}
	ms( seg , 0 );
	ms( lazy , 0 );
	int i , ans = 0 ;
	for ( i = n - 1 ; i >= 0 ; i-- )
	{
	if( query( 1 , 1 ,idx - 1 , num[inp[i][0]] , num[inp[i][1]] ) == 0 ) // এখনও কমপক্ষে একটা পজিশন খালি আছে যেখান থেকে এই
	// পোস্টারটা দেখা যেতে পারে
	{
	update( 1 , 1 , idx - 1 , num[inp[i][0]] , num[inp[i][1]] );
	ans++;
	}
	}
	printf("%d\n",ans);
	}
	}
	}

view raw seg3.cpp hosted with ❤ by GitHub

এই প্রবলেমটা লাইট ওজি তেও আছে link .  এই সিরিজটা আরো বড় করার ইচ্ছা আছে যদি সময় এবং লিখার মোটিভেশন পাওয়া যায় । ধন্যবাদ পড়ার জন্য ।

Minimum Expression

আমাদের একটা string দেওয়া হল যেটাকে আমরা চাইলে rotate করতে পারি । মানে একদম লাস্ট এ যে ক্যারেক্টারটা আসে তা আমরা একদম প্রথমে নিয়ে যেতে পারি । এবং বাকি ক্যারেক্টারগুলা এক ঘর করে রাইট সাইটে সরে যাবে । আমাদের বলতে বলা হল আমরা মিনিমাম কতটা এমন rotate করে string এর lexicographically smallest string  করতে পারি ।

আমাদের যদি n size এর এমন কোন array দেওয়া থাকে যার মধ্য দেখে আমাদের বলতে বলা হয় সবথেকে মিনিমাম নাম্বার/ ভ্যালু এর ইনডেক্সটা কি তাহলে আমরা কি ভাবে কাজ করি - 

	void solve()
	{
	int i = 0 , j ;
	for ( j = 1 ; j < n ; j++ )
	if( array[i] > array[j] ) i = j ;
	return i ;
	}

view raw ME1.cpp hosted with ❤ by GitHub

এখন যদি আমরা একই কাজটা string rotation এর জন্য করতে চাই তাহলে কিভাবে করব -

	void solve()
	{
	int i = 0 , j ;
	for ( j = 1 ; j < n ; j++ )
	{
	if( rotation( i ) > rotation( j ) ) i = j ;
	}
	return i ;
	}

view raw ME2.cpp hosted with ❤ by GitHub

এইখানে আমরা দেখি আমাদের রান টাইম হচ্ছে O(n^2) কারণ এই rotation( i ) > rotation ( j ) operation টা করার জন্য আমাদের O(n) টাইম যাচ্ছে এবং কাজটা আমাদের করতে হচ্ছে n বার মানে আমাদের টোটাল O(n^2) লেগে যাচ্ছে কাজটা করতে । string এর সাইজ যদি অনেক বড় হয় তাই আমাদের টাইম লিমিট এর মধ্যে এইভাবে করে আমরা পারব না , TLE খেয়ে যাব ।  আমরা যদি কিছু মোডিফিকেশন করতে পারি তাহলে আমরা কোডটাকে O(n) এ নিয়ে আসতে পারি ।

এই lexicographical string rotation O(n) এর এলগরিদমটা প্রথম দেন "Zhou Yuan" . আমরা rotation( i ) > rotation( j ) এই অপারেশনটার কয়েকটা Observation খেয়াল করি ।

Observation 1 :

যদি ইনডেক্স 'i' এর string থেকে ইনডেক্স 'j' এর string ( মানে rotation করার পর ( i , j ) থেকে যে stringটা স্টার্ট হয়ে আমরা যে string পাই সেই string ) ছোট হয় তাহলে আমরা বলতে পারি  s[ i + p ] = s [ j + p ] and s [ i + k ] < s [ j + k ] যেখানে ০ <= p < k আর i + k < length_of_the_string .

মানে i index স্ট্রিং j index এর string থেকে p টা ভ্যালু সমান হলেও j থেকে  k নাম্বার value টা i থেকে k নাম্বার ভ্যালুটার থেকে বড় ।

Observation 2 :
যেহেতু rotation ( i ) < rotation ( j ) যেখানে j + k নাম্বার পজিশন এ আমাদের i  + k থেকে বড় ভ্যালু পাওয়া যাচ্ছে , তাই আমাদের নেক্সড ক্যালকুলেশন এর জন্য j + k ভ্যালু বাদ দিতে পারি কারণ সবার জন্যই আমরা k নাম্বার পজিশন এ এসে বড় ভ্যালু পেয়ে যাব  তাই  আমরা নেক্সড comparison start করব i index এর সাথে  j + k + 1 index এর  ।

কোড

	int minimumExpression ( string s )
	{
	s = s + s ;
	int len = s.size() , i = 0 , j = 1 , k = 0 ;
	while( i + k < len && j + k < len )
	{
	if( s[i + k] == s[ j + k ] ) k++;
	else if( s[i + k] > s[ j + k] )
	{
	i = i + k + 1 ; // surely can escape this points
	if( i <= j ) i = j + 1 ; // as j is smallest now we will start from j + 1 minimum
	k = 0 ;
	}
	else if ( s [ i + k ] < s[ j + k ] )
	{
	j = j + k + 1 ;
	if ( j <= i ) j = i + 1 ;
	k = 0 ;
	}
	}
	return min( i , j ) ;
	}

view raw ME3.cpp hosted with ❤ by GitHub

এই কোডের রান টাইম হবে O(n) .

Practice Problem ::: 1 , 2 , 3 , 4

BFS/DFS part - 1

BFS/DFS কি , কিভাবে কাজ করে এই ব্যাপারে আমি আর কিছু লিখতে যাচ্ছি না । অনেক ভাল ব্লগ লেখা হইছে এইটা নিয়ে । এইখানে আমার ইচ্ছা BFS/DFS দিয়ে কিছু interesting problem কিভাবে সল্ভ করা যায় এর solve ট্রিক্স লিখে রাখা । যদি কারো এই এল্গরিথম নিয়ে কোন আইডিয়া না থাকে তাহলে নিচের লিঙ্ক থেকে দেখে নিতে পারে ।

1. BFS 
2. DFS    
3. youtube  

যারা একদমই নতুন নতুন BFS/DFS শিখেছে তাদের এই জন্য লিখাটা খুব একটা উপকারি হবে না । আমি চেস্টা করছি কিছু interesting problem এর solution process বলার জন্য ।

Xor-Tree ::
এই প্রবলেম এ বলা হইছে আমাদের একটা tree input দেওয়া হবে । প্রাথমিক ভাবে এর কোন নোডে কি কি ভ্যালু আছে ( ভ্যালু শুধু মাত্র ১/০ ) আছে তাও দেওয়া আছে । আমাদের একটা টার্গেট প্রসেস এ যাইতে হবে । এইখানে আমরা  কিছু কাজ করতে পারি ।

1.  আমরা চাইলে কিছু নোড এর ভ্যালু ফ্লিপ করে দিতে পারি ( মানে এখন আছে ১ তাহলে হয়ে যাবে ০ , যদি থাকে ০ তাহলে হয়ে যাবে ১ ) 
2. যদি আমরা ফ্লিপ করি তাহলে তার চাইল্ডের চাইল্ড মানে , আমরা এখন যদি থাকি   লেভেল ২ এর কোন নোডে । তাহলে লেভেল ৪ , ৬ , ৮ ......।। নোডের ভ্যালুও ফ্লিপ হবে ।   

আমাকে বলতে হবে আমি মিনিমাম কতটা ফ্লিপ অপারেশন এর মাধ্যমে এখন যেই অবস্থাতে আছি তা থেকে আমি আমার target stage এ  পৌঁছাতে পারব ।
আমরা কিছু সিন্ধান্ত নিতে পারি যেহেতু এইটা একটা ট্রি তাই । 

1.  এইখানে রুট বলা হইছে নোড ১কে ।  রুট থেকে আমি DFS চালাব । 
2. যখনই আমি দেখব আমার কারেন্ট যে ভ্যালু আছে তা আমার টার্গেট ভ্যালু এর সাথে ম্যাচ করছে না তখনই আমি ফ্লিপ করে দিব । যদিও এইটা দেখার আগে আমাকে দেখে নিতে হবে আমার কারেন্ট যে ভ্যালু আছে তার কোন দাদা বা দাদার দাদা এর থেকে তার ভ্যালু এখন ফ্লিপ হচ্ছে কিনা । 
3. কারেন্ট যে ভ্যালু আছে তা ফ্লিপ করতে হবে কি হবে না এইটা বুঝার জন্য আমাকে একটা ভ্যারিএবল রাখতে হবে । 
4. DFS call হবে এইরকম ভাবে DFS( current_node , parent , need_to_flip_now , need_to_flip_my_child )

কোড 

	const int NX = 1e5 + 10 ; // limit of the graph
	vector < int > g[NX] , ans ;
	int given[NX] , target[NX] ;
	void dfs( int curren_node , int parent , int need_to_flip_now , int need_to_flip_my_child )
	{
	if( need_to_flip_now ) given[current_node] ^= 0 ;
	if( given[current_node] != target[current_node] )
	{
	ans.push_back( current_node ); // we need to flip that node ;
	need_to_flip_now ^= 0 ;
	}
	for ( int u = 0 ; u < g[current_node].size() ; u++ )
	{
	if( g[current_node][u] != parent ) dfs( g[current_node][u] , current_node , need_to_flip_my_child , need_to_flip_now);
	// look here we swap the variable need_to_flip_now to need_to_flip_my_child
	// as what is need_to_flip_my_child is the next level need_to_flip_now
	}
	}

view raw one.cpp hosted with ❤ by GitHub

রান টাইম হবে O(node)
Distance in Tree :
এইটা অনেক চমৎকার একটা প্রবলেম । আমাদের একটা ট্রি দেওয়া হবে , আর একটা ভ্যালু K দেওয়া থাকবে , আমাদের বলতে হবে আমরা ট্রিতে কতটা distinct pair of nodes পাব যাদের মধ্যে distance হবে আমার K ।
প্রবলেমটা পড়ে একটু কঠিন মনে হইল এর সমাধান অনেক ইজি । tree dp এর প্রবলেম ও বলে এই ধরনের প্রবলেমকে ।
কিভাবে করর :

1. যেহেতু এইটা রুটেট ট্রি , কোন রুট u হলে , এর দুইটা চাইল্ড v আর w হইলে , তাদের মধ্যে distance হচ্ছে , v - u প্লাস u - w .
2. আমরা খুব সহজেই তাহলে কোন রুট এর দুইটা সাব ট্রি থেকে এর চাইল্ডের মধ্যে k distance এর রিলেশন পেতে পারি । রিলেশনটা হবে
    
          Ans += (  j = 1 to k ) dp[u][j-1] * dp[v][ k - j ]   ;
   এইখানে ,
        ( j - 1 + k - j + distance( u , v )  == k )
3. এখন প্রতিটা সাব ট্রি এর ক্যালকুলেশন এর পর আমার ট্রি এর নোড এর লেভেল আপডেট করব ।   

             ( j = 1 to k ) dp[u][j] += dp[v][j-1] ;

কোড :

	const int NX = 50000 + 10 ;
	const int MX = 500 + 10 ;
	vector < int > adj[NX];
	int deg[NX];
	int dp[NX][MX] ;
	Long ans ;
	int n , k ;
	void dfs( int x , int par )
	{
	dp[x][0] = 1 ;
	rep( i , deg[x] )
	{
	int u = adj[x][i];
	if( u == par ) continue ;
	dfs( u , x );
	for ( int j = 1 ; j <= k ; j++ ) ans += (Long) ( dp[x][j-1] * dp[u][k-j]); // লেফট এবং রাইট সাব ট্রি এর মধ্যে রিলেশন থেকে আন্সার এড করছি
	for ( int j = 1 ; j <= k ; j++ ) dp[x][j] += dp[u][j-1] ; // রুট থেকে কত দুরুত্বে কয়েকটা নোড আছে আপডেট করছি
	// আমাদের শুধুমাত্র k distance এর নোড গুলা বিবেচনা করতে হবে ।
	}
	}

view raw dfs2.cpp hosted with ❤ by GitHub

এই কোডের রান টাইম হবে O( Node * K ) .

Find Lexicographically Smallest Permutation :
আমাদের এই প্রবলেম এ বলা হইছে আমাদের একটা N সাইজের Array দেওয়া থাকবে । এই array থেকে lexicographically smallest permutation আমাদের প্রিন্ট দিতে হবে কিন্তু এইখানে একটা রেস্ট্রিকশন দেওয়া আছে আমরা চাইলেই যেকোন পজিশন এর ভ্যালু swap করতে পারি না । আমাদের কিছু good position দেওয়া আছে আমরা শুধু মাত্র সেই পজিশন এর মধ্যে ভ্যালু swap করতে পারি ।

Observation 1 :

এইখানে যদি আমরা লক্ষ্য করি complete connected position গুলাতে Array তে যাই ভ্যালু থাকুক না কেন আমরা এই পজিশন গুলার মধ্যে যেহেতু swap করতে পারি ফাইনাল array তে অবশ্যই এই পজিশনগুলার মধ্যে sorted value থাকবে ।

Observation 2:
আমরা যদি এখন observation 1 এর আইডিয়া থেকে array এর উপর dfs চালাই তাহলে আমরা complete connected position গুলার সাথে সাথে আমরা ফাইনাল array তে কি থাকবে তাও পেয়ে যাব ।

	const int NX = 1e3 + 10 ;
	vector < int > comp , tmp ;
	vector < int > adj[NX];
	bool vis[NX];
	int n , m , inp[NX] ;
	void clean()
	{
	rep( i , n + 4 )
	{
	vis[i] = 0 ;
	adj[i].clear();
	}
	}
	void dfs( int x )
	{
	int sz = adj[x].size();
	vis[x] = 1 ;
	comp.pb(x);
	tmp.pb(inp[x]);
	rep( i , sz )
	{
	int u = adj[x][i];
	if( vis[u] ) continue ;
	dfs(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
	int cs , t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	n = II , m = II ;
	clean();
	rep( i , n ) inp[i] = II ;
	rep( i , m )
	{
	int x = II , y = II ;
	x-- , y-- ;
	adj[x].pb(y);
	adj[y].pb(x);
	}
	rep( i , n )
	{
	if( vis[i] == 0 )
	{
	dfs(i);
	sort(comp.begin() , comp.end());
	sort(tmp.begin() , tmp.end());
	int sz = comp.size();
	rep( j , sz )
	{
	inp[comp[j]] = tmp[j];
	}
	comp.clear();
	tmp.clear();
	}
	}
	for( int i = 0 ; i < n - 1 ; i++ ) printf("%d ",inp[i]);
	printf("%d\n",inp[n-1]);
	}
	return 0;
	}

view raw dfs3.cpp hosted with ❤ by GitHub

এই কোডের রান টাইম কি হবে ? এইটা পাঠকদের উদ্দেশ্যই রেখে দিলাম :D

ইচ্ছা আছে এই সিরিজটা আরো বড় করার । ধন্যবাদ পড়ার জন্য । 

Light OJ DP ( part - 1 )

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

বিশেষ কিছু ডিপি ট্যাকনিক আছে , যেমন ( LCS , LIS , MCM , Digit DP , 0/1 knapsack , Bit Mask , min vertex,  Expected Value , N Queen type এমন ) . এইখানে প্রবলেম আইডি ধরে এমন ক্যাটেগরিতে ফেলার চেস্টা করছি ।  যেহেতু অনেক প্রবলেম এই আমার সল্ভ নাই এখনও এমন অনেক কিছু নিয়েই জানি না সব প্রবলেম করা সম্ভব হচ্ছে না । লিস্টটা আমি যথা সম্ভব আপডেট করতে থাকব । কোন প্রবলেম এর ক্যাটেগরি ভুল থাকলে বা নতুন প্রবলেম এর ক্যাটেগরি সম্পর্কে কমেন্ট এ বলতে পারেন ।

Bit Mask :::  
1011 ,  1018 ,  1021 ,  1037 ,  1057 , 1061 ( + N Queen ) , 1073 ( + KMP ) , 1086 ( +Euler trail )  .   1092 , 1119 , 1158  , 1228 , 1264 ( sub set mask ) ,  1270 , 1287 ( + Expected value ) , 1316 ( + Dijkstra ) , 1327 , 1406 ( subset mask ) ,

Binary Search ::: 
1170 , 1180 , 1360 ,

Coin Change ::: 
1079 , 1147 , 1226 , 1231 , 1232 , 1233 ,

Counting ::: 
1095 ,  1140 , 1170 ( + Binary search ) , 1302  , 1326  , 1329 , 1382

Digit DP :::  
1032 , 1068 ,  1140 , 1205 , 1394 ,

Edit Distance :::
1013 ( + LCS  ) , 1025 ,  1033 ,  1051 ,  1159 ( can be solved by suffix array ) , 1351 , 1420

Expected Value ::: 
1027 , 1030 , 1038 ,  1287 ( +  Bit Mask ) , 1364 ,


0/1 Knapsack ::: 
1017 , 1106 , 1125 , 1169 , 1200 , 1217 ,

KMP ::: 
1073 ( + Bit Mask ) , 1334 ,

LCS ::: 
1013 ( + Edit distance  ) , 1110 , 1157 ,

LIS ::  
1277 , 1421 .

MCM :::  

1031 , 1044 ,  1283 , 1302  , 1422

Min vertex Cover ::: 
1201 , 1230 ,

Non Classical :::  1004 ,  1036 , 1047 ,  1060 , 1071 , 1084 , 1105 , 1122 ,1134 , 1173 , 1191 , 1295 , 1345 ,

N Queen :::  
1005 ,  1061 ( + Bit Mask ) ,

Probability ::: 
1050 , 1064 ,

Space Reduction ::: 
1126 ,  1145

Subset Mask ::: 
1264 , 1406

DP on Tree :: 
1257 , 1382

Dp with BIT ::: 
1415

two pointer

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

আমাদের বলা হল আমাদের কাছে দুইটা সর্টেট array আছে , আমাদের বলতে হবে এই দুইটা array থেকে একটা একটা ভ্যালু নিয়ে আমরা কতভাবে একটা নাম্বার M বানাতে পারি যাদের কোন মধ্যে কোন ডুপলিকেট ভ্যালু নেই ।

যদি আমরা একটু Naive Method দেখি -

	const int NX = 1e5 + 10 ; // limit of the array
	int A[NX] , B[NX] ; // two array , both are ascendingly sorted
	int M ; // value that we need to match
	int N ; // Size of the Array
	void solve()
	{
	int ans = 0 , i , j ;
	for ( i = 0 ; i < N ; i++ )
	{
	for ( j = 0 ; j < N ; j++ ) if( A[i] + B[j] == M ) ans++;
	}
	return ans ;
	}

view raw one.cpp hosted with ❤ by GitHub

এইখানে আমরা inner এবং outer for loop এর দুইটা relation এর মাধ্যমে খুব সহজে Ans বের করে দিতে পারি ।


আমরা  এইখানে N পর্যন্ত দুইটা লুপ চাল্লাচ্ছি । তাই আমাদের টোটাল রানটাইম হয়ে যাচ্ছে  O( N ^ 2 ) । আমরা যদি একটু Modification করি আমরা এইটা কমিয়ে O(N) এ নিয়ে আসতে পারি ।  আমরা দুইটা পয়েন্ট নেই ।
Say low and high । low পয়েন্ট করতেছে আমাদের A array এরটার starting point কে এবং high পয়েন্ট করতেছে আমাদের B array এর ending পজিশনটাকে ।

Observation number one ::

আমরা যদি দেখি A[low] + B[high] > M তাহলে আমরা একটা জিনিস সিউর ভাবে বলতে পারব । আমাদের অবশ্যই B এর ভ্যালু কমাতে হবে । কারণ যেহেতু A[low] হচ্ছে A এর সবথেকে ছোট ভ্যালু সুতরাং  তাকে আর কমিয়ে কখনই B[high] এর সাথে add করে M বানানো যাবে না ।

Observation number two :::

আমরা যদি দেখি A[low] + B[high] < M তাহলে আমাদের অবশ্যই low এর ভ্যালু বাড়াতে হবে । কারণ high হচ্ছে B এর সবথেকে বড় ভ্যালু এর থেকে বড় ভ্যালু নাই । high থেকে আমরা কোন ভ্যালু বাড়াতে পারছি না । তাই অবশ্যই আমাদের এখন low থেকে বাড়াতে হবে ।

এইখানে একটা খটকা লাগতে পারে Observation one এ  যেহেতু A[] array তে left to right যাওয়া হচ্ছে current low ভ্যালু মানে low যাকে right now point করছে A[] array তে তার থেকেও তো কম ভ্যালু আমার array তে থাকতে পারে । আমরা নিচের কোডটা একটু ভাল মত খেয়াল করলেই দেখতে পাব যে যদি থেকে থাকে এবং তার সাথে যদি high B[] array এর এড যদি M এর সমান হয় তাহলে তা আগেই Ans এর সাথে এড হয়ে আসবে ।  একদমই একই কাজ হচ্ছে B[] array তেও । এইখানে আমরা condition দিয়ে দুইটা পয়েন্টকে নিয়ন্ত্রণ করছি ।

	const int NX = 1e5 + 10 ; // limit of the array
	int A[NX] , B[NX] ; // given array , ascending order sorted
	int N ; // limit of the array
	int M ; // We need to make M by using this two array
	void solve()
	{
	int ans = 0 , low = 0 , high = N - 1 ;
	while( low < N )
	{
	while( A[low] + B[high] > M && high > 0 ) high--;
	if( A[low] + B[high] == M ) ans++;
	low++;
	}
	return ans ;
	}

view raw two.cpp hosted with ❤ by GitHub

এইখানে আমরা low and high দুইটা পয়েন্ট merge করে আগাচ্ছি । এই ধরনের ট্যানিক এ প্রবলেম সল্ভ করাই হচ্ছে two pointer method .

এখন আমরা আরেকটা প্রবলেম এর মাধ্যমে two pointer এর মাধ্যমে কিভাবে প্রবলেম সল্ভ করা হয় এইটা দেখব ।
problem  এইখানে আমাকে N টা নাম্বার দেওয়া থাকবে এবং একটা ভ্যালু দেওয়া থাকবে say S । আমাকে minimum length এর consecutive sub sequence  বের করতে হয়ে যাতে এই consecutive sub sequence এর sum, S এর থেকে বড় বা সমান হয় ।

এই প্রবলেম অনেক এপ্ররোচে আমাদের করা যাবে মনে হইতে পারে । কিন্ত o(n) runtime আনা ব্যাতিত্ব এই প্রবলেম সল্ভ হবে না । o(n) runtime আমরা two pointer ট্যাকনিক এর মাধ্যমে আনতে পারি ।

একই ভাবে আগের প্রবলেম এর মত এইখানে আমরা দুইটা পয়েন্ট নিব । low , high । প্রাথমিক ভাবে দুইটা পয়েন্ট এই given number array এর starting point indicate করে । যতক্ষণ পর্যন্ত না low থেকে high এর sum  , M এর ভ্যালু ক্রস না করে আমরা high এর ভ্যালু বাড়াইয়া যাব । যখনই ক্রস করবে বা সমান হবে তখনই আমরা current length check করব ( high - low + 1 ) যদি minimum ans update করা যায় তাহলে update করব ।  যখনই sum  এর ভ্যালু M এর থেকে বড় হয়ে যাবে তখন আমরা low এর ভ্যালু বাড়ানো সাথে সাথে sum এর ভ্যালু ও adjust করতে থাকব ।

কোডটা দেখলে ব্যাপারটা ক্লিয়ার হয়ে যাবে

	//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 memo(a,b) memset((a),(b),sizeof(a))
	#define G() getchar()
	#define MAX3(a,b,c) max(a,max(b,c))
	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 ****************************************** */
	typedef long long ll ;
	const int MX = (int) 1e6+100;
	ll inp[MX] , S;
	int n ;
	int main()
	{
	// ios_base::sync_with_stdio(0); cin.tie(0);
	while(scanf("%d %lld",&n,&S)==2)
	{
	int low = 0 , high = 0 , ans = n+1 ;
	int i ;
	for ( i = 0 ; i < n ; i++ ) read(inp[i]);
	ll sum = inp[0];
	// Algorithm
	/*
	*/
	while( high < n )
	{
	if( sum >= S )
	{
	int temp = high - low + 1 ;
	if( temp < ans ) ans = temp ;
	}
	if( sum >= S && low < high )
	{
	sum -= inp[low];
	low++;
	}
	else if( sum < S )
	{
	high++;
	if( high < n )
	sum += inp[high];
	}
	}
	if( ans == n+1 ) ans = 0 ; // value possible na
	printf("%d\n",ans);
	}
	return 0;
	}

view raw nine.cpp hosted with ❤ by GitHub

এখন যদি আমরা এই কোডটার রান টাইম দেখি । কোডটা high = 0 থেকে high < len পর্যন্ত চলছে । মানে O(n) এ ।

two pointer এর আরো একটা problem হচ্ছে এইটা  । এইখানে আমাদের given array দেওয়া হ্য়নি । আমাদের given formula দিয়ে input ready করে নিতে হবে । এইটা বাদে almost same প্রবলেম হিসাবে মিলে যাচ্ছে আগের প্রবলেমটার সাথে ।

two pointer এর আরো প্রবলেম আইডি এইখানে কমেন্ট জানালে আমি এড করে দিতে পারব । বা কোন ট্যাকনিক কমেন্ট এ দিলে সবাই জানতে পারবে ।

Happy coding :)

Practice Problem :: 1 , 2 .