Codeforces Round #511 1034A, 1047C Enlarge GCD Solution [Part 2]

গত পর্বে আমি এই প্রোবলেম এর একটি সলিউশন আলোচনা করেছিলাম । আজ মুলত সেই সলিউশন এর ইমপ্লিমেন্টেশন নিয়ে আলোচনা করব । এরপরের পর্বে আলোচনা করব এই প্রোবলেম এর আরো কিছু সলিউশন নিয়ে । গত পর্বে যে সলিউশন বলেছিলাম, তা ছিল সবগুলো নাম্বার এর GCD বের করা ও প্রতিটা নাম্বার এর Prime Factorization করা । এরপরে GCD এর ভ্যালু তে যে প্রাইম যত বার আছে, ঐ প্রাইম কতগুলো নাম্বারে তার চেয়ে বেশি বার আছে সেটা বের করা...

Read More

Codeforces Round #511 1034A, 1047C Enlarge GCD Solution

Problem: n সংখ্যক নাম্বার দেয়া আছে । বলতে হবে- সর্বনিম্ন কয়টি সংখ্যা এই List থেকে Remove করলে, Remove করার আগে সবগুলো নাম্বার এর যে GCD, Remove করার পরে বাকি নাম্বার গুলোর GCD তার চেয়ে বড় হবে ? Constraints: সর্বোচ্চ $3.10^5$ টা নাম্বার দেয়া থাকবে । প্রতিটা নাম্বার এর সর্বোচ্চ মান হতে পারে 15000000 ($1.5 * 10^7$) Here is the problem link... Solution: What is GCD? GCD মানে হলো Greatest...

Read More

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

সমস্যাঃ$N$ নোড ও $E$ এজ বিশিষ্ট একটি গ্রাফ দেয়া আছে, যার প্রতিটা এজের ওয়েট (cost) বলে দেয়া আছে । এরপরে $Q$ সংখ্যক কুয়েরি দেয়া আছে । প্রতিটা কুয়েরিতে একটি নাম্বার $C$ দেয়া আছে । বলতে হবে, যেসব এজের ওয়েট $C$ এর কম, সেই এজগুলিকে যদি গ্রাফ থেকে মুছে দেয়া হয়, তবে ১ নাম্বার নোড থেকে কতগুলি নোডে যাওয়া সম্ভব । Constraints:ইনপুটে সর্বোচ্চ ১০ টি টেস্ট কেস দেয়া থাকবে । $1\leq \space N \space \leq 40,000...

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...

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 ত্রিভুজ তখনই হবে, যদি এর যে কোন দুই বাহুর যোগফল এর ৩য় বাহুর চেয়ে বড় হয় । আমরা যদি ৩ টা নেস্টেড লুপ চালিয়ে...

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...

Read More

[ Tutorial ] LightOj 1326 / UVa 12034 Solution

Problem description: n সংখ্যক ঘোড়া দৌড় প্রতিযোগিতায় অংশ নিয়েছে । বলতে হবে, কত উপায়ে দৌড় প্রতিযোগিতা শেষ হতে পারে । ans কে 10056 দিয়ে মড করে আউটপুট দেখাতে হবে । আর n এর সর্বোচ্চমান হতে পারে 1000 . Problem link: LightOj 1326 or, UVa 12034  Solution:আমরা ডাইনামিক প্রোগ্রামিং এর সাহায্যে...

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)...

Read More

[ Tutorial ] LightOj 1056 - Olympics

Problem description: 400 মিটার পরিধি বিশিষ্ট একটি athletic track বানাতে হবে, যার আকৃতি এরকম -   ট্র্যকের ভিতরের আয়তটির দৈর্ঘ্য ও প্রস্থের অনুপাত হতে হবে a:b । তোমাকে a ও b এর মান ইনপুট দেয়া আছে । বলতে হবে, আয়তটির দৈর্ঘ্য ও প্রস্থের মান কত হবে । Problem LinkSolution:মনে...

Read More

[tutorial] SPOJ AE00 - Rectangles

Problem Description: n সংখ্যক বর্গ আছে, যার প্রতিটা বাহুর দৈর্ঘ্য ১ ।বলতে হবে এই বর্গ গুলো দিয়ে কতগুলো ভিন্ন ভিন্ন আয়ত বানানো সম্ভব ।শর্ত হলো, কোন বর্গকে আরেকটার উপরে রাখা যাবে না, বা একাধিক বর্গ নিয়ে এর দৈর্ঘ্যকে পরিবর্তন করা যাবে না । যদি একটি আয়তের দৈর্ঘ্য a, প্রস্থ b হয়  এবং অন্য একটি আয়তের দৈর্ঘ্য b, প্রস্থ a হয় তবে তাদেরকে একই আয়ত হিসেবে গন্য করতে হবে । Prblem linkSolution: যদি দৈর্ঘ্য...

Read More