[ Tutorial ] LightOj 1326 / UVa 12034 Solution

Problem description:

n সংখ্যক ঘোড়া দৌড় প্রতিযোগিতায় অংশ নিয়েছে । বলতে হবে, কত উপায়ে দৌড় প্রতিযোগিতা শেষ হতে পারে ।
ans কে 10056 দিয়ে মড করে আউটপুট দেখাতে হবে ।

আর n এর সর্বোচ্চমান হতে পারে 1000 .

Problem link:

LightOj 1326 or, UVa 12034 

Solution:

আমরা ডাইনামিক প্রোগ্রামিং এর সাহায্যে প্রোবলেমটি সমাধান করতে পারি ।

উপরের রেখাগুলি দিয়ে বিভিন্ন পজিশন বুঝানো হয়েছে । ১ম রেখাটি ১ম পজিশন বুঝাচ্ছে, ২য় রেখাটি ২য় পজিশন বুঝাচ্ছে, ............ ইত্যাদি ।

প্রথমেই চিন্তা করি, যৌথ ভাবে ১ম হতে পারে কতজন ? ১ জন হতে পারে, ২ জন হতে পারে, ৩ জন হতে পারে, ......... এমনকি সবাই হতে পারে ।

এখন n সংখ্যক জনের মাঝে ১ জন প্রথম হতে পারে কত উপায়ে ? nC1 উপায়ে ।

n সংখ্যক জনের মাঝে ২ জন প্রথম হতে পারে কত উপায়ে ? nC2 উপায়ে ।

n সংখ্যক জনের মাঝে ৩ জন প্রথম হতে পারে কত উপায়ে ? nC3 উপায়ে ।

...........................

..........................

এভাবে, n সংখ্যক জনের মাঝে n জন প্রথম হতে পারে কত উপায়ে ? nCn উপায়ে ।

এখন, যে কয়জন যৌথভাবে ১ম পজিশনে আছে, তারা বাদে বাকিদের জন্য দেখতে হবে ২য়, ৩য়, ৪র্থ, ......... n তম হতে পারে কত উপায়ে ।

ধরি, x জন ১ম হয়েছে, তাহলে বাকি থাকল n-x জন । এখন n-x জন এর মাঝে ১ম পজিশনে ( এখানে ১ম পজিশন মানে বাকিদের মাঝে ১ম পজিশন, প্রকৃত পক্ষে ২য় পজিশন) থাকতে পারে কত উপায়ে ।

তাহলে সেক্ষেত্রেও কি একইভাবে আমরা হিসাব করতে পারিনা ? অর্থাৎ,
(n-x)C1, (n-x)C2, ...... এভাবে ।

অর্থাৎ এখানে রিকার্সন রিলেশন আছে ।

ধরি, calculate(n) একটি ফাংশন, যা n সংখ্যক ঘোড়া কত উপায়ে খেলা শেষ করতে পারে তা রিটার্ণ করে ।

তাহলে আমাদের ফাংশনটা লিখতে পারি এভাবে-

int calculate(int n)
{
    int cnt = 0;
    for(int i = 1;i<=n;i++)
    {
        cnt += nCr(n, i) * calculate(n-i);
    }
    return cnt;
}

উপরের ফাংশনে আমরা nCr() ফাংশনকে কল করেছি । আমরা প্রতিবার nCr ফাংশনকে কল না করে একবার nCr এর সব মান আগেই বের করে রাখতে পারি ।

আমরা জানি, nCr(x, y) = nCr(x-1, y-1) + nCr(x-1, y)
Problem এ n এর maximam value হতে পারে 1000, তাই আমরা 1000 পর্যন্ত nCr এর সব মান হিসাব করে 2D অ্যারেতে রাখতে পারি ।

int ncr[1001][1001];
void calNcr()
{
    ncr[1][1] = 1;
    ncr[1][0] = 1;
    for(int i = 2;i<=n;i++)
    {
        ncr[i][0] = 1;
        ncr[i][i] = 1;
        for(int j = 1;j<i;j++)
        {
            ncr[i][j] = ncr[i-1][j-1] + ncr[i-1][j];
        }
    }
}

এখন খেয়াল করি, calculate() ফাংশনে আমরা বারবার calculate() ফাংশন কে কল করছি । এখানে কিন্তু একই ভ্যালু দিয়ে বার বার একই ফাংশনকে কল করা হচ্ছে ।
যেমন, calculate(5),  কল করবে calculate(4),  calculate(3),  calculate(2),  calculate(1),  calculate(0) কে । calculate(4) কল করবে  calculate(3),  calculate(2),  calculate(1),  calculate(0) কে ।
calculate(3) কল করবে  calculate(2),  calculate(1),  calculate(0) কে ।
 ........ ইত্যাদি ।

যেহেতু, একই ভ্যালু দিয়ে একই ফাংশনকে বার বার কল করা হচ্ছে, তাই আমরা ডাইনামিক প্রোগ্রামিং এর সাহায্যে এটাকে ওভারকাম করতে পারি ।

আমরা  dp নামের একটি অ্যারে নেব, শুরুতেই এর মান -1 দিয়ে initialize করব । calculate(n) এর ভিতরে চেক করব, dp[n]  এর মান -1 কিনা । -1 না হলে, এই মান আগেই হিসাব করা আছে, তখন dp[n] এর মান রিটার্ণ করে দেব । না হলে হিসাব করব ।

নিচে সম্পুর্ণ কোড দিয়ে দিলাম-

Code:

	/*=================================*\
	Md. Shahidul Islam
	CSE, BRUR
	Rangpur, Bangladesh
	mail: shahidul.cse.brur@gmail.com
	FB : fb.com/shahidul.brur
	Blog: shahidul-brur.blogspot.com
	\*=================================*/
	#include<bits/stdc++.h>
	using namespace std;
	#define ll long long
	#define ull unsinged long long
	#define vi vector<int>
	#define vll vector<ll>
	#define ii pair<int, int>
	#define vii vector<pair<int, int> >
	#define vs vector<string>
	#define vd vector<double>
	#define mii map<int, int>
	#define mli map<ll, int>
	#define msi map<string, int>
	#define pb push_back
	#define mp make_pair
	#define ff first
	#define ss second
	#define sz size()
	#define all(a) a.begin(), a.end()
	#define rep0(i, k) for(int i=0;i<k;i++)
	#define rep1(i, k) for(int i=1;i<=k;i++)
	#define repab(i, a, b) for(int i=a;i<=b;i++)
	#define repba(i, b, a) for(int i=b;i>=a;i--)
	#define pi acos(-1.0)
	#define eps 1e-6
	#define mem(a, b) memset(a, b, sizeof(a))
	#define mod 10056
	#define inf 1e9
	const int MAX = 1100;
	int dp[MAX];
	int ncr[MAX][MAX];
	int solve(int n)
	{
	if(dp[n]!=-1)
	return dp[n];
	int cnt = 0;
	rep1(i, n)
	{
	cnt = cnt%mod + ( ncr[n][i]%mod) * (solve(n-i)%mod);
	cnt=cnt%mod;
	}
	dp[n] = cnt;
	return dp[n];
	}
	void calNcr()
	{
	ncr[1][1] = 1;
	ncr[1][0] = 1;
	repab(i, 2, 1000)
	{
	ncr[i][0] = 1;
	ncr[i][i] = 1;
	repab(j, 1, i-1)
	{
	ncr[i][j] = ncr[i-1][j-1]%mod + ncr[i-1][j]%mod;
	ncr[i][j] = ncr[i][j] % mod;
	}
	}
	}
	int main()
	{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	//ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n;
	calNcr();
	rep1(i, MAX)
	dp[i] = -1;
	dp[0] = 1;
	dp[1] = 1;
	solve(MAX);
	int t;
	cin>>t;
	rep1(cas, t)
	{
	cin>>n;
	cout << "Case " << cas << ": " << dp[n] << "\n";
	}
	return 0;
	}

view raw lightoj 1326.cpp hosted with ❤ by GitHub