[ 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: