ICPC Dhaka Preli 2017: Problem D - Connecting To One solution

সমস্যাঃ

$N$ নোড ও $E$ এজ বিশিষ্ট একটি গ্রাফ দেয়া আছে, যার প্রতিটা এজের ওয়েট (cost) বলে দেয়া আছে ।

এরপরে $Q$ সংখ্যক কুয়েরি দেয়া আছে । প্রতিটা কুয়েরিতে একটি নাম্বার $C$ দেয়া আছে । বলতে হবে, যেসব এজের ওয়েট $C$ এর কম, সেই এজগুলিকে যদি গ্রাফ থেকে মুছে দেয়া হয়, তবে ১ নাম্বার নোড থেকে কতগুলি নোডে যাওয়া সম্ভব ।

Constraints:

1. ইনপুটে সর্বোচ্চ ১০ টি টেস্ট কেস দেয়া থাকবে ।
2. $1\leq \space N \space \leq 40,000 $
3. $1\leq \space E \space \leq 150,000 $
4. $1\leq \space |W| \space \leq 10^9 $, W বলতে এজের ওয়েট বুঝানো হচ্ছে ।
5. $1\leq \space Q \space \leq 10^5 $
6. $1\leq \space |C| \space \leq 10^9 $

সমাধানঃ

আমরা কোন গ্রাফ তৈরি করব না । 

এজগুলি ইনপুট নিয়ে ওয়েটের Descending order এ সর্ট করব ।

এরপরে সবগুলো কুয়েরি ইনপুট নিয়ে তাদেরকেও Descending order এ সর্ট করব । এরপরে আমরা কুয়েরি গুলি অফলাইনে প্রসেস করব । এক্ষেত্রে পরে যেহেতু আমাদের কুয়েরির ইন্ডেক্স প্রয়োজন হবে, তাই ইন্ডেক্স সহ রেখে ( যেমন pair<int, int> হিসেবে ) সর্ট করতে হবে ।

এখন সর্ট করা এজগুলি থেকে একটি করে এজ নিয়ে ঐ এজের নোড দুটিকে ডিসজয়েন্ট সেটে যুক্ত করব। সাথে এখন পর্যন্ত সেটে রাখা এজগুলির মাঝে সবচেয়ে কম ওয়েট কত তা একটি ভেরিয়েবলে (minCost) রাখব ।

আর পাশাপাশি সর্টেড কুয়েরি লিস্টের কোন কুয়েরিকে প্রসেস করছি, তার ইন্ডেক্স একটা ভেরিয়েবলে (curQ)রাখব ।

প্রতিটা এজ থেকে নোড দুটিকে ডিসজয়েন্ট সেটে যুক্ত করার পরে যদি এই এজের ওয়েট টা minCost এর চেয়ে ছোট হয়, তবে minCost এর ভ্যালুকে এই ওয়েট দিয়ে আপডেট করব ।

এরপরে দেখব, যদি minCost এর ভ্যালু curQ তম কুয়েরি তে C এর মান এর চেয়েও ছোট হয়, তবে যতক্ষণ curQ < Q এবং minCost বর্তমান যে কুয়েরিকে প্রসেস করছি তার C এর মানের চেয়ে ছোট হয়, ততক্ষণ curQ এর মান কে 1 করে বাড়াব, মানে কুয়েরির ইন্ডেক্স কে এক বাড়াব এবং আরো ডানে যাব ।

কেন ?

কারণ, এখন পর্যন্ত যুক্ত করা এজ গুলির মাঝে সর্বনিম্ন ওয়েট হলো minCost.

কিন্তু যেসব কুয়েরিতে এর চেয়েও বড় ওয়েট(C) দিয়ে কুয়েরি করা হয়েছে, সেখানে C এর চেয়ে ছোট সব এজ গ্রাফ থেকে মুছে যাবে । তাই কুয়েরির জন্য উত্তর হবে ০ (শুণ্য) । যেহেতু কুয়েরি গুলিকে Descending order এ সাজানো আছে, তাই C এর চেয়ে ছোট ভ্যালু দিয়ে কুয়েরি করা হয়েছে সেরকম কুয়েরি পেতে আমাদেরকে আরো ডান দিকে যেতে হবে ।

১ম যে পজিশনে কুয়েরির ভ্যালু(C), minCost এর চেয়ে ছোট বা সমান হবে, সেই কুয়েরির উত্তর হবে আমাদের ১ নাম্বার নোডের সাথে যুক্ত থাকা নোড গুলোর সেটের সাইজ ।

curQ তম ইন্ডেক্সের ans যত, যতক্ষণ curQ কে বাড়াচ্ছি, তার মাঝের এই ইন্ডেক্স গুলির ans ও হবে তাই ।

তাই তাদের ans কেও আপডেট করে দেব ।

কেন ?

কারণ, ৬ এর চেয়ে ছোট ওয়েটের এজ ডিলেট করলে ans যত হবে ৫ এর চেয়ে ছোট এজগুলিকে ডিলেট করলেও ans হয় তাই হবে, না হয় তার চেয়ে বেশি হবে, কিন্তু কম হবে না কখনো । কিন্তু এখানে মাঝের এসব ইন্ডেক্সের জন্য ans  বেশি হতে পারবে না, কারণ তাদের কুয়েরির ভ্যালু minCost এর চেয়ে ছোট না । 

১ম যেই কুয়েরি ইন্ডেক্সের ভ্যালু minCost এর চেয়ে ছোট বা সমান হবে সেই কুয়েরিতে এই বাড়তি এজ টা থাকতে পারবে । তার আগের গুলোতে এই জন্য আগের কুয়েরির ans টাই থাকবে । ans রাখার সময় কুয়েরি এর অরিজিনাল ইন্ডেক্সে ans টা ব্যবহার করে সেই ইন্ডেক্সে ans টা রাখব ।

এই অংশটা বুঝতে একটু খাতা কলম নিয়ে বসতে হবে, একটু চিন্তা করতে হবে । আর তাও না বুঝলে কমেন্টে জানালে আমি ব্যাখ্যা করব ।

সব এজ গুলোকে প্রসেস করা হয়ে গেলে আমাদের সব কুয়েরির জন্য ans পেয়ে যাব ।

এরপরে শুধু প্রতি টা কুয়েরির ans ইনপুট এর অর্ডারে প্রিন্ট করব - ব্যাস হয়ে গেল !!

কমপ্লেক্সিটি :  $O(E log E + Q log Q)$

কোডঃ

Read More

[Tutorial] Toph - Is It A Square (solution)

Problem Description:

$N$ সাইজ বিশিষ্ট অ্যারে $A$ দেয়া আছে । এরপরে Q সংখ্যক কুয়েরি আছে । প্রতি কুয়েরিতে দুইটি সংখ্যা দেয়া আছে $l$ ও $r$ । 

বলতে হবে, অ্যারের $l$ থেকে $r$ পর্যন্ত সব সংখ্যা গুলিকে গুণ করলে গুণফল পুর্ণ বর্গ হবে কি না । 

Constraints:

$1 \space \leq N \space \leq \space 10^5$

$1 \space \leq Q \space \leq \space 10^5$

$-10^5 \space \leq A[i] \space \leq \space 10^5$

Problem Link: Is it A Square

Solution:

Prerequisite:

সলিউশনের জন্য আগে থেকেই যা যা জানা থাকতে হবে - 

1.  Cumulative Sum or Prefix Sum, or Cumulative Frequency Counting
2. Sieve of Eratosthenes
3. Prime Factorization
4. MO's Algorithm

যেহেতু $10^5$ টা সংখ্যাকে গুণ করলে তা স্টোর করা সম্ভব না, অতএব আমাদের Square Number এর অন্য কোন প্রোপার্টিজ ব্যবহার করতে হবে ।

একটি সংখ্যা পূর্ণ বর্গ হলে, তার প্রতিটা প্রাইম ডিভিজর জোড় সংখ্যক বার থাকে । যেমন, ৯ = ৩ * ৩,

৪ = ২*২*২*২, ২৫ = ৫*৫, ৩৬ = ২*২*৩*৩ ইত্যাদি ।

অতএব, আমরা অ্যারে এর প্রতিটা সংখ্যাকে প্রাইম ফ্যাক্টোরাইজেশন করে নেব । এরপরে দেখব, $l$ থেকে $r$ পর্যন্ত অ্যারের সংখ্যাগুলোকে গুণ করলে তাদের গুনফলে প্রতিটা প্রাইম ডিভিসর জোড় সংখ্যক বার আছে কিনা ।

গুনফলে প্রতিটা প্রাইম ডিভিসর জোড় সংখ্যক বার আছে কিনা, সেটা আমরা MO's Algorithm ব্যবহার করে বের করব ।

odd নামের একটা global ভ্যারিয়েবল নেব, যার ভিতর থাকবে এখন পর্যন্ত মোট কয়টা প্রাইম ডিভিজর বিজোড় সংখ্যক বার আছে । 

MO's Algorithm এর প্রতি ধাপে যখন কোন ইন্ডেক্সে যাব, তখন সেই ইন্ডেক্সের সংখ্যাটির প্রতিটা প্রাইম ডিভিসর count এর মান 1 বাড়াবো (add এর ক্ষেত্রে ), অথবা 1 কমাবো (remove এর ক্ষেত্রে ) । প্রতিবার বাড়ানো বা কমানোর সময় চেক করব, ঐ প্রাইম ডিভিজর এর count এর বর্তমান মান এখন বিজোড় কিনা । যদি বিজোড় হয়, তবে odd এর মান এক বাড়াবো, বিজোড় না হলে odd এর মান এক কমাবো । ফুল রেঞ্জ iterate করার পরে যদি odd এর মান 0 হয় ( odd এর মান 0 মানে হলো, এখন পর্যন্ত বিজোড় সংখ্যক বার আছে এমন প্রাইম ডিভিজর এর পরিমাণ 0), তবে গুণফল Square নাম্বার হবে, নতুবা হবে না । 

তবে দুইটি কর্ণার কেস আছে :

1. যদি রেঞ্জের ভিতর এক বা একাধিক 0 থাকে, তবে গুণফল Square Number হবে । 
2. যদি রেঞ্জের ভিতরে বিজোড় সংখ্যক negative number থাকে, তবে গুণফল Negative Number হবে । অতএব এক্ষেত্রে গুণফল Square Number হবে না । 

তবে এই দুইটা কন্ডিশন আমরা Cumulative Sum এর সাহায্যে O(1) এই চেক করতে পারব ।


এই সলিউশনের complexity হবে $O((N+Q) . sqrt(N) . log n)$

Code:

Read More

LightOj 1307 - Counting Triangles Solution

Problem:

N সংখ্যক stick এর দৈর্ঘ্য দেয়া আছে । বলতে হবে এই Stick গুলি দিয়ে কত উপায়ে একটি valid ত্রিভুজ বানানো যাবে ।

constraints:

• $3\leq N \leq 2000$
• $1 \leq length \quad of  \quad each \quad  stick \leq 10^9$

Problem link: Lightoj 1307

Solution:

একটি valid ত্রিভুজ তখনই হবে, যদি এর যে কোন দুই বাহুর যোগফল এর ৩য় বাহুর চেয়ে বড় হয় । 

আমরা যদি ৩ টা নেস্টেড লুপ চালিয়ে all possible way তে সল্ভ করার চেষ্টা করি তবে অবশ্যই TLE খাবে ।

তাহলে, আমরা কি করতে পারি ?

আমরা প্রথমেই stick গুলোকে সর্ট করে নেই । 

এখন, প্রতিটা stick নিয়ে দেখব এর সাথে আর কোন দুইটি stick নিলে সেটা valid ত্রিভুজ হবে ।

২য় stick এর জন্যও কিন্তু আমরা লুপ চালিয়ে প্রতিটাই একবার করে নিয়ে দেখতে পারি, কারণ দুইটা নেস্টেড লুপ চালালেও TLE খাবে না, কারণ $N\leq 2000$ ।

তাহলে, এখন দেখতে হবে এই দুইটা stick এর সাথে কত উপায়ে ৩য় stick নির্বাচন করা যায়।

শর্ত মতে, ১ম বাহু + ২য় বাহু > ৩য় বাহু হতে হবে ।

অতএব, আমাদের দেখতে হবে  - ১ম বাহু ও ২য় বাহুর যোগফল অপেক্ষা ছোট, এমন কতগুলো stick আছে । 

যেহেতু stick গুলো সর্টেড আছে, তাই আমরা বাইনারি সার্চ করেই এটা বের করতে পারি । যেহেতু একই ভ্যালু রিপিট হতে পারে, অতএব আমাদেরকে upper bound বের করতে হবে । এতে করে আমাদের আরেকটা লুপ চালাতে হবে না । বাইনারি সার্চের কমপ্লেক্সিটি $O(log(n))$, অতএব আমাদের টোটাল কমপ্লেক্সিটি হচ্ছে $O(N^2log(n))$

upper_bound ওই ইন্ডেক্স এর pointer return করে যেই ইন্ডেক্স এর মান সার্চ করা মানের চেয়ে বড় । তার মানে ওই index এর আগে পর্যন্ত যে কোন মান সার্চ করা value এর চেয়ে ছোট বা সমান ।

তাহলে upper_bound দিয়ে আমাদেরকে সার্চ করতে হবে (১ম বাহু + ২য় বাহু - ১) । ২য় লুপ যদি j দিয়ে চালানো হয়, তবে এই (index - j) সংখ্যক stick কে ১ম ও ২য় বাহুর সাথে ৩য় বাহু হিসেবে ব্যবহার করা যাবে ।

Code:

Read More

LightOj 1045 - Digits of Factorial Solution

Problem:

$T$ সংখ্যক টেস্ট কেস আছে, যেখানে $T\leq 50000$

প্রতি কেসে দুইটা সংখ্যা দেয়া আছে, $n$ ও $b$, যেখানে, $1\leq n\leq 10^6, \quad 1\leq b\leq 10^3$

বলতে হবে, b based number system এ $n!$ (Factorial of n ) এ কতগুলো ডিজিট থাকবে ।

Problem link: LightOj 1045

 Soultion:

আমরা জানি, 10 based number system এ $x$ এর ডিজিট সংখ্যা = $\lfloor log_{10} x \rfloor + 1$

একইভাবে, $b$ based number system এ $x$ এর ডিজিট সংখ্যা = $\lfloor log_{b} x \rfloor + 1$

লগারিদমের সূত্রানুসারে,

\[log_x y = log_x z \times log_z y \]

\[\implies log_z y = \frac {log_x y}{log_x z}\]

\[\therefore log_b n = \frac {log_{10} n}{log_{10} b}\]

আবার, আমরা জানি,

\[log_{10} {(x \times y \times z)} = log_{10} {x} + log_{10} {y} + log_{10} {z}\]

যেহেতু, $n! = 1 * 2 * 3 * 4 * .......... * n$ , অতএব, 

\[log_{10} {(n!)} = log_{10} {1} + log_{10} {2} + .......... + log_{10} {n}\]

অতএব, আমরা আগেই $10^6$ পর্যন্ত সব সংখ্যার $log$ এর মান বের করে অ্যারেতে রাখব ।

এরপরে, প্রতি কেসে শুধু $n$ ও $b$ এর মান ইনপুট নেব এবং $\lfloor \frac {log_{10} n}{log_{10} b} \rfloor + 1$ এর মান প্রিন্ট করে আউটপুটে দেখাব ।

Code:

Read More

[ 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