Digit Dp

Digit Dp এইখানে নামের সাথে এর কাজ এর মিল আছে , যখন কোন র‍্যাঞ্জের নাম্বারের মধ্যে পার ডিজিট নিয়ে কাজ করতে হয় , যেমন আমাদের একটা নাম্বারের র‍্যাঞ্জ দিয়ে দিল L - R আমাদের বলতে হবে এই র‍্যাঞ্জের মধ্যে  যতগুলা নাম্বার পসিবল তাদের মধ্যে কত গুলা ০/১ আছে বা কতগুলা নাম্বার Palindrome বা কতগুলা নাম্বার কোন নিদিষ্ট নাম্বার দ্বারা ভাগ যায় ।

এই  ধরনের প্রবলেম যখন আমরা দেখব যখন পার পজিশন নিয়ে কাজ করতে হচ্ছে এবং অবশ্যই ডিজিট এর উপর ( ০ - ৯ ) এই ধরনের প্রবলেমগুলা ডিপি সল্যুশন পসিবল ( অবশ্যই অবশ্যই নাম্বার থিউরী  সল্যুশন / ফর্মুলা থাকতে পারে কিন্তু যারা ম্যাথমেটেসিয়ান না কোডার তাদের জন্য এই ট্যাকনিক জানা দরকার যার মাধ্যমে আমারা আমাদের উত্তর পেতে পারি ) । ডিজিট নিয়ে কাজ করতে হয় বলে Digit dp বলা হয় ।

প্রবলেম এর উপর নির্ভর করে আমরা আমাদের সুবিধা অনুয়ায়ী state নিয়ে কাজ করব । তবে কিছু ব্যাপার প্রায় সব প্রবলেম এই কমন থাকে , নিদিষ্ট রেঞ্জ নিয়ে কাজ করতে হয় বলে কিছু state , current_digit_position , is_current_position_is_the_starting_position or not , is_greater _then_left_range_value or not , is_less_then_right_range_value or not এমন । এইগুলা প্রবলেম এর উপর নির্ভর করে আমরা ঠিক করে নিব ।

যারা ডিপি রিলেশন , base_case কি , state কি , কিভাবে ভ্যালুগুলা different হয় , memorization কি এইগুলার সম্পর্কে ধারণা আছে তাদের জন্য digit dp solution বুঝতে পারা কঠিন কিছু না । যারা এখনও এইগুলা clear ভাবে বুঝতে পারে না তাদের জন্য আমার সাজেশন হল কিছু non classical dp ( নিজে নিজে recursion relation বের করে করা ) করা তাহলে dp relation বুঝতে সুবিধা হবে । আমি এইখানে দুইটা digit dp এর প্রবলেম এর সল্যুশন প্রসেস আলাপ করছি । problem solving শিখার সবথেকে ভাল উপায় ।

How Many Zeroes?

এই প্রবলেম এ বলা হইছে আমাদের একটা নাম্বারের রেঞ্জ দেওয়া হবে । আমাদের বলতে হবে এই র‍্যাঞ্জের মধ্যে যতগুলা নাম্বার আছে এতে কতগুলা ০ আছে ।

এখন আমরা দেখি এই প্রবলেম এর জন্য আমাদের state কতগুলা হবে । অবশ্যই একটা state হবে position । position বলতে আমরা পার digit বুঝাইতেছি । যদি 123 আমাদের কোন একটা নাম্বার হয় তাহলে 0 number position এর এ আছে ৩ , ১ নাম্বার পজিশনে আছে ২ এমন । এইখানে একটা জিনিস বলে রাখা ভাল আমরা reverse order নিয়ে কাজ করব ।  মানে হইল আমরা ১ নাম্বার পজিশন বলতে বুঝব  123 এর 1 কে ।  এর অনেক সুবিধা আছে , যেহেতু আমরা highest digit position থেকে start করছি তাহলে আমাদের পক্ষে সহজ হবে কোন নাম্বার বড় কি ছোট এইটা নির্ণয় করা । ধরা যাক আমরা ১ নাম্বার পজিশনে কিছু বসালাম না এর মানে হইল আমরা 2 , 3 নাম্বার পজিশনে  এ যাই বসাই তা অবশ্যই আমাদের রেঞ্জ নাম্বার থেকে ছোট হবে । যদি ১ নাম্বার পজিশনে  ১ বসাইয়া আসি তাহলে আমাদের একটা লিমিট থাকবে দুই নাম্বার পজিশনে নাম্বার বসানোর জন্য । আমরা শুধু মাত্র ১ , ২ নাম্বার  digit ২ নাম্বার পজিশনে বসাতে পারি , নতুবা নাম্বারটা বড় হয়ে যাবে । তাহলে আমরা আমাদের dp solution এর জন্য এইটা বুঝতে পারতাম আমাদের দুইটা state লাগবেই । ( ১ ) পজিশন ( ২ ) কারেন্ট পজিশনে এর নাম্বারটা আমাদের র‍্যাঞ্জ থেকে ছোট কিনা ( এইটক একটা 2 space এর boolean flag নিয়েই করতে পারি ) ।
এখন আরো একটা ব্যাপার দেখি আমরা যে পজিশনে আছি এইটা কি starting_position কিনা এইটা আমাদের জানা দরকার । কেন দরকার ? যদি starting_position হয় তাহলে আমরা ০ বসাতে পারব না ( শুধু মাত্র ১ digit এর নাম্বার বাদে , কোন নাম্বারের প্রথম ডিজিট ০ হতে পারে না ) । তাহলে আমাদের জন্য আরো একটা state গুরুত্বপূর্ণ । is_current_position_is_starting_position or not . আরো একটা state এর information আমাদের থাকলে সুবিধা হয় এইটা হল আমরা কতগুলা 0 বসিয়ে নাম্বারটা generate করছি । তাই আমাদের আরো একটা state হবে total_zero_so_far  । এই প্রবলেম এ আমাদের একটা রেঞ্জ দেওয়া হয়েছে আমরা এইখানে করব কি আমরা  0 - L ( left_range ) পর্যন্ত কতগুলা zero আছে তা count করবে যা আমরা 0 - R পর্যন্ত কতগুলা zero আছে তা থেকে বিয়োগ করে দিব ।



Investigation :

এই প্রবলেম এ আমাদের একটা র‍্যাঞ্জ ( L - R ) আর একটা নাম্বার k দেওয়া হবে আমাদের বলতে হবে এই র‍্যাঞ্জের মধ্যে কতগুলা নাম্বার K দ্বারা ভাগ যায় । এইখানে একটা boundary case আছে । রেঞ্জ হবে < 2^31 মানে হইল হাইস্ট ৯ ডিজিট এর কোন নাম্বার হবে । যদি K এর মান তাই 81 ( প্রতিটা ঘরে ৯ বসিয়ে আসলে হাইস্ট আমরা ৮১ এই পেতে পারি ) থেকে হলে আন্সার হল ০ । এইখানে নাম্বারটা যেমন K দ্বারা ভাগ যাবে যাবে , নাম্বারটা কি কি digit দ্বারা হচ্ছে তাদের যোগফল ও K দ্বারা ভাগ যাবে । এর মানে হইল অবশ্যই আমাদের দুইটা state হবে একটা নাম্বার এর reminder এর জন্য আর একটা digit গুলার sum এর reminder এর জন্য । অবশ্যই  পজিশন , এবং এখন starting_position কিনা এইগুলা তো আমাদের state থাকবেই । digit dp এর সব থেকে ভাল দিক হল এর সল্যুশন এখন straight forward .


প্র্যাকটিস প্রবলেম : 1 , 2

DP part - 3

DP নিয়ে আগের লিখাগুলা এই লিঙ্কে পাওয়া যাবে ।

এই পোস্টেও কিছু interesting bitmask dp problem নিয়ে লিখার ইচ্ছা আছে ।

Can You win ?

এইখানে বলা হইছে তুমি তোমার বোনের সাথে  দাবা খেলতেছ কিন্তু খুব একটা পাত্তা পাইতেছ না ।তোমার শুধু মাত্র রাজা আর একটা ঘোড়া বাকি আছে ।   তোমার বোন তার প্রিয় " ‘panju muttai" খাইতে একটু বাহিরে গেছে , এই সুযোগ একটু দুই নাম্বারি করার । তুমি n টা মুভে যদি তোমার বোনের pawn ( 'p' small p , its important . this cause me 2/3 WA ) বাদে অন্য power ( capital 'P' ) খেয়ে ফেলতে পার তোমার ঘোড়া দিয়ে তুমি জিতবা । তোমারে দাবা বোর্ড এর কারেন্ট অবস্থা বলা হইছে তোমাকে বলতে হবে তুমি জিততে পারবা কি পারবা না ।

*** পাওয়ার এর সংখ্যা ১-৮ ( যখনই লিমিট কম থাকবে তখন আমাদের জন্য ভাল , আমরা একে bitmask এ ফালাইতে পারি না হয় state বাড়াইয়া দিতে পারি )

লিমিট কম তাই আমরা সহজেই bitmask করতে পারি । আমি 4টা state এ করছিলাম । কারণ x_position < 8 , y_position < 8 , maximum_move <= 64 , mask <= ( 1 << 8 ) । টোটাল ( 8 * 8 * 64 * ( 1 << 8 ) ) == 1048576 । প্রাথমিক ভাবে আমরা আমাদের ঘোড়ার পজিশন থেকে স্টার্ট করব । তারপর দেখব আমাদের যে মাক্সিমাম মুভ দেওয়া আছে এর মধ্যে আমরা সব গুলা পাওয়ারকে খেয়ে ফেলতে পারব কি না । যদি পারি তাইলে "Yes" না হবে "No" । এইখানে আমরা আমাদের কারেন্ট পজিশন থেকে যে সব পজিশনে পাওয়ার আছে তাতে কত মুভে যাওয়া যায় এইটা বের করার জন্য bfs() চালাব ।


Headmaster's Headache :

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

এইখানে সাবজেক্ট সর্বমোট থাকতে পারে ৮টা , লিমিট যেহেতু অনেক কম তাই আমরা এই প্রবলেমটাকে bitmask করতে পারি । এখন আমাদের state কয়েকটা হবে । যেহেতু পারমানেন্ট টিচার অবশ্যই থাকবে এইটা আমাদের বিবেচনার ব্যাপার না । আমাদের বিবেচনার ব্যাপার যারা আবেদন করেছেন । অবশ্যই একটা state হইল যারা আবেদন করেছেন তাদের সংখ্যা ( সর্বমোট ১০০ জন আবেদন করতে পারেন ) । এখন  প্রতিটা সাবজেক্ট দুইজন করে টিচার পড়াবে যা বুঝার জন্য আমরা দুইটা mask রাখতে পারি । mask1 এর কোন পয়েন্ট ১ থাকা মানে ১ জন টিচার আছেন যা এ সাবজেক্ট টা পড়ান । mask2 এর কোন পয়েন্ট ১ থাকা মানে ২ জন টিচার আছেন যা ঐ সাবজেক্ট পড়ান । আমরা যখন দেখব ( mask1 == ( 1 << total_sum ) - 1 && mask2 == ( 1 << total_sub ) - 1 ) ) এই কন্ডিশন টা ট্রু হচ্ছে মানে আমরা সব সাবজেক্ট এ কমপক্ষে দুইজন টিচার আছে তা পেয়েগেছি । ইনপুট এর বিশাল প্রবলেম আছে  এই প্রবলেম এ । এর বাদে আর কোন বিশেষ দিক নেই । straight forward bitmask dp এর প্রবলেম ।

Anagram Division 

এই প্রবলেম এ আমাদের বলা হইছে আমাদের একটা string ( s )  আর একটা নাম্বার ( d ) দেওয়া হবে । আমাদের বলতে হবে স্ট্রিংটা দ্বারা কয়টা নাম্বার এরকম করা যায় যা আমাদের এই নাম্বার d দ্বারা ভাগ যাবে ।

এই প্রবলেমটা ততক্ষণ পর্যন্ত কঠিন লাগতে পারে যতক্ষণ পর্যন্ত আমরা bitmask dp এর কথা ভাবি না । এইখানে বলা আছে স্ট্রিং এর লেন্থ হবে হাইস্ট ১০ ( যা খুব ভাল bitmask এর জন্য ) এবং d এর মান হাইস্ট হবে  < ১০০১ যাও অনেক ভাল । আমরা চাইলেই dp[ ( 1 << 10 ) ][ 1005 ] খুব সহজেই declear করতে পারি । এইখানে একটা উল্লেখ্য ব্যাপার আছে । যেহেতু permutation জড়িত , একই position main initial string এর different position same digit বসিয়েও আমরা একই নাম্বার তৈরি করতে পারি যা হবে ডুপলিকেট । ধরি আমাদের দেওয়া হল ০০০ স্ট্রিং । এইখানে bitmasking এ আমরা শুধু মাত্র position check করি । first index এ তার initial index এর 1  , 2 , 3 rd সব পজিশনের ভ্যালু বসেই কল হয় । কিন্তু আমাদের এই প্রবলেম এর জন্য আমাদের এই চেকটাও রাখতে হবে , আমরা যদি first index এ initial index এর 1 st position এর 0 বসাই তাহলে বসতে পারে initial string থেকে 2 , 3rd position এর ০ আমরা ১ নাম্বার পজিশনে বাসাব না । কারণ বসালে একই জিনিস দুই/আরও  বেশিও হতে পারে বসবে যা ডুপলিকেট অনেক কিছু তৈরি করবে । এর জন্য আমরা লোকাল ফ্লাগ array ( size 10 is good ) ব্যাবহার করব ।

Probability & Expected value ( part - 1 )

probability and expected value এর উপর top coder এবং codechef এ ভাল কিছু লিখা হইছে । যে কোন কিছু ভাল করে শিখার একটা ভাল উপায় হইল প্রথমে থিউরী শিখে এইগুলো কোন প্রবলেম এ এপ্লাই করা । আমার ইচ্ছা প্রবলেম সল্ভিং এ আমরা কিভাবে এই থিউরীগুলাকে কাজে লাগাইতে পারি তা নিয়ে লিখা । আমি নিজেও খুব একটা ভাল না এই টপিকটাতে । সাম্প্রতিক সময়ে যেহেতু আমি ২০১৫ এর ঢাকা রিজিওনালের জন্য প্রিপারেশন নিচ্ছি আমি আমার চোখে পড়া ভাল বা মজার প্রবলেম গুলার সল্যুশন ট্রিকগুলা  সিরিজ আকারে লিখে রাখার চেস্টা করছি যেন আগামীতে যে কেউ এইখান থেকে তার বা তার টিমের প্রিপারেশনের জন্য হ্যাল্প নিতে পারে ।

কিছু টিউটরিয়াল এর লিঙ্ক ( আমি এইটা আপডেট করতে থাকব , কোন কারণে এখন টপ কোডারের সাইট এক্সেস করা যাচ্ছে না তাই এইটা এইখানে এখন দিতে পারলাম না )

                  ১। codechef

What is the Probability ?

এই প্রবলেম এ বলা হইছে n জন ব্যাক্তি dice game টা খেলছে । dice এর ৬টা তলের যেকোন একটা তল হইল আমাদের উইনিং ইভেন্ট । মানে হইল ঐ তলটা যে খেলোয়াড় মারার টাইমে উঠে যাবে ও জিতে যাবে । এখানে আমাদের তিনটা ইনফরমেশন দেওয়া হবে । এক কয়জন খেলোয়াড় খেলছে , দুই যে তলটা উঠলে প্রতিযোগী জিতে যাবে ঐ তলটা উঠার সম্ভাব্যতা কত এবং শেষ হচ্ছে আমাদের যে প্রতিযোগীর জন্য probability বের করতে হবে তার সংখ্যা কত । এইখানে সিরিয়াল ওয়াইস মুভ দেওয়া হয় । মানে হইল প্রথমে ১ নাম্বার প্লেয়ার , তারপর ২ নাম্বার এইভাবে n নাম্বার তারপর আবার ১ নাম্বার প্লেয়ার ।  এইখানে সম্ভাব্যতা দশমিকের ৪ ঘর পর্যন্ত বের করতে বলা হইছে ।

আমরা যদি দেখি আমাদের k নাম্বার প্লেয়ারের জন্য তার winning probability বের করতে বলছে তাহলে আমরা এইটা পাই যে যেহেতু ও জিতবে তাহলে ও জিতবে হল k , n + k , n + n + k , n + n + n + k ............ নাম্বার মুভে । যদি ও k নাম্বার মুভে জিতে তাহলে আগের k - 1 মুভ হচ্ছে হারার মুভ , যেখানে সবাই ( 1 - p ) সম্ভাব্যতায় আমাদের winning event করে নি । যদি সে n + k নাম্বার মুভে জিতে তাহলে আগের n + k - 1 গুলা মুভ হচ্ছে হারার মুভ বা আমাদের জিতার ইভেন্ট না উঠার মুভ । যেহেতু সব গুলা dependent event তাই সবাই গুণ আকারে থাকবে । এখন আমারা একটা threshold value set করে নিবে এইখানে যেমন আমি ধরে নিয়েছি ( eps = 1e-9 ) . যখনই আমাদের winning event এর probability এই threshold value এর থেকে কমে যাবে আমরা loop  ব্রেক করে দিব ।


Probability|Given

এই প্রবলেম এ বলা হইছে n জন বন্ধু market এ গেছে এদের মধ্যে থেকে r জন বন্ধু কিছু না কিছু কিনছে । যদি সবার কিনার  সম্ভাব্যতা দেওয়া থাকে ( যদি ও মার্কেট এ যায় তাহলে কিনবে কি কিনবে না এর  সম্ভাব্যতা ) তাহলে যে r জন কিনছে এর মধ্যে প্রত্যেকের কিনার সম্ভাবতা কত ? এইটাই আমাদের এইখানে বলতে বলা হইছে ।


এইখানে আসলে আমাদের বলতে হবে ,

P ( A ( এই ব্যাক্তি কিনবে ) | R ( অবশ্যই R জন কিনবে ) ) = P ( A কিনছে এমন ঘটানায় টোটাল সম্ভাবনা ) / P ( R জন কিনছে এমন ঘটনার টোটাল সম্ভাবনা )

এই প্রবলেমটা আমরা backtrack করে সহজেই টোটাল সম্ভাবনা এবং এমন সবার আলাদা আলাদা কন্ট্রিবিউশনের টোটাল কত ছিল তা পেয়ে যেতে পারি , এমন কি এই কাজটা আমরা next_permutation দিতে করতে পারি , এর জন্য আগে থেকে n size এর কোন array এর  n - r কে মার্ক করব ০ আর বাকি r index কে মার্ক করব ১ । তারপর sort করে next_permutation করব । যে index এ ১ আছে মানে এই কেইজ এ ঐ ইনডেক্স এর জন কিনছিল তা বুঝায় । এইভাবে টোটাল এবং আলাদা আলাদা সবার টোটাল বের করে সবার  সম্ভাব্যতা উপরের সুত্র দিয়ে বের করতে পারি ।





Vampires :

এই প্রবলেম এ বলা হইছে দুইজন পিশাচ ( Vampirer এর বাংলা টার্ম :p ) যুদ্ধ লাগছে , প্রাথমিক ভাবে দুইজন এর লাইফ হচ্ছে যথাক্রমে ev1 , ev2 । এইখানে আরো দুইটা ইনফমেশন দেওয়া আছে । dice head , D .  এইখানে যে কোন ফাইটে প্রথম পিশাচের জিতবে যদি  একটা dice এর ৬টা তলের মধ্যে যেকোন তল উঠল এবং তা যদি given dice_head এর সমান বা ছোট হয় । যদি কোন পিশাচ কোন গেম জিতে তাহলে অপর পিশাচের লাইফ থেকে D amount life কমিয়ে ফেলবে । আমাদের বলতে হবে এই যুদ্ধে প্রথম পিশাচ জিতার সম্ভাব্যতা কত ?

এই প্রবলেমটা একটা ক্লাসিক সম্ভাব্যতা  প্রবলেম এর ক্লোন   "gambler's ruin problem" .  ঐ প্রবলেম এ দুইজন gambler যাদের initially n1 আর n2 টাকা আছে তারা বেট করে । যেখানে প্রতিটা গেম এর জন্য একটা  ফিক্সড সম্ভাব্যতা থাকে জিতার । যতক্ষণ না দুইজন এর একজন জিতছে তখন খেলা চলতেই থাকবে । এই প্রবলেম টার একটা closed form solution আছে ( formula solution ) না হলে হয়তো infinity পর্যন্ত খেলা চলতেই থাকত । প্রাথমিক অবস্থা দেখে আমরা বলে দিতে পারি কোন প্লেয়ার এর জিতার সম্ভাব্যতা কত ।

যদি l হয় প্লেয়ার ১ এর জিতার সম্ভাব্যতা এবং q = 1 - l হয় প্লেয়ার ২ এর জিতার সম্ভাব্যতা তাহলে প্লেয়ার ১ এর জিতার সম্ভাব্যতা হবে ( 1 - pow( q/p , n1 ) )/ ( 1 - pow( q/p , n1 + n2 ) ) । এবং প্লেয়ার ২ এর হবে ১ বিয়োগ এইটা ।

আমাদের এই প্রবলেমটাকে আমরা Gambler ruin problem এ convert করতে পারি । এইখানে n1 , n2 হবে
n1 = ceil( ev1 / d ) , n2 = ceil ( n2 / d ) .  p = ( given_head ) / 6.0 and q = ( 1 - p ) .

তবে যদি  p == q হয় তাহলে একটা special case হয় যেখানে প্রথম জনের জিতার সম্ভাব্যতা হবে  n1 / ( n1 + n2 ) .

এই পর্বে এইটুকুই । কোন ভুল থাকলে বা কনফিউশন থাকলে কমেন্ট করে জানাতে পারেন ।

DP trick - Knuth's optimization

কিছু classical dp problem আছে "cutting rod" এর মত যেখানে আমাদের একটা গ্রুপ এর মধ্যে ম্যাস্কিমাম বা মিনিমাম ভ্যালু বের করতে হয় । প্রবলেমগুলাতে এই ধরনের recursion relation থাকে
if l is the left part and r is the right part of the interval then

dp[l][r] = min( dp[l][r] , d[l][m] + dp[m][r] ) + Inp[l][r] ;

এই প্রবলেমগুলাকে আমরা l থেকে r এ যে কোন mid point ধরে o( n ^ 3 ) এ যেখানে n হচ্ছে আমরা রডটাকে কতটা ভাগে ভাগ করতে পারি প্রবলেমটা সল্ভ করতে পারি , যা লিমিট একটু বড় হলে TLE দিবে । এই ধরনের প্রবলেম সল্যুশনে আমরা knuth's optimization technique use করতে পারি এতে code এর run time O ( n ^ 3 ) থেকে কমে এসে O ( n ^ 2 ) হয়ে যায় ।

তবে তা ব্যাবহার করা যাবে যদি নিচের দুইটা শর্ত বজায় থাকে ।

1.  quadrangle inequality
   Inp[ a ] [ c ] + Inp [ b ] [ d ] <= Inp[a][d] + Inp[ b ][ c ] where a <= b <= c <= d
2. monotonicity  

         Inp[b][c] <= Inp[a][d] where a <= b <= c <= d 

যদি সহজে বলি আমাদের পার্টিশন পয়েন্ট গুলা শর্ট হিসাবে থাকবে ( ছোট থেকে বড় )

আমরা একটা প্রবলেম নিয়ে এইটা কিভাবে এই ট্যাকনিক এ সল্ভ করা যাবে এইটা দেখি ।
Breaking Strings :

এই প্রবলেম এ একটা string কে কিভাবে break করলে সব থেকে মিনিমাম খরচে করা যাবে তা বলতে হবে । এইখানে string এর breaking point গুলা কি কি তা দেওয়া হয়েছে । এইখানে যে কোন পয়েন্ট এ ব্রেক করার সময় টোটাল কত lenght এর পার্ট থেকে এইটা ভাঙ্গছে এইটাই হচ্ছে এর cost ।

এর সমাধানে কোন পার্ট l - r এর জন্য এর mid[l][r] হচ্ছে এই পয়েন্ট যেখানে l - r  ভাঙলে সব থেকে কম হবে । যেহেতু middle point monotonously  end point এর উপর নির্ভর করে তাই
 mid[ l ][ r - 1] <= mid [ l ][ r ] <= mid [ l + 1 ][ r ] এইটা বজায় থাকবে । এইখানে আমরা l to r এর জন্য mid point update করতে থাকব mid[l][r-1] & min[l+1][r] এর পার্ট থেকে কারণ অবশ্যই best mid point ( partioning point ) হবে mid[l][r-1] <= our_target_partitioning_point <= mid[l+1][r ] for l - r interval .

প্রতিটা starting l এর জন্য আমরা চেক করে দেখছি যার জন্য m বার iteration লাগছে । run time  O( m ^ 2 ) .
প্রবলেম : 1
Reference Link : here

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 করতে পারি ।

কোড

Expedition :

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

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

এই কোডের রান টাইম হবে 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 করে যেতে থাকলেই আমরা রেজাল্টটা পাই । এই অবজারবেশন থেকে আমরা প্রবলেমটা সল্ভ করতে পারি ।

এই প্রবলেম 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 দেখি কিভাবে করা যেতে পারে ।
এইখানে 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 ] ) ;
   এইটা কেন কাজ করে এই জিনিসটা সম্পূর্ণ কোডটা দেখা হলে বুঝা যাবে ।

কোড :

যেহেতু 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 এর সবগুলা লাইটা জ্বালানো আছে ( যদি না থাকে তাহলে আর কোন ভাবেই ঐ লাইটাকে আর জ্বালানো সম্ভব হবে না  কিন্তু প্রথম রো থেকে এই জন্যই যাব কারণ আমি দ্বিতীয় রো থেকেও প্রথম রো এর সব লাইট নিভাতে পারি । ) ।
  
  কোড :

এই প্রবলেমটা আমরা 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 করব ।  

কোড :

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 দিয়েই হয়ে যাবে । 
কোড

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

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 সব থেকে বেশি হবে । 

কোড ::

রান  টাইম হচ্ছে 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 এর বড় বিলিং করা যায় ( কথাগুলা না বুঝলে ভয় পাওয়ার কিছু নাই কোড দেখলেই বুঝা যাবে ) । 

কোড

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

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 রাখি ( মানে সব পজিশন এখন ভিজিবল ) । তারপর আসতে আসতে প্রতিটা অপারেশন এর সময় শুধু চেক করব যে রেঞ্জ এর মধ্যে এখন পোস্টারটা লাগাব তার কোন একটা পজিশন কি কোন না কোন ভাবে দেখা যায় কিনা , দেখে গেলেই লাস্ট এও এইটা দেখা যাবে কারণ এর পরের পোস্টার গুলা আমরা আগেই লাগাইয়া আসসি ।

কোড 

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

Minimum Expression

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

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

এখন যদি আমরা একই কাজটা string rotation এর জন্য করতে চাই তাহলে কিভাবে করব -
এইখানে আমরা দেখি আমাদের রান টাইম হচ্ছে 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 এর  ।

কোড

এই কোডের রান টাইম হবে 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 )

কোড 

রান টাইম হবে 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] ;

কোড :

এই কোডের রান টাইম হবে 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 তে কি থাকবে তাও পেয়ে যাব ।

এই কোডের রান টাইম কি হবে ? এইটা পাঠকদের উদ্দেশ্যই রেখে দিলাম :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 দেখি -
এইখানে আমরা 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 দিয়ে দুইটা পয়েন্টকে নিয়ন্ত্রণ করছি ।

এইখানে আমরা 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 করতে থাকব ।

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

এখন যদি আমরা এই কোডটার রান টাইম দেখি । কোডটা 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 .

Backtrack & N Queen

[ এইখানের সব চরিত্রই কাল্পনিক , বাস্তবতার সাথে কাছে , উপরে , নিচে , দূরে কোন খানেই কোন মিল নাই । গল্পে তাই বাস্তবতার সাথে কোন মিল ,  কোন লজিক খুঁজে বেড়ানো  অমূলক । ]    

হাতে একটা DLSR আছে আর কোন মেয়ে পটবে না এমনটা হবে না । রেদোয়ান এরও তাই সখিনাকে পটাইতে টাইম লাগল না । স্বাধীনতার পাওয়া থেকে স্বাধীনতা রক্ষা করা কঠিন । এত এত কম্পিটিশন এর যুগে তাই গার্লফ্রেন্ড রক্ষা করা কঠিন । কত কত থ্রেড আনাচে কানাচে । শিশির ভাবুক ছেলে , মনে গভীরের আবেগ বুঝতে তাই দেড়ি হয়ে গেছিল । ভার্সিটির লিফটে মনের আদান প্রদান হইলেও কিঞ্চিৎ সংকোচের কারণে রেদোয়ান এর কাছে একটু পিছিয়ে ছিল । সখিনা আর রেদোয়ান ক্লাসমেট , শিশির তাদের সিনিয়র । নানা ছালচাতুরে রেদোয়ান শিশির কে ধোঁকা দিয়ে সখিনাকে আগলাইয়া রাখলেও বহুমুখী প্রতিভার অধিকারী শিশির যদি কোনভাবেই সখিনার কাছে মনের ভাব পৌঁছাইয়া দিতে পারে , অতি ভাল ফ্রেন্ড থেকে শুধু  ফ্রেন্ড  সম্পর্কে  সখিনা রেদোয়ানকে নামাইয়া নিয়া আসলেও আসতে পারে । তাই কোন ভাবেই রেদোয়ান শিশির এর  কোন প্রকার নোট , হৃদয় দিয়ে আঁকা ছবি সখিনার কাছে পৌঁছাতে দিতে পারে না । এমনেই সহপাঠী বান্ধবী মাত্রই সিনিয়র ভাইয়াদের প্রতি কিঞ্চিৎ দুর্বল থাকে তারপর যদি সিনিয়র বহুমুখী প্রতিভার অধিকারী হয় । বলা রাখা ভাল আমরা এমন একটা যুগের কথা বলতেছি এইযুগে  লিফট , হাতে DLSR থাকলেও মোবাইল ফোন নাই , এমনকি ফেসবুক ও নাই । এই যুগে ছেলে যতই আধুনিক হোক আশে-পাশে  জুনিওর ছেলে থাকলে সৎ সাহস নিয়ে কোন মেয়ের সাথে কথা বলতে সাহস করে না ।  

যেভাবেই হোক রেদোয়ানকে সখিনাকে রক্ষা করতে হবে যেকোন ধরণের আলাপ-চারিতা   শিশির এর কুনজর থেকে । রেদোয়ান ঠিক একটা N*N rectangle Grid কল্পনা করল সখিনার আসে-পাশে একদম দাবা ঘরের মত । এই ঘর গুলা যদি রেদোয়ান গার্ড দিয়ে রাখতে পারে তাহলে শিশির কখনই সখিনার ধারের কাছেও আসবে না ।  রেদোয়ান এর কিছু স্পেশাল ফ্রেন্ড আছে । যারা সব সময় ভাবেই রেদোয়ান এর লাইফে আসে শুধু দুইজন মানুষ , এক সখিনা আর সে । আর কেউ নাই , আর কেউ থাকবে তা ও কল্পনাও করতে পারে না । তারা আবার দাবা খেলার মন্ত্রীর মত গার্ড দিতে পারে । মানে কেউ কোন ঘরে থাকলে মন্ত্রী যেমন এট্যাক করে তেমন করে গার্ড দিয়ে রাখতে পারে সখিনাকে যেন শিশির কোন ভাবেই সখিনার কাছে আসতে না পারে । এমন কিছুটা 

 

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

সুপার বুড়া ভাইয়া মাহির খুবই গুরু গম্ভীর মানুষ । প্রোগ্রামিং ছাড়া কোন কথা বলেন না । সব কিছু শুনে অনেকক্ষণ চিন্তা ভাবনা করে বলল “ শুন রেদোয়ান তুমি যে প্রবলেম এ আছ , এইডা খুবই পুরাতন ক্যাসিক্যাল N Queen Problem , যা ১৮৫০ সালেই “Franz  Nauck” নামের এক ভদ্রলোক সমাধান দিয়ে গেছেন । এই সমাধান তোমাকে বুঝতে হবে , শুধু বুঝতে হবে না অন্তর দিয়া ফিল ও করতে হবে তাইলেই তুমি সখিনাকে শিশির এর কুনজর থেকে রক্ষা করতে পারবা ”  

আমরা যে যুগে আছি এইডা হইল ভাল যুগ , এইখানে মানুষ মনের মধ্যে ভয়-ভিতি নিয়ে প্রেম-পিরিতি করে কখন কে এসে প্রেমিকা  ভাগাইয়া নিয়া যায় । তাই যতই কঠিন হোক রেদোয়ানকে বুঝতে হবে N-Queen  প্রবলেম এর সমাধান , নিজের জন্য , নিজের অনাগত নাতি-নাতনীর জন্য যে তারা রেদোয়ানকে দাদু , সখিনাকে দিদা ডাকতে পারে ।

N Queen Problem কি ?

N Queen problem হল একটা N*N দাবা বোর্ডে কত ভাবে N টা queen বসানো যায় যাতে তারা একজন অপরজনকে কোন ভাবে এট্যাক না করে । N Queen problem এর solution এর মাধ্যমে আমরা খুব সহজেই যত কম্বিনেশন আছে তা পেয়ে যেতে পারি । 

Solution :  

Queen যেভাবে এট্যাক করে তাতে প্রতিটা Row এবং column এ মাত্র একজন করে queen  বসতে পারে এবং সাথে সাথে আমাদের চেক করে রাখতে হবে diagonal ভাবে কোন Queen আবার যে ঘরে এই Queen টা কে বসাতে চাচ্ছি তাতে  এট্যাক করে   বসে আছে কিনা । কাজটা আমরা খুব সহজেই backtrack দিয়ে করে ফেলতে পারি । আমরা জানি সব Row তে শুধু মাত্রই একটা করে Queen থাকবে এবং সিরিয়ালই যদি আমরা Queen বসাতে থাকি তাহলে আমাদের শুধু বের করতে হবে কোন Queen কোন কলামে আছে যাতে diagonally ও অন্য কোন Queen যেখানে আমরা এই Queenটা বাসাতে চাচ্ছি তাকে এট্যাক করছে না মানে এইখানে আমরা Queen বসাতে পারি ।

একটা জিনিস খেয়াল করি , যখন আমরা কোন Queen বসাই তখন শুধু এইটা চেক করলেই আগের বসানো কোন Queen এর সাথে এখন যে প্লেস এ Queenটা আমরা বসাতে চাচ্ছি তা conflict করছে কিনা মানে এই পজিশন previous বসানো কোন Queen already attack করে রেখেছে কিনা । এইখানে column এর চেক এর পার্টটা অনেক ইজি কিন্তু diagonally part টা একটু tricky . একটা জিনিস খেয়াল করলে দেখা যাবে যে সব কলাম বাম থেকে নিচের ডান দিকে যায় তাদের row আর column এর বিয়োগ ফল একই হয় এবং যে সব কলাম ডান থেকে নিচের বাম দিকে যায় তাদের row এবং column এর যোগফল একই হয় , মানে একটা Queen এর জন্য কলাম সাপেক্ষে দুইটা আলাদা ভাল্যু আছে যেইটা তারা স্টোর করে রাখে যা তাদের অন্য Queen থেকে different করে ।  কোডটা দেখি

এইখানে আমরা global variable column[] , diagonal1[] , diagonal2[] এর মাধ্যমে কোনটা কোনটা নেওয়া হইছে একটা সল্যুশন এর জন্য তা দেখানো হয়েছে । যখন কোন একটা কল হয় তার আগে আমরা এদের ১ করে দিচ্ছি মানে তাদের নেওয়া শেষ , যতক্ষণ পর্যন্ত না recursion কলটা ফেরত আসতেছে ততক্ষণ তারা ১ থাকবে মানে বুক থাকবে । এইভাবে all solution পাওয়া যায় ।

সারাংশ : 

অতপর আমরা এইটা বুঝতে পারি যে যদি আমাদের গার্লফ্রেন্ড রক্ষা করে রাখতে হয় অবশ্যই আমাদের backtrack এর এপ্লিকেশন N Queen সম্পর্কে ক্লিয়ার ধারণা রাখতে হবে নাহলে যুগ যুগান্তর ধরে শিশির এর মত সুযোগ সন্ধানীরা তাদের ভাগাইয়া নিয়া যাবে । UVA 750 প্রবলেমটা এখন তাই করা উচিত সবার ।