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 ) ব্যাবহার করব ।