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

গত পর্বে আমি এই প্রোবলেম এর একটি সলিউশন আলোচনা করেছিলাম । আজ মুলত সেই সলিউশন এর ইমপ্লিমেন্টেশন নিয়ে আলোচনা করব । এরপরের পর্বে আলোচনা করব এই প্রোবলেম এর আরো কিছু সলিউশন নিয়ে ।

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

Prime Factorization in Efficient way:

এখন Prime Factorization এর সাধারণ যে পদ্ধতি সবাই ব্যবহার করে, তার কমপ্লেক্সিটি- $O(sqrt(n))$ ।

এই প্রোবলেমে $3*10^5$ টা নাম্বার আছে, প্রতিটা নাম্বার হতে পারে সর্বোচ্চ $1.5 * 10^7$ । তাই $O(sqrt(n))$  কমপ্লেক্সিটিতে Prime Factorization করলে টাইম লিমিটে কুলাবে না ।

এজন্য আমাদেরকে $O(logn)$ কমপ্লেক্সিটিতে Prime Factorization করতে হবে । এ জন্য আমরা প্রথমে সিভ চালিয়ে প্রতিটা নাম্বার এর সর্বনিম্ন প্রাইম ফ্যাকটর বের করে নেব ।

 এখন কোন নাম্বার এর Prime Factorization এর সময় সেই নাম্বার এর সর্বনিম্ন প্রাইম ফ্যাকটর দিয়ে যতক্ষণ ভাগ করা যায়, ভাগ করতে থাকব । ভাগ করার পরে যে নতুন নাম্বার পাব, তাকেও আবার তার সর্বনিম্ন প্রাইম ফ্যাকটর দিয়ে যতক্ষণ ভাগ করা যায়, ভাগ করতে থাকব । এভাবে যতক্ষণ সংখ্যাটি ১ এর চেয়ে বড় ততক্ষণ চলতে থাকবে ।

তাহলে GCD এর Prime Factorization এ কোন প্রাইম কত বার আছে, সেটা বের করার জন্য কোড হবে এরকম-

যেহেতু কোন নাম্বার এর সর্বোচ্চ log(n) টা প্রাইম ফ্যাকটর থাকতে পারে, তাই এটার কমপ্লেক্সিটি হবে $O(logn)$

Using Memory in Efficient Way:

এখন প্রতিটা প্রাইম ১ বার আছে কতগুলো নাম্বারে, ২ বার আছে কতগুলো নাম্বারে,... এভাবে সর্বোচ্চ ২৩ বার আছে কতগুলো নাম্বারে তা স্টোর করতে একটা 2D অ্যারে freq[][] লাগবে, যেখানে freq[i][j] স্টোর করবে i তম প্রাইম j বার আছে অ্যারের কতগুলো নাম্বারে । এই অ্যারের সাইজ হবে $1.5 * 10^7 * 24$ । কিন্ত এত বড় অ্যারে মেমোরি লিমিটে কুলাবে না । তাহলে কী করতে পারি ?

1.5 * 10^7 পর্যন্ত প্রাইম আছে 970704 টা । আমরা প্রাইম নাম্বার ইউজ না করে তার সিরিয়াল নাম্বার ব্যবহার করতে পারি । ১ম প্রাইম ২, ২য় প্রাইম ৩, ৩য় প্রাইম ৫,... । তাই ২ এর জন্য ১, ৩ এর জন্য ২, ৫ এর জন্য ৩,... ব্যবহার করব । তাহলে এই 2D অ্যারের সাইজ হবে 970704 * 24, যা মেমোরি লিমিটে কুলাবে ।

Calculating Frequency of Each Prime in Factorization:

আমরা প্রতিটা নাম্বার এর প্রাইম ফ্যাক্টোরাইজেশনের সময় freq[][] অ্যারেটা তৈরি করে নিতে পারি। যখন কোন প্রাইম পাব, তার সিরিয়াল নাম্বার আছে maap[] নামের অ্যারেতে । যদি ঐ প্রাইম tot বার পাওয়া যায়, তবে আমরা freq[maap[pf]][tot]++ করে দেব, যেখানে pf হলো প্রাইম ফ্যাক্টর ।

Using Cumulative Sum aka Prefix Sum: 

আমরা freq[][] নামের একটা 2D অ্যারে নেব, freq[i][j] স্টোর করবে i তম প্রাইম j বার আছে অ্যারের কতগুলো নাম্বারে ।

আমরা চাই freq[i][j] স্টোর করবে i তম প্রাইম j বার বা j এর চেয়ে বেশি বার আছে অ্যারের কতগুলো নাম্বারে । এজন্য আমরা প্রতি i তম প্রাইম এর লুপের ভিতরে freq[i][j] = freq[i][j+1] করে দিলেই হবে ।

Calculating answer:

যদি মোট c টা প্রাইম থাকে ১৫০০০০০০ পর্যন্ত, তবে প্রতি প্রাইম এর জন্য আমাদের দেখতে হবে সেই প্রাইম GCD তে আছে কতবার, এবং তার চেয়ে বেশি বার আছে কতগুলো নাম্বারে। যতগুলো নাম্বারে তার চেয়ে বেশি বার আছে, সেই নাম্বার গুলো অ্যারেতে রেখে বাকিগুলো রিমুভ করে দিলে এই রেখে দেয়া নাম্বারগুলোর GCD সবগুলো নাম্বার এর GCD এর চেয়ে বড় হবে ।
এভাবে প্রতিটা প্রাইম নাম্বার এর জন্য দেখতে হবে, কতগুলো নাম্বার রিমুভ করতে হবে এবং এদের মাঝে সর্বনিম্নটাই হবে answer.
যদি সবগুলো নাম্বারই রিমুভ করতে হয়, অর্থাৎ answer যদি n হয় ( এটা তখনই হবে, যদি অ্যারের সব নাম্বারই একই হয়), তবে output হবে -1.

সম্পূর্ণ কোডঃ

কোডফোর্সেসে আমার সলিউশন এর রান টাইম ছিল 0.358 second, টাইম লিমিট ছিল 1 second.

Codeforces এ সাবমিশন লিংকঃ https://codeforces.com/contest/1047/submission/48318621

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

তাহলে আজ এ পর্যন্তই । সামনের পর্বে এই প্রোবলেম এর আরো কিছু সলিউশন নিয়ে আলোচনা করব ।
আল্লাহ হাফেজ । হ্যাপি কোডিং ।

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 Common Divisor. GCD কে বাংলায় গরিষ্ঠ সাধারণ গুণনীয়ক বা গ.সা.গু. বলা হয় । দুই বা ততোধিক সংখ্যার GCD হলো- যেসব সংখ্যা দিয়ে প্রতিটি নাম্বারকেই নিঃশেষে ভাগ করা যায় ( অর্থাৎ, যেসব সংখ্যা দিয়ে প্রতিটা সংখ্যাকে ভাগ করলে কোন ভাগশেষ বা remainder থাকে না), এমন সংখ্যাগুলোর মাঝে সবচেয়ে বড় সংখ্যা ।

যেমন, ১২, ১৮ ও ৬০ এর GCD হলো.৬ । কারণ, যেসব সংখ্যা দিয়ে ১২,১৮ ও ৬০ প্রতিটি নাম্বারকেই নিঃশেষে ভাগ করা যায় তারা হলো- ১,২,৩,৬ । এদের মাঝে সবচেয়ে বড় হলো ৬ । তাই এদের GCD হলো ৬ ।

Relation of GCD with Prime Factors:

যেসব নাম্বার এর GCD বের করতে হবে, তাদের প্রতিটা নাম্বারকে যদি Prime Factorization (মৌলিক উৎপাদকে বিশ্লেষণ) করা হয়, তবে তাদের GCD হবে- যেসব Prime নাম্বার (মৌলিক সংখ্যা) প্রতিটা নাম্বার এর Divisor (উৎপাদক) হিসেবে আছে, তাদের প্রতিটি Prime নাম্বারকে দেখতে হবে কোন সংখ্যার মাঝে ঐ Prime কতবার গুণ আকারে আছে, অর্থাৎ কোন সংখ্যার মাঝে ঐ Prime এর Power বা ঘাত কত । প্রতিটা Prime এর জন্য ঐ Prime প্রদত্ত সংখ্যাগুলোর মাঝে সর্বনিম্ন যত বার আছে, অর্থাৎ Prime এর সর্বনিম্ন Power যত আছে, তত বার গুণ করতে হবে । এভাবে সব Prime কে গুণ করলে যে গুণফল পাওয়া যাবে সেটাই হলো ঐ সংখ্যাগুলোর GCD.

উদাহরণ:

মনে করি, আমরা ১২, ১৮ ও ৬০ এর GCD বের করব । এখন এদের প্রতিটাকে Prime Factorization(মৌলিক উৎপাদকে বিশ্লেষণ) করে পাই-

১২ = ২ * ২ * ৩
১৮ = ২ * ৩ * ৩
৬০ = ২ * ২ * ৩ * ৫

এখানে,  ২ ও ৩ এই দুইটা Prime প্রতিটা নাম্বার এর মাঝেই আছে ।
১২ এর মাঝে ২ আছে ২ বার, ১৮ এর মাঝে ২ আছে ১ বার, ৬০ এর মাঝে ২ আছে ২ বার । তাহলে ২ সর্বনিম্ন আছে ১ বার ।
১২ এর মাঝে ৩ আছে ১ বার, ১৮ এর মাঝে ৩ আছে ২ বার, ৬০ এর মাঝে ৩ আছে ১ বার । তাহলে ৩ সর্বনিম্ন আছে ১ বার ।

৫ শুধু ৬০ এর মাঝে আছে ১ বার, আর কারও মাঝে নেই । এজন্য ৫ নেয়া যাবে না ।

তাই ১২, ১৮ ও ৬০ GCD বের করার জন্য ২ গুণ হবে ১ বার, ৩ গুণ হবে ১ বার ।
সুতরাং, ১২, ১৮ ও ৬০ এর GCD = ২ * ৩ = ৬

Back to the Problem:

মনে করি, আমাদেরকে যে n টা নাম্বার দেয়া আছে, তাদের GCD হলো g.

তাহলে g এর Prime Factorization করলে যেসব Prime g এর মাঝে পাওয়া যাবে, তাদের প্রতিটা Prime g এর মাঝে যত বার আছে, n টা নাম্বার এর প্রতিটা নাম্বার এর মাঝে কমপক্ষে তত বার আছে, কিছু কিছু নাম্বার এর মাঝে তার চেয়েও বেশি বার আছে ।

আমাদেরকে n টা নাম্বার এর মাঝে সর্বনিম্ন পরিমাণ নাম্বারকে remove করে g এর মানকে আরো বড় বানাতে হবে । এখন, g এর মান আরো বড় করা হবে কিভাবে ? কিছু নাম্বারকে যদি লিস্ট থেকে বাদ দেয়া হয়, তবে g এর মান আরও বড় করা যেতে পারে । কী রকম ?

মনে করুন, আপনারা কিছু ফ্রেন্ড মিলে পিকনিকে যাবেন । এখন প্রত্যেকের চাদা কত করে ধরবেন ? প্রত্যেক ফ্রেন্ডকে আপনি জিজ্ঞেস করবেন যে সে সর্বোচ্চ কত চাদা দিতে পারবে । সব ফ্রেন্ড এর মাঝে যে সবচেয়ে কম পরিমাণ চাদা দিতে পারবে, আপনি যদি তার চেয়ে বেশি চাদা ধরেন, তবে সে যেতে পারবে না । তাহলে সর্বনিম্ন যত চাদা ধরলে প্রত্যেক ফ্রেন্ডই সেই পরিমাণ চাদা দিতে পারবে তত করে চাদা ধরবেন, তাই না?

এখন আপনার এই ফ্রেন্ডদের মাঝে কেউ অনেক কিপ্টে থাকতে পারে ( সেফু দার ভাষ্য মতে অনেক গরীব :p), যারা অনেক কম চাদা দিতে দিবে, বেশি হলে যাবে না পিকনিকে ।

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

আমাদের প্রোবলেমে কিন্তু বলেনি GCD কে maximize করতে হবে, অর্থাৎ, বাড়িয়ে যত বড় করা যায় তত বড় করতে হবে তা বলেনি ।

মানে, g এর মান এখন যা, নাম্বার remove করার পরে  তার চেয়ে বড় হলেই হলো । আমাদেরকে বলতে হবে, সর্বনিম্ন কয়টা নাম্বার remove করলে বাকি নাম্বারগুলোর GCD, g এর চেয়ে বড় হবে ।

GCD এর মান বড় করার জন্য আমরা কী করতে পারি ?

g এর মাঝে কোন একটা prime যত বার আছে, তাকে তার চেয়ে বেশি বার গুণ করলে g এর মান বাড়বে ।
কিছু prime g এর মাঝে নেই, তার মানে তারা 0 বার আছে মনে করতে পারি ।

g এর মান যেহেতু বড় করলেই হলো, তাহলে কোন একটা prime g এর মাঝে যত বার আছে, যদি তার চেয়েও একবার বেশি থাকার উপায় বের করা যায়, তবেই আমাদের কাজ শেষ !

ধরি, কোন একটা Prime p, g এর মাঝে আছে x বার । আমরা চাই, p কে x+1 বার রাখতে । p কখন x+1 বার থাকবে g এর মাঝে ? যদি প্রতিটা নাম্বার এর মাঝেই p কমপক্ষে x+1 বার থাকে, তবেই p g এর মাঝেও  x+1 বার থাকবে ।
তার মানে, এই লিস্টে যেসব নাম্বার এর মাঝে p কমপক্ষে x+1 বা তার চেয়ে বেশি বার আছে, তাদেরকে রেখে বাকি নাম্বারগুলোকে রিমুভ করতে হবে । ধরি, p কমপক্ষে x+1 বা তার চেয়ে বেশি বার আছে n টা নাম্বার এর মাঝে এমন আছে y টা । তাহলে রিমুভ করতে হবে n-y টা ।

তাহলে এভাবে প্রতিটা প্রাইম এর জন্য আমরা চেক করব যে ঐ প্রাইম এর পরিমাণ g এর prime factorization এ এক বাড়াতে কতগুলো নাম্বার রিমুভ করতে হবে । এভাবে যে ক্ষেত্রে সবচেয়ে কম পরিমাণ রিমুভ করতে হবে, সেই সর্বনিম্ন পরিমাণটাই হবে এই problem এর আউটপুট ।

Algorithm to solve the problem:

1. n টা নাম্বার এর GCD, g বের করি ।
2. n টা নাম্বার এর প্রতিটা নাম্বারকেই prime factorization করি ।
3. g এর মাঝে কোন prime কত বার আছে, তা বের করি ।
4. 1 থেকে 15000000 পর্যন্ত প্রতিটা prime নাম্বার এর জন্য সেই প্রাইম ১ বার আছে কতগুলো নাম্বার এর মাঝে, ২ বার আছে কতগুলো নাম্বার এর মাঝে, ৩ বার আছে কতগুলো নাম্বার এর মাঝে, .........বের করি ।
5. Cumulative sum (prefix sum) ব্যবহার করে 1 থেকে 15000000 পর্যন্ত প্রতিটা prime নাম্বার এর জন্য সেই প্রাইম ১ বা তার বেশি বার আছে কতগুলো নাম্বার এর মাঝে, ২ বা তার বেশি বার আছে কতগুলো নাম্বার এর মাঝে, ৩ বা তার বেশি বার আছে কতগুলো নাম্বার এর মাঝে, .........বের করি ।
6. প্রতিটা প্রাইম g এর মাঝে যত বার আছে, তার চেয়ে বেশি বার আছে কতগুলো নাম্বার এর মাঝে, তা বের করি । 
7. যদি কোন প্রাইম g এর মাঝে থাকে x বার, এবং প্রদত্ত n টা নাম্বার এর মাঝে যেসব নাম্বার এর মাঝে ঐ প্রাইম x+1 বা তার বেশি বার আছে এমন নাম্বার থাকে y টা, তবে রিমুভ করতে হবে n-y টা ।
8. যে প্রাইম এর জন্য n-y এর মান সর্বনিম্ন হয়, সেই n-y হবে আউটপুট ।

আজকের মত এই পোস্ট এখানেই শেষ । এই পোস্ট এর ২য় পর্বে implementation নিয়ে আলোচনা করব । ২য় পর্বে আরো থাকবে, আরো বিকল্প কী কী উপায়ে এই প্রোবলেম সলভ করা যায়, কিভাবে এই সলিউশনকে টাইম ও মেমোরি ইফিসিয়েন্ট করা যায় । ফাইনালি থাকবে এই প্রোবলেম এর জন্য আমার accepted সলিউশন ও সলিউশন এর বিভিন্ন অংশের ব্যাখ্যা ।

আমি রিকমেন্ড করব, প্রথমে আপনি সর্বোচ্চ চেস্টা করুন, নিজে ইমপ্লিমেন্ট করতে । না পারলে অপেক্ষা করুন ২য় পর্বের জন্য ।

পোস্টের কোন অংশে বুঝতে সমস্যা হলে বা কোন ভুল চোখে পড়লে, কমেন্ট করুন । 

আমার ব্লগ বা পোস্ট নিয়ে কোন পরামর্শ বা কোন বিষয়ে আপনি পোস্ট চান তা কমেন্টে বলুন । আমি চেস্টা করব সেই বিষয়ে পোস্ট দিতে ।

হ্যাপি কোডিং । আল্লাহ হাফেজ ।।

এই পোস্টের ২য় পর্ব

Read More

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