Dp part - 4

DP নিয়ে আমার আগের লিখাগুলা পাওয়া যাবে এই লিঙ্ক এ । এই পোস্টে কিছু কমন ডিপি সল্যুশন নিয়ে আলোচনা করছি ।


nth premutation :

এই প্রবলেম এ বলা হয়েছে আমাদের একটা string দেওয়া হবে আমাদের এই string এর nth permutation ভ্যালু কত হবে তা বলতে হবে । যদি তা সম্ভব না হয় আমাদের "impossible" প্রিন্ট করতে হবে । এইখানে n এর ভ্যালু হতে পারে ২^৩১ । এইখানে একটা জিনিস দেখি আমরা string এর সাইজ হতে পারে হাইস্ট ২০ লেটারে এবং সব যদি ভিন্ন ভিন্ন লেটার হয় তাহলে পারমুটাশেন সম্ভব হত n! বা ২০! । যা অনেক বড় মান , আমরা যদি built in function,  next_premutation ব্যাবহার করে যাই তাহলে এইটা সম্ভব হবে না । এখন প্রবলেমটাকে ছোট করার জন্য আমরা corner-case চিন্তা করতে পারি । প্রথম এ আছি impossible case এ , কখন কখন impossible হবে । আমরা সহজেই লেটার ফ্রিকিউয়েন্সি কাউন্ট করে দেখতে পারি আমাদের দেওয়া string থেকে কতটা permutation possible , যদি এর মান আমাদের nth value এর মান এর থেকে কম হয় আমরা সহজেই  বলে দিতে পারি যে nth-value string পসিবল না পাওয়া । এইটা আমরা permutation এর ব্যাসিক ফরমুলা থেকে পেতে পারি ।

         ( size_of_the_string ) ! / ( frequency_of_every_letter_in_that_string ) ! ......... ( 1 )

এখন মেইন পার্ট । আমারা এখন nth-value পসিবল string এর কিভাবে আমরা এই  ভ্যালুটা পাব দেখব । আমরা কোন পজিশনে কোন লেটার বসিয়ে , এই লেটার এই পজিশনে বসবে এবং  এর জন্য কতটা permutation হতে পারে তা আমরা সহজেই ( ১ ) ইকুয়েশন থেকে পেয়ে যেতে পারি । যদি এর মান আমাদের nth_value এর চেয়ে কম হয় তাহলে আমরা বুঝব আসলে এই লেটার টা এইপজিশনে বসবে না আমাদের ফাইনাল string এর যদি বসত তা হলে এর জন্য মান nth_value এর সমান বা বেশি হত । কথাগুলা অসংলগ্ন লাগতে পারে একবারে পড়লে । একটা example এর মাধ্যমে দেখলে সহজ হয়ে যাবে  ।

Say string : abc , আমাদের বলতে হবে  এর ৬ষ্ঠ পারমুটেশনের স্ট্রিংটা কি ?

যদি 'a' final string এর ফাস্ট লেটার হত তাহলে আমরা 'a' কে প্রথম পজিশনে বসিয়ে b এবং c থেকে আরো 2টা পারমুটেশন পেতে পারতাম । ( abc , acb ) , কিন্তু তা ৬ এর চেয়ে কম অর্থাৎ আমরা বলতে পারি 'a' প্রথম পজিশনে বসিয়ে আমরা আমাদের ফাইনাল string পাব না । এখন 'b' কে যদি প্রথম পজিশনে বসাই তাহলে আমরা 'b' কে বসিয়ে আরো দুইটা পারমুটেশন পাব a and c এর জন্য । ( bac , bca ) , যেহেতু 'a' এর পর 'b' আসে তাই 'a' জন্য ও মানগুলা এইখানে যুক্ত হবে । টোটাল ২ + ২ = ৪ < ৬ অর্থাৎ 'b' বসিয়েও আমরা আমাদের ফাইনাল string টা পাব না । এখন 'c' এর জন্য দেখা যাবে একই ভাবে ৪ + ২ >= ৬ তাই ফাইনাল string এর প্রথম লেটার আমরা নিশ্চিত ভাবে বলতে পারি 'c' বসবে ,  এবং 'c' বসানোর মাধ্যমে আমরা 'a' এবং 'b' বসানোর জন্য মান গুলা আমাদের ফাইনাল স্ট্রিং থেকে বাদ দিয়ে পারি । এইভাবে প্রতিটা পজিশনের জন্য আমাদের ক্যালকুলেশন করে বুঝতে হবে কোন লেটারটা বসবে ।

কোড

Be Efficient :

এই প্রবলেম এ বলা হয়েছে আমাদের n টা নাম্বার এবং আরো একটা নাম্বার m দেওয়া হবে । আমাদের বলতে হবে এই nটা নাম্বার এর মধ্যে কতগুলা নাম্বার consecutive sequence  m দ্বারা বিভাজ্য । যেমন যদি n = 3 এবং m = 3 হয় এবং n sequence numbers :  3 , 6 , 9 তাহলে মোট ..
{ 3 } , { 3 , 6 } , { 3 , 6 , 9 } , { 6 } , { 6 , 9 } , { 9 } এই  ছয়টি নাম্বার m = 3 দ্বারা বিভাজ্য ।

এইখানে একটা important point হচ্ছে m <= 10^5 . এইটা এইজন্য important আমরা তাহলে নিশ্চিতভাবে বলতে পারব যে consecutive number এর sequence এর mod value কখনই 10^5 থেকে বড় হবে না , যা আমরা কোন array তেও store করে রাখতে পারি । এইখানে কিছু key observation আছে এই consecutive mod value নিয়ে । যদি প্রথম নাম্বার এর জন্য mod value আসল ১ , আবার দেখা গেল প্রথম ৩টা নাম্বার নিয়ে mod value হচ্ছে ১ এবং আমারা যদি  প্রথম ৫টা নাম্বার নিয়েও একই ১ পাই  তাহলে আমরা দেখব যে প্রথম ২ - ৩ নাম্বার অবশ্যই m দ্বারা এবং একই ভাবে ২-৫ এবং ৪-৫ consecutive number গুলা m দ্বারা বিভাজ্য হবে । এইটা একটা example এর মাধ্যমে দেখলে ক্লিয়ার হবে ।

say n = 5 , m = 3 , n sequence numbers are : 1 , 2 , 1 , 1 , 2 । তাহলে { 2 , 1 } , { 2 , 1 , 1 , 2 } , { 1 , 2 } m = 3 দ্বারা ভাগ হবে । consecutive result এর জন্য mod value এর সাথে সাথে আমরা এড ভ্যালু বাড়িয়া আমাদের answer এর সাথে যোগ করব , কোন নাম্বার নিজেও একা m দ্বারা বিভাজ্য হতে পারে বলে mod = 0 , এর নাম প্রথমে ১ করে রাখব ।

কোড ঃ