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

Read More

[tutorial] SPOJ QUEEN - Wandering Queen solution

Problem description:

n x m সাইজের একটি দাবার বোর্ড আছে । বোর্ডে একটি Queen (মন্ত্রী) এর বর্তমান পজিশন ও টার্গেট পজিশন দেয়া আছে । বোর্ডে বিভিন্ন cell এ 4 ধরণের ক্যারেকটার আছে - 

1) S দিয়ে বুঝানো হয়েছে Queen (মন্ত্রী) এর starting পজিশন, 

2) F দিয়ে বুঝানো হয়েছে Queen (মন্ত্রী) এর Final পজিশন, 

3) .(dot) বুঝানো হয়েছে ফাকা cell, যেখানে মুভ দেয়া যাবে ।

4) X দিয়ে বুঝানো হয়েছে নিষিদ্ধ cell ।

আউটপুটে বলতে হবে, Queen টা মিনিমিমাম কতটা মুভ দিয়ে starting cell থেকে final পজিশনে যেতে পারবে ।

Problem Link

সমাধান:

Queen যে কোন cell থেকে ৮ দিকে মুভ দিতে পারে এবং একটি মুভে যে কোন দিকে যত দূর ইচ্ছা যেতে পারে, যতক্ষণ না কোন নিষিদ্ধ cell না পায় ।

যদি কোন Queen (x, y) পজিশনে থাকে, তবেঃ

 ১) সে ডান দিকে (x, y+1), (x, y+2), (x, y+3), ... এভাবে (x, m-1) পজিশন পর্যন্ত যে কোন  cell এ যেতে পারে, যতক্ষণ  না কোন নিষিদ্ধ cell পায় ।

 ২) সে বাম দিকে (x, y-1), (x, y-2), (x, y-3), ... এভাবে (x, 0) পজিশন পর্যন্ত যে কোন  cell  এ যেতে পারে, যতক্ষণ  না কোন নিষিদ্ধ cell পায় ।

 ৩) সে উপর দিকে (x-1, y), (x-2, y), (x-3, y), ... এভাবে (0, y) পজিশন পর্যন্ত যে কোন  cell  এ যেতে পারে, যতক্ষণ  না কোন নিষিদ্ধ cell পায় ।

 ৪) সে নিচ দিকে (x+1, y), (x+2, y), (x+3, y), ... এভাবে (n-1, y) পজিশন পর্যন্ত যে কোন  cell এ যেতে পারে, যতক্ষণ  না কোন নিষিদ্ধ cell পায় ।

 ৫) সে lower right corner বরাবর (x+1, y+1), (x+2, y+2), (x+3, y+3), ... এভাবে যতক্ষণ  না board এর বাইরে চলে যায় বা নিষিদ্ধ cell পায়, যে কোন  cell এ যেতে পারে ।

 ৬) সে lower left corner বরাবর (x+1, y-1), (x+2, y-2), (x+3, y-3), ... এভাবে যতক্ষণ  না board এর বাইরে চলে যায় বা নিষিদ্ধ cell পায়, যে কোন  cell এ যেতে পারে ।

 ৭) সে upper right corner বরাবর (x-1, y+1), (x-2, y+2), (x-3, y+3), ... এভাবে যতক্ষণ  না board এর বাইরে চলে যায় বা নিষিদ্ধ cell পায়, যে কোন  cell এ যেতে পারে ।

 ৮) সে upper left corner বরাবর (x-1, y-1), (x-2, y-2), (x-3, y-3), ... এভাবে যতক্ষণ  না board এর বাইরে চলে যায় বা নিষিদ্ধ cell পায়, যে কোন  cell এ যেতে পারে ।

তাহলে আমরা প্রতি মুভে কারেন্ট পজিশন থেকে ৮ দিকে যত গুলো possible মুভ দেয়া সম্ভব তা এক চালেই দিতে পারি ।

এজন্য আমরা যে cell এ S আছে, সেখান থেকে একটি BFS চালাতে পারি । এখান থেকে এক মুভ দিয়ে ৮ দিকে যে সব cell এ যাওয়া সব cell গুলোকে Queue তে push করে রাখব । শুধু ৮ দিকের adjacent cell গুলো নয়, যত গুলো cell এ যাওয়া যায়, সবগুলোকেই Queue তে পুশ করে রাখব ।

এরপরে সেই একই কাজ । প্রতিবার Queue এর front cell টা নেব, এবং সেখান থেকে এক মুভ দিয়ে ৮ দিকে যে সব cell এ যাওয়া সব cell গুলোকে Queue তে push করে রাখব ।

যখন Target cell পাব, তখন তার distance রিটার্ণ করে দেব ।

কিন্ত এখানে একটি ঝামেলা আছে, তা হলো visited cell কে কন্ট্রোল করা । 

কিরকম ঝামেল ? একটা উদাহরণ দেই - 

উপরের চিত্রে, ৮ x ৮ সাইজের একটি দাবা বোর্ড দেখানো হয়েছে । ডান দিকে row এর নাম্বার, আর নিচে column এর নাম্বার দেয়া আছে ।

মনে কর, শুরুতে Queen টি (৪, ৩) পজিশনে আছে । এখান থেকে সে এক মুভে লাল রেখা চিহ্নিত ঘরগুলোর যে কোন ঘরে যেতে পারে ।

ধর, সে ডান দিকে (৪, ৪) পজিশনে গেল । এখান থেকে নীল রেখা চিহ্নিত ঘরগুলোর যে কোন ঘরে যেতে পারে ।

খেয়াল কর, আমি বামে বা ডানে রেখা টানিনি । কারণ, বামে এবং ডানে সব ঘরই visited হয়ে আছে ।

কিন্তু, (৪, ৫) ঘরটি আগে visited হলেও আবার visit করেছে, কারণ তার নিচের ঘর গুলো এখনো unvisited আছে । সে গুলো visit করতে হলে (৪, ৫) ঘরের উপর দিয়ে নিচে যেতে হবে ।

তাহলে, ব্যাপার টা কী দাড়ালো ? কোন ঘর visited হলেই থামা যাবে না । আবার কোন দিকে সব ঘরই visited হয়ে থাকলে আর visit করে লাভ নেই, এতে করে শুধু শুধু সময় বেশি নেবে ।

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

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

তাহলে এর থেকে মুক্তির উপায় কী ?

উপায়টা হলো, ঐ যে বললাম, যদি সব ঘরই ভিজিট হয়ে থাকে, তাহলে ভিজিট করার দরকার নেই । যেমন, (৪, ৪) থেকে বামে আর ডানে যাইনি ।

কিন্তু কিভাবে বুঝব, ঐ বরাবর সব ঘরই ভিজিট করা আছে কিনা ?

খেয়াল কর, কোন রো বামে বা ডানে থেকে visit করা একই কথা, কারণ বাম থেকে ডানে যত গুলো ঘরে যাওয়া যাবে, ডান থেকে বামে তত গুলো ঘরেই যাওয়া যাবে ।

একই ভাবে, কোন কলাম উপরে বা নিচে থেকে visit করা একই কথা, কারণ উপরে থেকে নিচে যত গুলো ঘরে যাওয়া যাবে, নিচ থেকে উপরেও তত গুলো ঘরেই যাওয়া যাবে ।

একই কথা কোণাকুনি যাবার ক্ষেত্রেও প্রযোজ্য ।

তাহলে, কোন ঘর ভিজিট করার দিক ৮ নয়, আসলে ৪ ।

১) বাম-ডান বরাবর,

২) উপর-নিচ বরাবর,

৩) কোণাকুনিভাবে upper left বা lower right বরাবর,

৪) কোণাকুনিভাবে upper right বা lower left বরাবর ।

তাহলে, কোন ঘর visit করার সময় যদি আমরা visited array তে ঘরটি কোন দিক থেকে visited হয়েছে, এই তথ্য রাখি তবেই সমস্যাটির সমাধান হয়ে যাবে ।

যেমন, আমরা (৩, ৪) থেকে যখন বামে বা ডানে কোন ঘর visit করেছি, তখন ঐ ঘরটি ১ নাম্বার উপায়ে visit করা হয়েছে এটা রেখে দিলাম । তাহলে পরবর্তীতে আর ১ নাম্বার উপায়ে এর কোন ঘর visit করব না ।

উদাহরণ হিসেবে ধর, আমরা visited array টা এভাবে নিলামঃ bool visited[1005][1005][5];

তাহলে, (৩, ৪) থেকে ডানের যে কোন ঘর (p, q) ভিজিট করার সময় visited[p][q][1] = 1; করে দেব । এরপরে, (৪, ৪) থেকে যখন ডানে (৪, ৫) ভিজিট করতে চাইব, তখন আগেই দেখব visited[4][5][1] = 1 কিনা । যদি 1 হয়ে থাকে, তার মানে এই ঘরটি বাম-ডান বরাবর visit করাই আছে । তাই আর visit করব না।

আর BFS এর শুরুতেই আমরা starting cell এর ৪ টা দিক বরাবরই visited array এর মান 1 করে দেব, কারণ, starting cell থেকে ১ম বারই ৪ দিকের সব cell ভিজিট করব । তাই এই cell এ আর আসার দরকার নেই ।

Code:

Read More

[ Tutorial ] LightOj 1056 - Olympics

Problem description:

400 মিটার পরিধি বিশিষ্ট একটি athletic track বানাতে হবে, যার আকৃতি এরকম - 

 ট্র্যকের ভিতরের আয়তটির দৈর্ঘ্য ও প্রস্থের অনুপাত হতে হবে a:b । তোমাকে a ও b এর মান ইনপুট দেয়া আছে । বলতে হবে, আয়তটির দৈর্ঘ্য ও প্রস্থের মান কত হবে ।

Problem Link

Solution:

মনে করি আয়তটি, ABCD ।

আয়তের প্রস্থের দু পাশে যে দুইটা বৃত্তচাপ আছে, তারা একই বৃত্তের চাপ ।

অতএব, আয়তের কর্ণের দৈর্ঘ্য হবে ঐ বৃত্তের ব্যাস ।

অতএব, AC = sqrt(AD^2 + CD^2)

অতএব, r = OC = OD = AC/2

আমরা জানি, cos A = (b^2 + c^2 - a^2)/2bc

অতএব, cos(theta) = cos COD = (r^2 + r^2 - b^2)/2.r.r

অতএব, s = r.theta

মনে করি, অনুপাতকে x দিয়ে গুণ করলে বাহুর দৈর্ঘ্য পাওয়া যাবে ।

এখন, চাপ = s.x

আয়তের দৈর্ঘ্য = a.x

অতএব, 2.s.x + 2.a.x = 400

অতএব, x = 400 / (2s + 2a)

এখন, আউটপুট হবে a.x এবং b.x

Code:

Read More

[tutorial] SPOJ AE00 - Rectangles

Problem Description:

n সংখ্যক বর্গ আছে, যার প্রতিটা বাহুর দৈর্ঘ্য ১ ।

বলতে হবে এই বর্গ গুলো দিয়ে কতগুলো ভিন্ন ভিন্ন আয়ত বানানো সম্ভব ।

শর্ত হলো, কোন বর্গকে আরেকটার উপরে রাখা যাবে না, বা একাধিক বর্গ নিয়ে এর দৈর্ঘ্যকে পরিবর্তন করা যাবে না ।

যদি একটি আয়তের দৈর্ঘ্য a, প্রস্থ b হয়  এবং অন্য একটি আয়তের দৈর্ঘ্য b, প্রস্থ a হয় তবে তাদেরকে একই আয়ত হিসেবে গন্য করতে হবে ।

Prblem link

Solution:

যদি দৈর্ঘ্য 1 হয় তবে প্রস্থ হতে পারে, 1, 2, 3, ...... সর্বোচ্চ n = মোট n টা আয়ত

যদি দৈর্ঘ্য 2 হয় তবে প্রস্থ হতে পারে, 1, 2, 3, ...... সর্বোচ্চ n/2 = মোট n/2 টা আয়ত

যদি দৈর্ঘ্য 3 হয় তবে প্রস্থ হতে পারে, 1, 2, 3, ...... সর্বোচ্চ n/3 = মোট n/3 টা আয়ত

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

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

এভাবে, যদি দৈর্ঘ্য n হয় তবে প্রস্থ হতে পারে সর্বোচ্চ 1, কারণ n/n = 1, মোট 1 টা আয়ত ।

এখানে খেয়াল কর, দৈর্ঘ্য 1 এর জন্য আয়তের (দৈর্ঘ্য, প্রস্থ) = (1, 1), (1, 2), (1, 3), ....., (1, n)

আবার, দৈর্ঘ্য 2 এর জন্য আয়তের (দৈর্ঘ্য, প্রস্থ) = (2, 1), (2, 2), (2, 3), ....., (2, n/2)

দৈর্ঘ্য 3 এর জন্য আয়তের (দৈর্ঘ্য, প্রস্থ) = (3, 1), (3, 2), (3, 3), ....., (3, n/3)

খেয়াল কর, ১ এর জন্য (১, ২) আছে, আবার ২ এর জন্য আছে (২, ১), অর্থাৎ রিপিট হচ্ছে ।

আবার, ১ এর জন্য (১, ৩) আছে, ২ এর জন্য আছে (২, ৩), আবার ৩ এর জন্যও আছে (৩, ১), (৩, ২), অর্থাৎ, আবারো রিপিট ।

এভাবে, যে কোন দৈর্ঘ্য i এর জন্য i-1 পর্যন্ত আসলে আগেই তৈরি করা হয়েছে ।

তাই i দৈর্ঘ্য বিশিষ্ট মোট n/i - (i-1) টা নতুন আয়ত বানানো সম্ভব ।

তাহলে আউটপুট হবে, i = 1 থেকে শুরু করে i<=n পর্যন্ত  প্রতি দৈর্ঘ্যের জন্য যতগুলো করে আয়ত বানানো যাবে তাদের যোগফল ।

Code:

Read More

[tutorial] UVa 11629 - Ballot Evaluation

Problem Description:

ইলেকশনে n সংখ্যক দল আছে । কোন দল কত ভোট পেয়েছে, তা দেওয়া আছে । এরপরে দেওয়া আছে কিছু অনুমান(তুলনা) । প্রতিটা তুলনা এভাবে দেওয়া আছে,

p1 + p2 + ....+pn comaprison value

যেখানে, p1, p2, ..... pn হলো পার্টির নাম, comparison হিসেবে থাকতে পারে <, >, =, <= অথবা >=, আর value হিসেবে থাকতে পারে ১ থেকে ১০০ এর মাঝে একটি পুর্ণ সংখ্যা ।

আউটপুটে বলতে হবে, অনুমানটা ঠিক নাকি ভুল ।

Problem Link:

সমাধান:

আমরা map<string, float> টাইপের একটি ম্যাপ নিতে পারি ।

যখন কোন দলের ভোটের পরিমাণ ইনপুট দেয়া হবে, তখনই আমরা সেটা ম্যাপে রাখব । এরপরে যখনই কোন অনুমান দেয়া হবে, আমরা string এর ১ম থেকে + চিহ্ন পাবার আগ পর্যন্ত একটি করে string বানাব, আর ম্যাপ থেকে তার vote এর মান কে যোগ করতে থাকব । এরপরে ওই যোগফল কে প্রদত্ত value এর সাথে তুলনা করে আউটপুট দেখাব ।

কোড:

Read More