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

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

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

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