Binary Search part - 1

 বাইনারি সার্চ কি ? 

বাইনারি সার্চ হচ্ছে একটা sorted array তে কোন Key value (  যেইটা আমি খুঁজে বের করতে চাচ্ছি ) এর position বের করা । অধিকাংশ  ভার্সিটিতেই ফাস্ট ইয়ারের কোন না কোন কোর্সে ( আমি প্রথম জানতে পারি আমার ১/২ এর ডিসক্রিট ম্যাথ কোর্সে ) পড়ানো হয় তাই  আল্গরিথম নিয়ে কারো কোন প্রবলেম থাকে না , প্রবলেম হয় এর Use এ । কখন কোথায় আমার বাইনারি সার্চ লাগবে এইটা ধরতে । পৃথিবীর অনেক সুন্দর আল্গরিথম এর মধ্যে আমার মনে বাইনারি সার্চ একটি । কত কঠিন দেখতে লাগা প্রবলেম গুলাকে কত easy করে দেয় ।
আমি ধরে নিচ্ছি যারা এইটা পড়ছে সবারই Binary search নিয়ে idea আছে । কিভাবে code হয় । যদি তাও কারো না থেকে থাকে তাহলে নিচের দুইটা লিঙ্ক দেখলেই সবার ক্লিয়ার হয়ে যাবে । 

(১) টপ কোডার বাইনারি সার্চ                                                                                                              

(২)আসিফের হ-য-ব-র-ল ( Painless Binary Search )                                                                        

আমার এই লেখাটার উদ্দেশ্য হচ্ছে কিছু interesting problem এ আমি যদি binary search চালাই তাহলে  কিভাবে solution আমি খুব সহজেই পেয়ে যাই তা আলোচনা করা । আমি নিজে খুবই বাজে কোডার হয়ত আমার প্রসেস গুলা থেকেও ভাল প্রসেস আছে আমি এই প্রসেস এ AC পাইছিলাম তা আলোচনা করার চেস্টা করতেছি । লিখাটা আমার অনেক গুলা পার্ট এ করার ইচ্ছা আছে কারণ binary search এর এত এত সুন্দর problem আছে একটা পার্ট লিখা সম্ভব না :D

যেসব জিনিসপাতি সবাই জানি :

আচ্ছা যদিও আমরা সবাই জানি তাও কয়েকটা বিষয় আগে রিভাইস দিয়ে নেই বাইনারি সার্চ এর প্রবলেম দেখার আগে । 

•  কোন sorted array binary search চালানো মানে lg(n) এর calculation করা । lg(n) এর মানে আমি কিছুটা এমন কল্পনা করতে পারি যদি n এর value  ১০০ হয় তাহলে  ১০০  < ২ ^  ( এর যে পাওয়ার use করলে এর মান বড় হয় তত গুলা অপারেশন ) যেমন এইখানে ৭ ,  ১০০ < ২ ^ ৭ ( ১২৮ ) । অর্থাৎ যদি ১০০ length এর কোন array এর উপর আমার বাইনারি সার্চ চালানো হয় তাহলে আমার মাত্র ৭টা অপারেশন করা লাগবে । 
• বাইনারি সার্চ আমি শুধু মাত্র sorted value এর উপর করতে পারব । 
• lower_bound ( আমাকে একই value এর অনেক গুলা জিনিস থাকলে এদের সবার প্রথমের value এর index return করবে ) ও upper_bound  ( almost same as lower_bound this time we will get the highest index of the key value + 1 , if there is no match then we will get immediate highest index ) 

Light Oj 1048 - Conquering Keokradong :::

এই প্রবলেমটা অনেক interesting . আমি  Keokradong climb করতে যাচ্ছি এর জন্য আমাকে  বিভিন্ন ক্যাম্পের distance দেওয়া আছে । ( এইখানে একটা ক্যাম্পের distance আর আগের ক্যাম্পের সাপেক্ষে ) . এখন আমাকে একটা লিমিট দেওয়া হইছে ( K ) এর মানে হইল আমাকে আমার পুরা tripটা k+1 camp এ নিয়ে আসতে হবে ( যেখানে আমি K night থাকব ) কিন্তু এমন ভাবে যেন আমার দুইটা ক্যাম্পের distance এর maximum value minimum হয় , আসলে এইখানে বলা হইছে আমি highest আমার trip কে k+1 এ ভাগ করতে পারি কিভাবে যেখানে পর পর ক্যাম্পের মধ্যে distance সব থেকে কম হয় । 

এখন দেখি প্রবলেমটা পড়ার সাথে সাথে আমার মাথায় কি কি চিন্তা আসতে পারে । প্রথমত আমাকে আসলে এমন কোন value নিতে হবে যাতে আমার পর পর ক্যাম্পের মধ্যে Distance কম হয় যদি দেখি এইটা কম আছে তাহলে আমি ওই ক্যাম্পটা skip করে Ans generate করার চেস্টা করব । আমাকে এমন sample case দেওয়া হইছে আমি Idea পাওয়ার সাথে সাথে মনে হবে আরে এমনই । ইয়েস পাইছি Idea । কোড করে সাথে সাথে submit এমন সুন্দর একটা verdict "Wrong Answer"  । ও আচ্ছা আমি এইটা মিস করছি আমাকে N এর value 1000 দেওয়া হইতে পারে এমন K এর মান হইতে পারে min ( N , 300 ) । তাহলে skipটা N-k শুধু একটা value এর উপরও হয়ত থাকতেছে না আমাকে অনেক গুলা position এই এমন কাজ করতে হয়ত হইতে পারে । মানে এমন অনেক কেস এই থাকবে যেখানে আমাকে এমন করে দেখতে হবে । আচ্ছা তাইলে বুঝছি DP করে করত হবে , অর্থাৎ আমাকে খালি বের করতে হবে skip পয়েন্ট গুলা কোনগুলা । normal sense এ যখন দেখি N এর মান 10000 হয়( মানে একটা ক্যাম্প থেকে অন্য ক্যাম্পের distance ) হইতে পারে মানে যদি আমি Dp করতে যাই তাহলে worst case এ N-k == 999*10000 == 9990000 লাগতেছে আর position er junno 1000 তো আছেই । অর্থাৎ যদি কোন compiler dp[1000][9990000] এমন কিছু declear করার permission আমাকে দেয় এবং অভয় দেয় পাগলা কোড কর আমি দ্রুতই Ans generate করে দিব তাহলে আমি একটা try দেওয়ার হইলেও দিতে পারতাম । যেইটা বর্তমান সময়ে কেউ দিচ্ছি না so dp এর চিন্তা বাদ । এতক্ষণ আমি খালি value skip এর পয়েন্ট নিয়েই চিন্তা ভাবনা করছি এখন এইটা বাদ দিয়ে দেখি অন্য কিছু ভাবা যায় নাকি । আসলে আমার main concern এর ব্যাপাটা হইল max value । আমি যদি max value ঠিক করে দেখি এমন কিছু করা possible কিনা মানে এই Max value এর জন্য আমার পুরা tripটাকে K part এ ভাগ করা যায় কিনা । যদি যায় তাহলে আমি Max value কমাইয়া দেখব এইভাবে possible হচ্ছে কিনা যদি হয় তাহলে কম Max value এর আমার Ans . এই কাজটাই আমি খুব সহজেই binary search এ করতে পারি । এইখানে Max value এর highest value  কি হইতে পারে সবগুলা ক্যাম্পের distance এর যোগফল কারণ এর চেয়ে বেশি কিছু আমার লাগতেছে না । আর lowest অবশ্যই পর পর দুইটা ক্যাম্পের মধ্যে যে distance তাদের মধ্যে highest টা ( কারণ K <= min ( n , 3000 ) ) .এখন All possible এর মধ্যে আমি lowest possibleটা নিব মানে এইখানে আমার lower_bound এর concept লাগতেছে । 

	code টা কিছুটা এমন হবে
	N --- > ( N+1 ) camp given
	K ----> আমাকে ক্যাম্প সাইটা গুলাকে আমি highest K+1 part করতে পারি
	// checking এর পার্ট এর কোড
	bool Binarysearch ( int expected_max )
	{
	int commutative_sum = 0 , part = 0 ;
	for i = 0 -- > size_of_Array Inp // given camp sites are here mainly n+1 is array size
	{ commutative_sum += inp[i] ;
	if ( commutative_sum > expected_max ) // মানে যদি আমি এই camp সাইট টাও নেই তাহলে আমার expected_max distance থেকে আমার বসানো ক্যাম্প গুলার distance বড় হইতেছে । মোট কথা আমি এই কাজটা করতে পারি না
	{
	part++ ; // এইখানে আমাকে অবশ্যই একটা ক্যাম্প বসানো লাগতেছে
	commutative_sum = inp[i] ; // এইখান থেকে আমার শুরু করব
	}
	}
	return part <= K ; // possible expected _ value
	// Binary search এর পার্ট
	int low = max_value ; // highest camp value
	int high = total_sum ; // its possible to take to no night for sleep :D but for sure there will be smaller value where we can take k nights thus distance between two consecutive camp sites will be lesser .
	int expected_ans = high ;
	int mid ;
	while ( low <= high )
	{
	mid = ( low + high ) / 2 ;
	if ( Binarysearch( mid ) ) // its possible
	{
	expected_ans = mid ;
	high = mid - 1 ; // now we try to generate lesser expected_ans
	}
	else low = mid + 1 ; // its not possible so we need to increase low
	}
	print -- > expected_ans // এইটা highest max value

view raw example.cpp hosted with ❤ by GitHub

ক্যাম্প সাইট পিন্ট এর কাজটা এর পর অনেক সোজা । তাই আর আলোচনা করতেছি না । সবাই এখনই বুঝে গেছে না গেলে খাতা কলমে চিন্তা করে বের করতে হবে :D সব তো বলা ঠিক না :D 

প্রিন্ট এর কাজ বাদ দিয়ে same concept এ একটা প্রবলেম আছে এই প্রবলেম এর solution process বুঝা হয়ে গেলে  এইটাও সবার Try করা উচিত ।
 Light Oj 1076

Renting Bikes :::: 

এইটা আরেকটা খুবই চমৎকার binary search এর প্রবলেম । এই প্রবলেম এ কি বলা হইছে বলি । এইখানে বলা আছে N টা school boy আছে যাদের কোন bike নাই তারা bike রেন্ট নিতে পারে । যে site bike rent দেয় তাদের M টা bike আছে । প্রতিটা bike rent এর জন্য আলাদা আলাদা ফিক্সড প্রাইজ আছে । school boy গ্রুপ এর কিছু কমন মানি আছে ( সবার চাঁদা ধরতে পারি ) যেই টাকা তারা bike rent এ use করতে পারে কিন্তু কেউ নিজের টাকা থেকে অন্যকে টারা ধার দিতে পারে না এবং তারা রেন্ট নেওয়া বাইক শেয়ার ও করে না । আমাকে বলতে হবে maximum কয়টা boy bike রেন্ট নিতে পারবে এবং তাদের মিনিমাম কতটা খরচ করতে হইতে পারে ( মানে নিজেদের টাকা ) । 

প্রবলেমটা পড়ার সাথে সাথে মাথায় Idea আসে এইটা অবশ্যই greedy problem এমন কোন না কোন ভাবে sorting করে value গুলা use করতে হবে এবং অবশ্যই আমি যার নিজের টাকা বেশী তাকে বাইক দিতে চেস্টা করব । যদি আমি আরো একটু ভাবি যদি আমি ঠিক করে ফেলি আমি ৩জন কে bike দিব তাহলে অবশ্যই এইটা সবথেকে ভাল যার সবথেকে বেশী টাকা পয়সা আছে ও কিনবে ৩ নাম্বার সব থেকে কম cost এর বাইক , তারপরের জন্য ২ নাম্বার , এবং শেষজন সবথেকে কম cost এর বাইক । এই যে 3 জন ফিক্সড করে চেক করা এইটাই তো বাইনারি সার্চ :D আর যদি আরও একটু ভাবি code টা হবে upper_bound এর মত অর্থাৎ আমি সব সময় চেস্টা করব যেন আমি সব থেকে বেশী জন নিতে পারি । আর একটা পয়েন্ট আমি সব সময়ই আমার common money এর পুরাটাই use করব । 

    কোড

Present  :::: 

এইটা ও খুব চমৎকার প্রবলেম । এইখানে বলা হইছে beaver নামে এক পিচ্চি নতুন প্রোগ্রামিং শিখতেছে । ও তার প্রিয় ম্যামকে ম্যামের বার্থডে তার বাগানের ফুল গিফট করতে চায় ( ছেলে চালু পাবলিক :P ) । কিন্তু এইটা bad manners to present little flowers কিন্ত্ তার বাগানের ফুলগুলা হঠাৎ করে আর বড় হচ্ছে না এখন এর m days বাকি আছে বার্ডে থেকে । ও স্পেশাল একটা water পাইছে যেইটা দিলে next day তে ফুল গুলা 1 unit height বাড়ে । কিন্ত্ প্রবলেম হইল এই special water ও w wide এর contiguous flower কে শুধু মাত্র স্প্রে করতে পারে একদিনে  । আমাকে বলতে হবে ফুলগুলার minimum height কত হবে gift এর সময় মানে গিফট দেওয়া ফুলাগুলার মধ্যে কোন ফুলের height সব থেকে কম হবে ।  

    আমি যখনই দেখব আমাকে Min বা Max এর কোন ক্যালকুলেশন এর প্রয়োজন হচ্ছে আমি চেস্টা করে দেখব যে এইটা কোনভাবে binary search এ ফেলা যাচ্ছে কিনা । অধিকাংশ ক্ষেত্রেই দেখা যাবে Ans আসসে বা যদি দেখি Ans আসতেছে আমি binary search করার চেস্টা করব । এই প্রবলেমটা দেখি আমাকে কি করতে হবে । আমি ফুলগুলার highest min value calculation করব for sure এইটা করতে হবে binary search এ । আর যদি একটু ভাবি এতে upper_bound এর একটা ভাব আছে । all possible Ans থেকে আমি ম্যাক্স নিব । এখন দেখি কিভাবে । 

	// Binary search এর পার্ট
	typedef long long ll ;
	ll inp[1000000] ; // size of initial flower
	ll updated[1000000] , n , m , w ;
	ll BinarySearch(ll expected_height, ll left)
	{
	int i , j , start ;
	for ( i = 0 ; i < n ; i++ ) updated[i] = 0 ; // initially all zero
	for ( i = 0 ; i < n ; i++ )
	{
	if( i ) updated[i] += updated[i-1]; // update value if its previously updated
	ll need = expected_height - inp[i] - updated[i] ; // need to do
	if ( need > 0 ) // we need to spray water
	{
	left -= need ; //
	updated[i] += need ;
	updated[i+w] -= need ;
	}
	if(left < 0 ) return 0 ; // if left is less then zero this mean its need more days to spray water
	// to grow flower that expected_height which is n't possible
	}
	return 1;
	}
	// Main এর পার্ট
	ll Ans , mid ;
	low = 0;
	high = 1000000000000000000 ; // large value
	while( high >= low )
	{
	mid = (high + low)/2;
	if(posible(mid,m)) // here m days left
	{
	Ans = mid ; // current best answer
	low = mid + 1 ; // check the next upper_value
	}
	else high = mid - 1; // need to check lesser value
	}
	cout << Ans << endl;

view raw second.cpp hosted with ❤ by GitHub

টানা লিখা আসলে অনেক ধৈর্যের  ব্যাপার :P আর পারতেছি না এখন লিখলেও খারাপ হবে । Next part এ আরও কিছু interesting প্রসেস লিখার চেস্টা করব । আর কেউ ভাল কোন প্রবলেম করে থাকলে কমেন্ট এ সবার জন্য suggest করতে পারেন যাতে আমরা সবাই এইখান থেকে শিখতে পারি ।