Wednesday, September 24, 2014

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 লাগতেছে । 




ক্যাম্প সাইট পিন্ট এর কাজটা এর পর অনেক সোজা । তাই আর আলোচনা করতেছি না । সবাই এখনই বুঝে গেছে না গেলে খাতা কলমে চিন্তা করে বের করতে হবে :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 থেকে আমি ম্যাক্স নিব । এখন দেখি কিভাবে । 
টানা লিখা আসলে অনেক ধৈর্যের  ব্যাপার :P আর পারতেছি না এখন লিখলেও খারাপ হবে । Next part এ আরও কিছু interesting প্রসেস লিখার চেস্টা করব । আর কেউ ভাল কোন প্রবলেম করে থাকলে কমেন্ট এ সবার জন্য suggest করতে পারেন যাতে আমরা সবাই এইখান থেকে শিখতে পারি ।




















3 comments:

  1. ভাইয়া আসিফ ভাই এর ব্লগ টা কাজ করছে না ? একটু দেখবেন কি ?

    ReplyDelete
    Replies
    1. https://github.com/abuasifkhan/abuasifkhan.me/blob/gh-pages/_posts/2014-06-20-painless-binary-search.md

      Delete
  2. আমার তথ্য উন্নত করতে চমৎকার নিবন্ধ। দরকারী তথ্য ভাগ করার জন্য আপনাকে ধন্যবাদ
    ওয়েব প্রোগ্রামিং টিউটোরিয়াল
    স্বাগত খোলার

    ReplyDelete