LightOJ Binary Search Problems

Problem 1:
Points in Segments(LOJ-1088) - Lightoj, Easy

এই সমস্যাই একটা এরে দেয়া থাকবে N সাইজের এবং Q টা এরে কুয়েরি দেয়া থাকবে, প্রত্যেক কুয়েরিতে একটা রেঞ্জ দেয়া থাকবে [A, B], আমাদেরকে বলতে হবে A থেকে B এর মধ্যে কতগুলা সংখ্যা এই এরেতে উপস্থিত আছে।

একটা উদাহরন দিই,

5 1
1 4 6 8 10
1 5
অর্থাৎ ৫ সাইজের একটা এরে দেয়া আছে, এবং ১ টা কুয়েরি দেয়া আছে,
আমাকে বলতে হবে ঐ এরে তে ১ থেকে ৫ এর মধ্যে কইটা সংখ্যা আছে,
আমরা চেইক করলেই দেখবো [১,৫] = [১,৪], অর্থ্যাত দুইটা সংখ্যা আছে, আমাদের কে ২ প্রিন্ট করতে হবে। এইভাবে যতটা কুয়েরি দেয়া থাকবে ততটা এন্সার প্রিন্ট করতে হবে।

লিমিট দেখলেই খুব সহজেই বোঝা যায় আমরা এটা বারবার লুপ চালিয়ে করতে পারবো না, অর্থ্যাত O(N^2) সল্যুশন পাস করবে না ।

আমরা এটা খুব সহজে বাইনারি সার্স দিয়ে করতে পারি যেহেতু এরে টা আগে থেকেই সর্টেড আছে আর আমাদেরকে কিছু একটা খুজতে হবে, প্রত্যেক কুয়েরিতে বাইনারি সার্স করতে টাইম লাগবে O(log(N), আর Q কুয়েরি শেষে কমপ্লেক্সিটি দাঁড়াবে O(Q*log(N)), N এরে সাইজ। এই টাইম খুব সহজে পাস করবে।

যেহেতু আমাদেরকে একটা লিমিট খোজা লাগতেছে, বাইনারি সার্স রিলেটেড দুইটা সেইম কাজের জিনিস আছে, সেটা হইতেছে Upper_bound এন্ড Lower_bound

এই দুইটা জিনিস নিয়ে একটু বলি,

ধরি আমাদেরকে একটা এরে দেয়া আছে, এরে টা সর্টেড, আর একটা সংখ্যা('X') বলা আছে, আমাদেরকে বলতে হবে এক্সাক্টলি কোন নাম্বার টা/ কোন পজিশনে 'X' এর থেকে বড় সংখ্যা আছে, এটা বের করে Upper_bound, আর যদি বলা হয় greater or equal  তাহলে Lower_limit বের করে দেই,

কিভাবে ব্যবহার করতে হয় ?

vector<int>a;
int l = lower_limit(a.begin(), a.end(), 'X') - a.begin(), এরের কোন পজিশনে X এর থেকে বড় অথবা সমান সংখ্যা আছে সেটা বের করবে।

int u = upper_limit(a.begin(), a.end(), 'X') - a.begin(), এরের কোন পজিশনে X এর থেকে বড় সংখ্যা আছে সেটা বের করবে।

এখন আমাদের প্রব্লেমে ফিরে আসি, আশা করি এক্ষণ বোঝা গেছে কিভাবে প্রবলেম টা সলভ করতে হবে । প্রত্যেক কুয়েরিতে দুইটা লিমিটের বিয়োগফল ই হবে আমাদের এন্সার ।

বুঝতে সমস্যা হইলে কোড
 


Problem 2:
Funny Knapsack-(LOJ-1127) - Lightoj, Medium Hard

আশা করি প্রবলেম টা একবার পড়ছো ।
ডাইনামিক প্রোগ্রামিং শুরু করছে আর শুরুতেই এই ব্যাগ ভর্তি করার প্রবলেম সল্ভ করে নাই এমন মানুষ খুব কমই আছে , কিন্তু মজার ব্যাপার হচ্ছে এটা সেই ডাইনামিক প্রোগ্রামিং এর ন্যাপসাক(ব্যাগ ভর্তি) এর প্রবলেম না ।

প্রবলেম টা'তে আসলে কি চাইছে সেটা একটু বলি,
আমাকে একটা ওয়েট(ফিক্সড ওজন) "W" দেওয়া আছে , আর কিছু নাম্বার দেয়া আছে ।
আমাকে বলতে হবে ঠিক কত ভাবে আমরা এই ওয়েটে কিছু(অথবা সব) নাম্বারের সমষ্টি রাখতে পারি, যেনো ওয়েট ওভারফ্লো না হয়ে যায়, অর্থাৎ ভর্তি হয়ে পড়ে না যায় ।
 
প্রবলেম টা বুঝতে সমস্যা হইলে আরো একটু পরে সব ক্লিয়ার হয়ে যাবে, তার আগে বলি এই নাম্বারের সমষ্টি বলতে কি বোঝায় !

ধরি, আমাদের কে কতগুলা নাম্বার দেয়া আছে,  এতভাবে সম্ভব এদের নাম্বারের সমষ্টি বের করতে হবে, উল্লেখ্য আমরা চাইলে সব নাম্বার নিয়ে যোগফল করতে পারি, আবার চাইলে একটাও না নিতে পারি সে ক্ষেত্রে যোগফল শুন্য। এটাকে বলা হয় "অল পসিবল সাবসেট সাম" । সব সাবসেট ইউনিক হতে হবে, এবং একটা সাবসেটে একটা নাম্বার একবারের বেশি থাকবে না ।

উদাহরন সহ দেখি, ধরি আমাদের তিন(৩) সাইজের এরে দেয়া আছে,
A[3] = {1,2,3}, All possible subset sum given below,
বাম পাশের গুলা সাবসেট, ডান পাশের গুলা যোগফল
{} = 0
{1} = 1
{2} = 2
{3} = 3
{1,2} = 3
{1,3} = 4
{2,3} = 5
{1,2,3} = 8

অর্থাৎ, যদি এরের সাইজ N হয়, তাহলে সর্বমোট 2^N টা সাবসেট জেনেরেট করা সম্ভব, এবং সবগুলা সাবসেট ইউনিক, বলে রাখি একটা নাম্বারও  না নেয়া ও একটা সাবসেট, অর্থাৎ ফাকা সাবসেট ও কাউন্ট করতে হবে ।

এখন, প্রব্লেমে ফিরে আসি । আমাদেরকে N সাইজের একটা এবং একটা ওয়েট W দেয়া আছে। W কে আমারা কত ভাবে ভর্তি করতে পারি যেনো W এর থেকে বেশি ওজন হয়ে না যায়। অর্থাৎ W এর থেকে ছোটো যেকোনো যোগফল কে আমরা W তে রাখতে পারবো।

আরো একটা উদাহরন দিয়ে প্রবলেম বোঝার পর্ব শেষ করি ।

A[3]={1,2,4} and W = 10
{0} = 0
{1} = 1
{2} = 2
{4} = 4
{1,2} = 3
{1,4} = 5
{2,4} = 6
{1,2,4} = 7

এই আটভাবে আমরা আমাদের ১০ ওজনের পাত্র টা ভর্তি করতে পারি, খেয়াল করি কোনোও যোগফল ই ১০ এর থেকে বেশি না ।


এপ্রোচ ঃ
এতক্ষনে হইতো ধারনা হয়ে গেছে, আমরা নাম্বারের সাবসেট সাম বের করবো, আর যেই সাম গুলা W এর থেকে ছোটো পাবো, আমাদের Answer বাড়াইতে থাকবো ।

আচ্ছা তাহলে দেখি, এইভাবে আসলে সম্ভব কিনা ।

N এর মান সর্বোচ্চ 30 হইতে পারে, অর্থাৎ 2^N টা সাবসেট পসিবল ।
সুতরাং 2^30 = 1073741824, এটা খুব সহজেই অনুধাবন যোগ্য যে আমরা নরমাল টাইমে কখন ই এত বড় ক্যালকুলেশন করতে পারবো না ।

তাহলে আমাদের এই সোজাসাপ্টা এপ্রোচ টা ব্যর্থ হইলো ।

তাহলে এখন নতুন আরেকটা প্রবলেম নিয়ে আলোচনা করবো পাশাপাশি নতুন একটা এপ্রোচ ও আলোচনা করা হয়ে যাবে।
ধরি আমাদেরকে একটা এরে দেয়া আছে আর একটা টারগেট ভ্যালু দেয়া আছে, আমাদেরকে বলতে হবে কত ভাবে দুইটা ভিন্ন সংখ্যা যোগ করে আমরা টারগেট ভ্যালু বানাইতে পারি , একটু চিন্তা করলে খুব সহজেই আমরা প্রব্লেম টা সলভ করতে পারি। নাম্বার গুলা একটা ম্যাপে মার্ক করে রেখে প্রত্যেকবার আমরা টারগেট থেকে কারেন্ট ভ্যালু বিয়োগ করে ম্যাপে খুজে দেখতে পারি যে (টারগেট - কারেন্ট) ভ্যালু টা আছে কিনা, থাকলেই এন্সার ইনক্রিমেন্ট করবো। আশা করি বোঝা গেছে, কিভাবে এটা সল্ভ করা যায়।

এখন আসি কেনো আমি এটা আলোচনা করলাম, আমাদেকে ম্যাক্সিমাম ত্রিশ(৩০) লেন্থ এর এরে দেয়া থাকবে, আমরা যদি কোনোভাবে এটাকে দুইটা এরেতে ভাগ করে, তাদের আলাদা সাবসেট বের করে তারপর যেকোনো একটা সাবসেট এরেকে ঐযে ম্যাপের মত চিন্তা করতে পারি, তাহলে আমাদের প্রবলেম টা ৯০% সলভ হয়ে যায়, বাকি ১০% হচ্ছে কিভাবে আমরা আলাদা দুইটা সাবসেট বানাইতে পারি, ম্যাপের মত করে খুজতে পারি, সেটা ইমপ্লিমেন্ট করার মধ্যে ডিপেন্ড করতেছে ।

এখন দুইটা এরে তে ভাগ করলে কেমন হয় দেখি, ম্যাক্সিমাম লেন্থ ৩০, এটাকে দুইভাগ করলে ১৫, ১৫ লেন্থ এর সাবসেট সাম ২^১৫ = ৩২৭৬৮, বাহ! খুব সহজেই আমরা লুপ চালিয়ে অথবা রিকার্সন এর মাধ্যমে সল্ভ করতে পারবো।
তাহলে এই প্রবলেম টা সল্ভ করার জন্য পর্যায়ক্রমিক স্টেপ গুলা দেখি ।
১।দুইটা নতুন এরেতে নাম্বারগুলোকে রাখা।
২।দুইটা নতুন এরেতে এদের সাবসেট সাম রাখা।
৩।যেকোনো একটা সাবসেট সাম এরেকে সর্ট করে ম্যাপের মত করে চিন্তা করা।
৪।ম্যাপের মত করে খোজার জন্য বাইনারি সার্চ অথবা আপার বাউন্ড(Binary search or Upper_Bound) ব্যবহার করা।

৪ নম্বর টা কি বললাম ? ধরো আমাদেরকে ১০ খোজা লাগবে এখন আপার বাউন্ডের মাধ্যমে কতগুলা সংখ্যা নিলে আমাদের ১০ বানানো যাবে সেটা জানা যাবে, কারন এটা আমাদেরকে রিটার্ন করবে এক্সাক্টলি গ্রেটার ভ্যালুর পজিশন, আর যতটা পজিশন রিটার্ন করবে, ততগলা কম্বিনেশন পসিবল ।

এখনও বুঝতে সমস্যা হইলে খাতা কলমে একটু ঘাটাঘাটি করলেই সব ক্লিয়ার হয়ে যাবে, সাথে সাথে সুন্দর মত ভিজুয়ালাইজ ও করা যাবে।

কমপ্লেক্সিটি?
সাবসেট জেনেরেট করতে, O(2^N/2)
আপার বাউন্ড, O(log(2^N/2) 
তাহলে অভারল কমপ্লেক্সিটি দাড়ালো, O(2^(N/2)*log(2^N/2))
 

একদম সহজ কোড

Problem 3:
Coin Change(IV)-(LOJ-1235) - Lightoj, Medium

আগের প্রবলেম টা ভালোমত বুঝতে পারলে এই প্রবলেম টা একদম সহজ । এখানে N এর সর্বোচ্চ মান 18 হইতে পারে এবং আরো বলা আছে আমরা চাইলে যেকোনো ইলিমেন্ট দুইবার নিতে পারি। অর্থ্যাত N এর মান সর্বোচ্চ 18*2 = 36 হইতে পারে ।
তাহলে আমরা ইচ্ছা করলেই সব সাবসেট সাম জেনেরেট করতে পারবো না ।

আমরা প্রবলেম টাকে আগের মত দুইভাগ করে ফেলবো, এবং একই সাথে প্রত্যেক ইলিমেন্ট এক বা দুইবার নিয়ে অল পসিবল সাবসেট সাম বের করবো ।

এটা আমরা করতে পারি রিকার্সন এর মাধ্যমে, আমাদের বেইজ কেস হবে এরের সর্বশেষে পৌছাই গেলে আমরা সাবসেট এ সাম রেখে দিবো, আমাদের অপারেশন হবে তিনটা,
১। শূন্য বার নিবো, অর্থ্যাত নিবো না
২। একবার নিবো
৩।দুইবার নিবো ( বলা আছে, আমরা চাইলেই একটা ইলিমেন্ট দুইবার নিতে পারি)

এই ধরনের প্রবলেম কে বলা হয়া মিট ইন দ্যা মিডল(Meet In The Middle) প্রবলেম ।

এর পর ঠিক আগের মতই একটা এরেকে সর্ট করে, ঐটার মধ্যে বাইনারি সার্স চালাইলেই আমাদের সমাধান পেয়ে যাবো ।

সি++ এর STL এর আপার, লোয়ার বাউইন্ডের মত Binary_Search ও আছে ।
ডিফাইন করতে হয় কিভাবে ?
Vector<int>A;
bool check = binary_search(A.begin(), A.end(), 'X');

এখানে আমরা A ভেক্টরের মধ্যে বাইনারি সার্স করে দেখছি 'X' ইলিমেন্ট আছে কিনা, যদি থাকে তাহলে check, True return করবে, না থাকলে False রিটার্ন করবে ।

খাতা কলমে কয়েকটা ছোটো কেইস নিয়ে ঘাটাঘাটি করলে খুব সহজে ভিজুয়ালাইজ করা যাবে, এটা পড়ার পর আশা করি সবাই এটা ইমপ্লিমেন্ট করতে পারবে ।

না বুঝতে পারলে, সহজ কোড


Problem 4:
Very Lucky Numbers-(LOJ-1276) - Lightoj, Medium Hard

এই প্রবলেম টা ভালো মত পড়লেই বোঝা যাবে এটা ঠিক প্রবলেম ১ এর মত কিছুটা মিল আছে । এখানেও আমাদেরকে রেঞ্জ নিয়ে কাজ করতে হবে।

প্রবলেমে দুই ধরনের নাম্বারের কথা বলা আছে,
১। লাকি নাম্বার - যেসকল নাম্বারের ডিজিট শুধু মাত্র ৪ এবং ৭ দ্বারা গঠিত। যেমন - ৪,৭,৪৪,৭৭,৪৪৭ ইত্যাদি।
২। ভেরি লাকি নাম্বার - যেসকল নাম্বার কয়েক লাকি নাম্বারের গুনফল থেকে পাওয়া যায়। যেমন- ১৬,২৮,৪৪,৪৭।

উল্লেখ্য লাকি নাম্বার ও ভেরি লাকি নাম্বারের অন্তর্ভুক্ত।

আমাদেরকে দুইটা নাম্বার (A, B) দেয়া থাকবে, আমাদেরকে বলতে হবে A থেকে B এর মধ্যে কতগুলা ভেরি লাকি নাম্বার আছে।

এখন নিশ্চয় বোঝা গেছে কেনো এটা প্রবলেম এর সাথে মিল আছে।

এপ্রোচঃ
এটা একদম সোজা সাপটা একট প্রবলেম, আমাদের কাজ শুধু আগে থেকে ভেরি লাকি নাম্বার জেনেরেট করা। কিন্তু জিনিস টা একটু জটিল ও বটে।

আমরা চাইলেই একই সাথে লাকি এবং ভেরি লাকি নাম্বার জেনেরেট করতে পারবো না। প্রথমে আমাদেরকে লাকি নাম্বার জেনেরেট করতে হবে, এর পর তাদেরকে বিভিন্ন ভাবে গুন করে নতুন ভেরি লাকি নাম্বার জেনেরেট করতে হবে ।

এখন আসি কিভাবে আমরা লাকি নাম্বার জেনেরেট করতে পারি, খুব সহজ রিকার্সন এর মাধ্যমে এটা করতে পারি।

বেইজ কেস ? আমাদেরকে লিমিট বলে দেয়া আছে 10^12, অর্থ্যাত এর থেকে বড় নাম্বার হইলে সরাসরি রিটার্ন করে দিবো।
অপারেশন ? দুই ধরনের ডিজিট দিয়ে লাকি নাম্বার গঠিত ৪, ৭ । অর্থাৎ ৪ দিয়ে এবং ৭ দিয়ে আমরা লাকি নাম্বার জেনেরেট করবো, এইভাবে
Lucky(10*n+4),Lucky(10*n+7)

ধরলাম, Lucky একটা ফাংশন , প্রথমে আমরা জিরো(০) দিয়ে ফাংশন স্টার্ট করবো, 10*0+4 = 4, নতুন একটা Vector এর মধ্যে ৪ রেখে দিবো, ঠিক এইভাবে বাকি গুলাও জেনেরেট হবে।

ভেরি লাকি নাম্বার জেনেরেট করার জন্য আমরা আরেকটা ফাংশন বানাবো, যার মধ্যে প্রত্যেক বার একটা একটা করে লাকি নাম্বার নিয়ে তাদের অল পসিবল মাল্টিপ্লিকেশন রেখে দিবো।

এর পর সব জেনেরেটেড নাম্বার গুলাকে ইউনিক করবো, যাতে কোনো ডুপ্লিকেট ভ্যালু না থাকে। 

বাকিটা তো বোঝা হয়ে গেছে শুরুতেই, আপার এবং লোয়ার লিমিট দিয়ে কত গুলা সংখ্যা আছে বের করে ফেলবো।

এখোনো বুঝতে না পারলে সহজ কোড