Dp part - 4

DP নিয়ে আমার আগের লিখাগুলা পাওয়া যাবে এই লিঙ্ক এ । এই পোস্টে কিছু কমন ডিপি সল্যুশন নিয়ে আলোচনা করছি ।


nth premutation :

এই প্রবলেম এ বলা হয়েছে আমাদের একটা string দেওয়া হবে আমাদের এই string এর nth permutation ভ্যালু কত হবে তা বলতে হবে । যদি তা সম্ভব না হয় আমাদের "impossible" প্রিন্ট করতে হবে । এইখানে n এর ভ্যালু হতে পারে ২^৩১ । এইখানে একটা জিনিস দেখি আমরা string এর সাইজ হতে পারে হাইস্ট ২০ লেটারে এবং সব যদি ভিন্ন ভিন্ন লেটার হয় তাহলে পারমুটাশেন সম্ভব হত n! বা ২০! । যা অনেক বড় মান , আমরা যদি built in function,  next_premutation ব্যাবহার করে যাই তাহলে এইটা সম্ভব হবে না । এখন প্রবলেমটাকে ছোট করার জন্য আমরা corner-case চিন্তা করতে পারি । প্রথম এ আছি impossible case এ , কখন কখন impossible হবে । আমরা সহজেই লেটার ফ্রিকিউয়েন্সি কাউন্ট করে দেখতে পারি আমাদের দেওয়া string থেকে কতটা permutation possible , যদি এর মান আমাদের nth value এর মান এর থেকে কম হয় আমরা সহজেই  বলে দিতে পারি যে nth-value string পসিবল না পাওয়া । এইটা আমরা permutation এর ব্যাসিক ফরমুলা থেকে পেতে পারি ।

         ( size_of_the_string ) ! / ( frequency_of_every_letter_in_that_string ) ! ......... ( 1 )

এখন মেইন পার্ট । আমারা এখন nth-value পসিবল string এর কিভাবে আমরা এই  ভ্যালুটা পাব দেখব । আমরা কোন পজিশনে কোন লেটার বসিয়ে , এই লেটার এই পজিশনে বসবে এবং  এর জন্য কতটা permutation হতে পারে তা আমরা সহজেই ( ১ ) ইকুয়েশন থেকে পেয়ে যেতে পারি । যদি এর মান আমাদের nth_value এর চেয়ে কম হয় তাহলে আমরা বুঝব আসলে এই লেটার টা এইপজিশনে বসবে না আমাদের ফাইনাল string এর যদি বসত তা হলে এর জন্য মান nth_value এর সমান বা বেশি হত । কথাগুলা অসংলগ্ন লাগতে পারে একবারে পড়লে । একটা example এর মাধ্যমে দেখলে সহজ হয়ে যাবে  ।

Say string : abc , আমাদের বলতে হবে  এর ৬ষ্ঠ পারমুটেশনের স্ট্রিংটা কি ?

যদি 'a' final string এর ফাস্ট লেটার হত তাহলে আমরা 'a' কে প্রথম পজিশনে বসিয়ে b এবং c থেকে আরো 2টা পারমুটেশন পেতে পারতাম । ( abc , acb ) , কিন্তু তা ৬ এর চেয়ে কম অর্থাৎ আমরা বলতে পারি 'a' প্রথম পজিশনে বসিয়ে আমরা আমাদের ফাইনাল string পাব না । এখন 'b' কে যদি প্রথম পজিশনে বসাই তাহলে আমরা 'b' কে বসিয়ে আরো দুইটা পারমুটেশন পাব a and c এর জন্য । ( bac , bca ) , যেহেতু 'a' এর পর 'b' আসে তাই 'a' জন্য ও মানগুলা এইখানে যুক্ত হবে । টোটাল ২ + ২ = ৪ < ৬ অর্থাৎ 'b' বসিয়েও আমরা আমাদের ফাইনাল string টা পাব না । এখন 'c' এর জন্য দেখা যাবে একই ভাবে ৪ + ২ >= ৬ তাই ফাইনাল string এর প্রথম লেটার আমরা নিশ্চিত ভাবে বলতে পারি 'c' বসবে ,  এবং 'c' বসানোর মাধ্যমে আমরা 'a' এবং 'b' বসানোর জন্য মান গুলা আমাদের ফাইনাল স্ট্রিং থেকে বাদ দিয়ে পারি । এইভাবে প্রতিটা পজিশনের জন্য আমাদের ক্যালকুলেশন করে বুঝতে হবে কোন লেটারটা বসবে ।

কোড

	//BISMILLAHIRRAHMANIRRAHIM
	/*
	manus tar shopner soman boro
	all my suceesses are dedicated to my parents
	Author :: Shakil Ahmed
	.............AUST_CSE27.........
	prob ::
	Type ::
	verdict::
	*/
	#include <bits/stdc++.h>
	#define pb push_back
	#define mp make_pair
	#define pi acos(-1.0)
	#define ff first
	#define ss second
	#define re return
	#define QI queue<int>
	#define SI stack<int>
	#define SZ(x) ((int) (x).size())
	#define all(x) (x).begin(), (x).end()
	#define sqr(x) ((x) * (x))
	#define ms(a,b) memset((a),(b),sizeof(a))
	#define G() getchar()
	#define MAX3(a,b,c) max(a,max(b,c))
	#define II ( { int a ; read(a) ; a; } )
	#define LL ( { Long a ; read(a) ; a; } )
	#define DD ({double a; scanf("%lf", &a); a;})
	double const EPS=3e-8;
	using namespace std;
	#define FI freopen ("input.txt", "r", stdin)
	#define FO freopen ("output.txt", "w", stdout)
	typedef long long Long;
	typedef long long int64;
	typedef unsigned long long ull;
	typedef vector<int> vi ;
	typedef set<int> si;
	typedef vector<Long>vl;
	typedef pair<int,int>pii;
	typedef pair<string,int>psi;
	typedef pair<Long,Long>pll;
	typedef pair<double,double>pdd;
	typedef vector<pii> vpii;
	// For loop
	#define forab(i, a, b) for (__typeof (b) i = (a) ; i <= b ; ++i)
	#define rep(i, n) forab (i, 0, (n) - 1)
	#define For(i, n) forab (i, 1, n)
	#define rofba(i, a, b) for (__typeof (b)i = (b) ; i >= a ; --i)
	#define per(i, n) rofba (i, 0, (n) - 1)
	#define rof(i, n) rofba (i, 1, n)
	#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
	template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
	template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
	//Fast Reader
	template<class T>inline bool read(T &x){int c=getchar();int sgn=1;while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; x*=sgn; return ~c;}
	//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
	//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
	//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
	//int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction
	/* ************************************** My code start here ****************************************** */
	const int NX = 30 ;
	Long fact[NX] , nth_value ;
	int freq[NX] ;
	char inp[NX];
	void ini()
	{
	fact[0] = 1 ;
	Long i ;
	for( i = 1 ; i <= 25 ; i++ ) fact[i] = ( fact[i-1]* i);
	}
	Long occurence( int len)
	{
	Long now = fact[len];
	int i ;
	for( i = 0 ; i < 26 ; i++ ) now /= fact[freq[i]];
	return now ;
	}
	void solve(int sz)
	{
	while(sz)
	{
	Long upto = 0 ;
	bool found = 0 ;
	int i ;
	for ( i = 0 ; i < 26 && !found; i++ )
	{
	if( freq[i] == 0 ) continue ;
	freq[i]--;
	Long now = occurence(sz-1);
	if( now + upto >= nth_value)
	{
	nth_value -= upto;
	found = 1 ;
	printf("%c",i+'a');
	sz--;
	}
	else
	{
	upto += now ;
	freq[i]++;
	}
	// printf("i :: %c sz :: %d now :: %lld upto :: %lld nth :: %lld \n",i+'a',sz,now,upto,nth_value);
	}
	if( !found ) break;
	}
	puts("");
	}
	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 ;
	ini();
	for( cs = 1 ; cs <= t ; cs++ )
	{
	scanf("%s %lld",inp,&nth_value);
	// printf("hello\n");
	ms( freq , 0 );
	int sz = strlen(inp);
	// rep( i , sz ) printf(" integer :: %d \n",inp[i]-'a');
	rep( i , sz ) freq[inp[i]-'a']++;
	Long need = occurence(sz);
	printf("Case %d: ",cs);
	if( need < nth_value ) puts("Impossible");
	else solve(sz);
	}
	return 0;
	}

view raw DP441,cpp hosted with ❤ by GitHub

Be Efficient :

এই প্রবলেম এ বলা হয়েছে আমাদের n টা নাম্বার এবং আরো একটা নাম্বার m দেওয়া হবে । আমাদের বলতে হবে এই nটা নাম্বার এর মধ্যে কতগুলা নাম্বার consecutive sequence  m দ্বারা বিভাজ্য । যেমন যদি n = 3 এবং m = 3 হয় এবং n sequence numbers :  3 , 6 , 9 তাহলে মোট ..
{ 3 } , { 3 , 6 } , { 3 , 6 , 9 } , { 6 } , { 6 , 9 } , { 9 } এই  ছয়টি নাম্বার m = 3 দ্বারা বিভাজ্য ।

এইখানে একটা important point হচ্ছে m <= 10^5 . এইটা এইজন্য important আমরা তাহলে নিশ্চিতভাবে বলতে পারব যে consecutive number এর sequence এর mod value কখনই 10^5 থেকে বড় হবে না , যা আমরা কোন array তেও store করে রাখতে পারি । এইখানে কিছু key observation আছে এই consecutive mod value নিয়ে । যদি প্রথম নাম্বার এর জন্য mod value আসল ১ , আবার দেখা গেল প্রথম ৩টা নাম্বার নিয়ে mod value হচ্ছে ১ এবং আমারা যদি  প্রথম ৫টা নাম্বার নিয়েও একই ১ পাই  তাহলে আমরা দেখব যে প্রথম ২ - ৩ নাম্বার অবশ্যই m দ্বারা এবং একই ভাবে ২-৫ এবং ৪-৫ consecutive number গুলা m দ্বারা বিভাজ্য হবে । এইটা একটা example এর মাধ্যমে দেখলে ক্লিয়ার হবে ।

say n = 5 , m = 3 , n sequence numbers are : 1 , 2 , 1 , 1 , 2 । তাহলে { 2 , 1 } , { 2 , 1 , 1 , 2 } , { 1 , 2 } m = 3 দ্বারা ভাগ হবে । consecutive result এর জন্য mod value এর সাথে সাথে আমরা এড ভ্যালু বাড়িয়া আমাদের answer এর সাথে যোগ করব , কোন নাম্বার নিজেও একা m দ্বারা বিভাজ্য হতে পারে বলে mod = 0 , এর নাম প্রথমে ১ করে রাখব ।

কোড ঃ

	#include <stdio.h>
	#define rep(i,n) for(i=0;i<n;i++)
	#define MAX 100005
	int dp[MAX],a[MAX] ,n,m,cs,t,i;;
	long long int sum=0,ans=0;
	int main()
	{
	scanf("%d",&t);
	for(cs=1;cs<=t;cs++)
	{
	scanf("%d %d",&n,&m);
	rep(i,m) dp[i]=0;
	dp[0]=1;
	sum=ans=0;
	rep(i,n)
	{ scanf("%d",&a[i]);
	sum=(sum+a[i])%m;
	ans+=dp[sum];
	dp[sum]++;
	}
	printf("Case %d: %lld\n",cs,ans);
	}
	}

view raw dp442.cpp hosted with ❤ by GitHub