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 আছে তা থেকে বিয়োগ করে দিব ।

	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;
	}

view raw digitDp1.cpp hosted with ❤ by GitHub

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 .

	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;
	}

view raw digitDp2.cpp hosted with ❤ by GitHub

প্র্যাকটিস প্রবলেম : 1 , 2