SPOJ - NUMTSN - 369 Numbers Tutorial

Problem Description here

প্রব্লেমটিতে বলা হয়েছে, একটি রেঞ্জ এর মধ্যে এমন কয়টি সংখ্যা আছে যাদের মধ্যে ৩,৬ এবং ৯ ডিজিটগুলো সমান সংখ্যকবার আছে এবং কমপক্ষে একবার করে আছে। 

সল্যুশন আইডিয়াঃ

এই প্রব্লেমের কিছু অবজার্বেশন আছে। 

১) সবচেয়ে বড় সংখ্যাটি (১০^৫০) তে সর্বোচ্চ ৫১ টি ডিজিট থাকতে পারে। তার মানে, প্রব্লেমের শর্ত পূরণ করে এমন সংখ্যায় ৩,৬,৯ প্রতিটি ডিজিট সর্বোচ্চ ১৬বার থাকতে পারে। এর বেশি হলে সেই সংখ্যাটি আমাদের প্রয়োজন নেই।

এতোটুকু বুঝতে পারলে আর ডিজিট ডিপি মোটামুটি পারলে হয়তো মনে মনে কিছু স্টেট ধরে নিয়েছো। তাদের মধ্যে তিনটি স্টেট হলো, 

i) কয়টা ৩ পেলাম এখন পর্যন্ত।

ii) কয়টা ৬ পেলাম এখন পর্যন্ত।

iii) কয়টা ৯ পেলাম এখন পর্যন্ত।

এই তিনটা স্টেট এর জন্য কমপ্লেক্সিটি ১৭*১৭*১৭ = ৪৯১৩

এবার, প্রব্লেমটি ইমপ্লিমেন্ট করলে তোমার TLE খাওয়ার সম্ভাবনা প্রবল!!! আরো কিভাবে অপটিমাইজ করা যায় ভাবতে হবে।

..........

..........

ভাবা শেষেও না পেলে দেখো। আমি যদি দুইটা স্টেট নেই যাদের কাজ হচ্ছে, ৩ ও ৬ এর সংখ্যার পার্থক্য রাখা। ৩ ও ৯ এর সংখ্যার পার্থক্য রাখা। তাহলে স্টেট দুটির কমপ্লেক্সিটি হচ্ছে ৩৫*৩৫ = ১২২৫! 

এখন, অনেকেই আমার ভূল ধরবে যে কমপক্ষে ১ টা ৩ আছে কি না, কীভাবে বুঝবো?

হুম, আমি ভূল ছিলাম। এটা বুঝার জন্য ২ সাইজের আরো একটা স্টেট নিবো যার কাজ হচ্ছে আছে কি নাই মনে রাখা। 

তাহলেও কিন্তু কমপ্লেক্সিটি কমে! 

২*৩৫*৩৫ = ২৪৫০ < ৪৯১৩ -_-

২) এখন, অনেকেই বলবা ৩ ও ৬ এর সংখ্যার পার্থক্য কীভাবে রাখবো! যদি আমি ৩ পেলে স্টেট এর ভ্যালু বাড়াই আর ৬ পেলে কমাই তাহলে তো ভ্যালু নেগেটিভ হয়ে RTE হবে নিশ্চিত!

স্টেটের প্রাথমিক ভ্যালু ধরবো ১৭। তাহলে কী নেগেটিভ আশার সম্ভাবনা নাই? অবশ্যই আছে। তবে এই ক্ষেত্রে যখনই সে নেগেটিভ এর দিকে যেতে চাইবে অথবা ৩৪ থেকে বড় হতে চাইবে তুমি বুঝে যাবা তাকে আর তোমার প্রয়োজন নাই!!! অবাঞ্ছিত তাকে এখানেই থামাও। সামনে গেলে বিপদ।

তাহলে, এই প্রব্লেমের জন্য আমার প্রয়োজনীয় সকল স্টেট কী কী?

স্টেট-১ঃ বর্তমান পজিশন কী একটি সংখ্যা বানানোর শুরুর পজিশন? মানে অতীতে এখনো কোন ডিজিট আমি নেই নি এই বর্তমান অবস্থার জন্য।

স্টেট-২ঃ বর্তমান অবস্থায় আমি যে সংখ্যা বানাতে যাচ্ছি তা কি অলরেডি লিমিট এর থেকে ছোট?

স্টেট-৩ঃ বর্তমান অবস্থায় আমি যে সংখ্যা বানাচ্ছি তার মধ্যে কী এখন পর্যন্ত ৩ ডিজিট টি ব্যাবহার করেছি?

স্টেট-৪ঃ এখন পর্যন্ত ব্যাবহার করা ৩ ও ৬ এর সংখ্যার পার্থক্য কত? শুরুতে এই স্টেটের ভ্যালু ১৭ থাকবে। ৩ পেলে ১ কমাবো ভ্যালু আর ৬ পেলে ১ বাড়াবো।

স্টেট-৫ঃ এখন পর্যন্ত ব্যাবহার করা ৩ ও ৯ এর সংখ্যার পার্থক্য কত? এটিও পূর্ববর্তী স্টেটের মতোই কাজ করবে।

স্টেট-৬ঃ এখন কততম পজিশনে আছি আমি। 

তাহলে, মোট কমপ্লেক্সিটি কত দাড়ালো?

২*২*২*৩৫*৩৫*৫১

এবার উপরোক্ত ফাংশনের মাধ্যমে আমি ০ থেকে UB পর্যন্ত কয়টা সংখ্যা পাওয়া যায় বের করবো। এরপর ০ থেকে LB-1 পর্যন্ত কয়টা সংখ্যা পাওয়া যায় বের করবো।

প্রথম ভ্যালু থেকে ২য় ভ্যালু বিয়োগ করলেই আউটপুট পাওয়া যাবে।

ঝামেলার বিষয় হচ্ছে, সংখ্যাটা অনেক বড় বিধায় স্ট্রিং আকারে ইনপুট নেয়া লাগবে। আর সেক্ষেত্রে LB-1 বের করা কষ্টসাধ্য। তাহলে, উপায় কী?

ans = FuN(UB) - FuN(LB)

যদি, LB নিজেই একটা ভ্যালিড সংখ্যা হয় তাহলে জাস্ট ans+1 করে দিবো। কাজ শেষ!

এবার নিজে নিজে কোড করার চেষ্টা কর।

অনেক অনেকবার ব্যার্থ হলে নিচে গিয়ে কোড দেখতে পারো নিজ দায়িত্বে। কারণ, নিজে খুব বেশি চেষ্টা না করে কোড দেখে প্রব্লেম সলভের দায় আমি নিবো না -_-

	ll dp[2][2][2][35][35][51];
	vi num;
	char s[5][55];
	ll FuN(bool isStart,bool isSmall,bool veThree,int dif1,int dif2,int pos)
	{
	if(pos >= (int)num.size()){
	if(veThree && dif1==17 && dif2==17)
	return 1LL;
	else
	return 0LL;
	}
	if(dp[isStart][isSmall][veThree][dif1][dif2][pos] != -1)
	return dp[isStart][isSmall][veThree][dif1][dif2][pos];
	ll ret = 0 , can_be_taken = 0;
	can_be_taken = (isSmall == 1)? 9:num[pos];
	if(isStart){
	for(int i=1 ; i<=can_be_taken ; i++){
	if((i==3 && dif1<34 && dif2<34) || (i==6 && dif1>0) || (i==9 && dif2>0) || (i!=3 && i!=6 && i!=9))
	ret = (ret + (FuN(0 , (isSmall|(i<can_be_taken)) , (veThree|(i==3)) , (dif1+(i==3)-(i==6)) , (dif2+(i==3)-(i==9)) , pos+1)%MOD) )%MOD;
	}
	ret = (ret + (FuN(isStart , 1 , veThree , dif1 , dif2 , pos+1)%MOD))%MOD;
	}
	else{
	for(int i=0 ; i<=can_be_taken ; i++){
	if((i==3 && dif1<34 && dif2<34) || (i==6 && dif1>0) || (i==9 && dif2>0) || (i!=3 && i!=6 && i!=9))
	ret = (ret + (FuN(0 , (isSmall|(i<can_be_taken)) , (veThree|(i==3)) , (dif1+(i==3)-(i==6)) , (dif2+(i==3)-(i==9)) , pos+1)%MOD) )%MOD;
	}
	}
	return dp[isStart][isSmall][veThree][dif1][dif2][pos] = ret;
	}
	ll Calculate(int id)
	{
	num.clear();
	int i,sz = strlen(s[id]);
	for(i=0 ; i<sz ; i++)
	num.pb(s[id][i]-'0');
	ms(dp , -1);
	return FuN(1 , 0 , 0 , 17 , 17 , 0);
	}
	void Solve(int t)
	{
	ll ans1,ans2,ans;
	sc("%s %s",s[0],s[1]);
	ans2 = Calculate(1);
	ans1 = Calculate(0);
	ans = (ans2-ans1+MOD)%MOD;
	ll sz = strlen(s[0]) , cnt3=0,cnt6=0,cnt9=0,i;
	for(i=0 ; i<sz ; i++){
	if(s[0][i] == '3')
	cnt3++;
	else if(s[0][i] == '6')
	cnt6++;
	else if(s[0][i] == '9')
	cnt9++;
	}
	if(cnt3==cnt6 && cnt6==cnt9 && cnt3>0)
	ans = (ans+1)%MOD;
	pf("%lld\n",ans);
	}

view raw SPOJ - NUMTSN.cpp hosted with ❤ by GitHub