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 আছে তা থেকে বিয়োগ করে দিব ।
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const int NX = 70 ; | |
| Long dp[2][2][NX][NX]; | |
| int vis[2][2][NX][NX]; | |
| int lim , tt ; | |
| vector < int > inp ; | |
| Long DP( int pos , int isSmall ,int isStart, int value) | |
| { | |
| if( pos == lim ) return value ; | |
| Long &ret = dp[isSmall][isStart][pos][value]; | |
| int &v = vis[isSmall][isStart][pos][value]; | |
| if( v == tt ) return ret ; | |
| v = tt ; | |
| int ses = isSmall ? 9 : inp[pos]; | |
| int i ; | |
| ret = 0 ; | |
| if( !isStart ) // আগেই নাম্বার বসানো শুরু করে দিছি | |
| for ( i = 0 ; i <= ses ; i++ ) | |
| { | |
| ret += DP( pos + 1 , isSmall | i < inp[pos] ,0, (i == 0) + value ); | |
| } | |
| else | |
| { | |
| for ( i = 1 ; i <= ses ; i++ ) | |
| { | |
| ret += DP( pos + 1 , isSmall | i < inp[pos] ,0, (i == 0) + value ); | |
| } | |
| ret += DP( pos + 1 , 1 ,1, 0 ); | |
| } | |
| return ret ; | |
| } | |
| Long Cal( Long x ) | |
| { | |
| if( x < 0 ) return 0 ; | |
| if( x <= 9 ) return 1 ; | |
| inp.clear(); | |
| while( x ) | |
| { | |
| inp.pb(x%10); | |
| x/=10; | |
| } | |
| reverse(inp.begin(),inp.end()); // সুবিধার জন্য রিভারস করে নিচ্ছি , এইটা করতেই হবে | |
| lim = inp.size(); | |
| tt++; | |
| return DP( 0 , 0 , 1 , 0 ) + 1; // শুধু ০ টা আলাদা এড করছি | |
| } | |
| int main() | |
| { | |
| // I will always use scanf and printf | |
| // May be i won't be a good programmer but i will be a good human being | |
| // cout << fixed << setprecision(10) ; | |
| int cs , t = II ; | |
| for ( cs = 1 ; cs <= t ; cs++ ) | |
| { | |
| Long n = LL , m = LL ; | |
| Long ans = Cal(m) - Cal(n-1); | |
| printf("Case %d: %lld\n",cs,ans); | |
| } | |
| return 0; | |
| } | |
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 .
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const int NX = 82 ; | |
| int dp[ 10 ][ NX ][ NX ][ 2 ] , cs , vis[ 10 ][ NX ][ NX ][ 2 ] , len , inp[ 12 ]; | |
| int k , tt , a , b ; | |
| int DP( int pos , int rem , int remdigit , int isSmall ) | |
| { | |
| if( pos == len ) return !( rem + remdigit); | |
| int &v = vis[pos][rem][remdigit][isSmall]; | |
| int &ret = dp[pos][rem][remdigit][isSmall]; | |
| if( v == tt ) return ret ; | |
| v = tt ; | |
| ret = 0 ; | |
| int mx = isSmall ? 9 : inp[pos]; | |
| rep( i , mx ) ret += DP( pos + 1 , ( rem*10 + i )%k , (remdigit + i)%k , 1 ); | |
| if(isSmall) ret += DP( pos + 1 , ( rem*10 + mx)%k , (remdigit + mx)%k , 1 ); | |
| else ret += DP( pos + 1 , ( rem*10 + mx)%k , (remdigit + mx)%k , 0 ); | |
| return ret ; | |
| } | |
| int solve( int num) | |
| { | |
| len = 0 ; | |
| while(num > 0 ) | |
| { | |
| inp[len++] = num%10; | |
| num/=10; | |
| } | |
| reverse( inp , inp + len ); | |
| tt++; | |
| return DP( 0 , 0 , 0 , 0 ); | |
| } | |
| int main() | |
| { | |
| // I will always use scanf and printf | |
| // May be i won't be a good programmer but i will be a good human being | |
| int cs , t = II ; | |
| for ( cs = 1 ; cs <= t ; cs++ ) | |
| { | |
| a = II , b = II , k = II ; | |
| if( a > b ) swap( a , b ); | |
| printf("Case %d: ", cs); | |
| if( k == 1 ) printf("%d\n",b-a+1); | |
| else if( k > 81 ) printf("0\n"); | |
| else | |
| { | |
| int ans = solve(b); | |
| ans -= solve(a-1); | |
| printf("%d\n",ans); | |
| } | |
| } | |
| return 0; | |
| } |
প্র্যাকটিস প্রবলেম : 1 , 2
