Wednesday, September 16, 2015

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

10 comments:

  1. This comment has been removed by the author.

    ReplyDelete
    Replies
    1. asole eita joto digit er number hobe toto hobe . ei problem er junno 70 neoar kono dorkar nai . limit hocche unsigned int . unsigned int er highest number joto digit er hote pare toto limit dhore korlei hobe , jemon unsigned int er number highest 9 digit er hoy amra 10 dhore korleo AC pabo .

      Delete
  2. 1st problem e....
    value = # of 0's taken so far
    why value is a state?

    ReplyDelete
  3. Vai ki blog likhsen. Bakker kuno aga gura thik nai. Likhben e jokhon 1tu valo kore lekhen. Jate kore kisuta pore bujhi.

    ReplyDelete
    Replies
    1. Thank you so much for your comment. I will try.

      Delete
    2. Rizwan vai apni evabe comment korte paren na..Sakil vai der moton kichu boro vaider blog porei amra algorithm sikhce..Onader jnno amader programming ta onekta easy hoice..Amra actually onader kache rini..Kichu paren ar na paren at least onader koster respect tuku dekhaben asa kori..Ar etto kichur majhe choto kichu problem hotei pare..Vul kichu bole thakle sorry..

      Delete
  4. please you should define 'tt' it is disturbing.you can also intialize the dp array with '-1'.

    ReplyDelete
  5. 1st problem a dp r res theke kibhabe abar value eshay (v==tt) howar karone ret return hocche.Eta bhujtesina

    ReplyDelete
  6. Dp function er first 5 5ta line er logic bhujtesina other than that purata bhucchi

    ReplyDelete