TC SRM 169 Div-2 1000 (Using Binary Search)

বাইনারি সার্চ শিখতে গিয়ে টপকোডার এর একটা প্রব্লেম সল্ভ করলাম। SRM 169 এর Division 2 এর 1000 নম্বরের জন্য থাকা প্রব্লেমটা (Link: http://goo.gl/kH5Dbm)। প্রব্লেমটা আমার ভাষায় এরকমঃ

একটা ঘরে কিছু আলমারি রাখা আছে। প্রতিটা আলমারিতে কতগুলো ফাইল রাখা আছে। ফাবিয়ানের কাজ এর মধ্যে একটা ফাইল খুঁজে বের করা। এই কাজ করানোর জন্য তার কাছে কিছু (workers সংখ্যক) কর্মী আছে। প্রতিটা কর্মীর কাজ আবার ভাগ করা। প্রতিটা কর্মী একটা বা পাশাপাশি রাখা একাধিকটা আলমারিতে খুঁজতে পারে। তার মানে কোন কর্মী যদি ১ম আলমারিতে খোঁজার দায়িত্বে থাকে তবে হয় সে খালি ১মটাতেই খুঁজবে অথবা এর পাশের আর কয়েকটাতে খুঁজবে। কিন্তু কোনটা বাদ দিয়ে তার পরের কোনোটায় খুঁজতে পারবেনা। একটানা কিছু আলমারিতে খুঁজতে পারবে।

একেক আলমারিতে একেক সংখ্যক ফাইল রাখা। ফাবিয়ান বৈষম্য পছন্দ করেনা। তাই সে চায় এমন ভাবে কর্মীদের কাজ ভাগ করে দিতে যাতে কারো ভাগেই খুব বেশী ফাইল না পরে। যদি একজন কর্মীকে সর্বোচ্য MAX সংখ্যক ফাইলে খুঁজতে হয় তবে ফাবিয়ান চেষ্টা করবে MAX এর মান যত পারে কমাতে।

মনে করি মোট আলমারি ৯ টা। আলমারিগুলোতে ফাইল আছে যথাক্রমেঃ

১০, ২০, ৩০, ৪০, ৫০, ৬০, ৭০, ৮০, ৯০ টি করে।

হাতে কর্মী ৫ জন।

তো আমরা কিভাবে সাজালে কাউকেই বেশী ফাইল ঘাঁটতে হবেনা?

১০, ২০, ৩০, ৪০ । ৫০, ৬০ । ৭০ । ৮০ । ৯০ এভাবে সাজানো যেতে পারে। মানে প্রথমজন প্রথম ৪ টি আলমারিতে খুঁজবে, ২য় জন তার পরের দুইটাতে খুঁজবে আর ৩য়, ৪র্থ আর ৫ম জন যথাক্রমে ৭, ৮ আর ৯ নম্বর আলমারিতে খুঁজবে। এতে করে শুধু দ্বিতীয় জনকে কষ্ট করে ১১০ টা ফাইল ঘাঁটতে হোল। কারো এর বেশী দেখা লাগলো না। সুতরাং MAX এর মান এখানে ১১০।

এইযে আমরা পার্টিশন গুলো দিলাম একেক কর্মীর মোট ফাইল সংখ্যা ভাগ করতে, এই কাজটা কিভাবে করা যায়?

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

এর পরে ধরি আমার কর্মী সংখ্যা একজন। তাহলে তো তাকেই সব আলমারি অর্থাৎ ফাইল দেখতে হবে। এর মানে MAX এর সর্বোচ্য মান হবে সব আলমারিতে রাখা মোট ফাইল সংখ্যা।

তার মানে আমরা MAX এর সম্ভাব্য সর্বনিম্ন আর সর্বোচ্য মান পেলাম। এবার আমরা এই ২ মানের মধ্যে বাইনারি সার্চ চালিয়ে বের করে ফেলতে পারি যে MAX এর মান সবচেয়ে কম কত হলে workers সংখ্যক কর্মী সব আলমারির ফাইল দেখে ফেলতে পারবে।

আমরা কোডটা দেখিঃ

 ****

এখানে যা হচ্ছে তা হল আমরা lo আর hi এর মধ্যে একটা median বের করছি। এরপর দেখছি সেই mid টাকে MAX ধরে থাকলে কয়টা কর্মী যথেষ্ট, সব ফাইল দেখতে।

যদি দেখি এতে আমাদের হাতে থাকা কর্মী থেকেও কম বা সমান লাগছে তবে MAX এর মানটা কমিয়ে দেখতে পারব। কারণ লোক যত কম লাগে তত একজনের কাজ বেশী হয়। আমাদের তো লোক Limit এর মধ্যেই আছে। তাই কাজ কমিয়ে দেখি। তাহলে hi এর মান হয়ে যাবে mid এর সমান। কারণ একেকজনের কাজ mid পরিমান হলেই লোক বেশী লাগছেনা। কাজ আরো বাড়ানোর তো দরকারই নেই।

ঠিক উল্টোভাবে যখন দেখব workers এর চেয়ে লোক বেশী দরকার হয়ে গেছে তখন আমরা কাজের পরিমান অর্থাৎ ফাইলের পরিমান বাড়িয়ে দেখব। মানে একেকজনকে এখন বেশী কাজ করতে হবে। তা হবে mid এর বেশী। কারণ mid বা তার কম কাজ একেকজন করলে তো আরও লোক বেশী লাগছে।

এই পদ্ধতিতে করলেই আমরা জেনে যাব MAX এর সর্বনিম্ন কোন মানের জন্য workers সংখ্যক কর্মী folders এর সব ফাইল দেখে ফেলতে পারবে।

প্রাইম নিয়ে যত কথা – ১

নাম্বার থিওরির গুরুত্বপূর্ণ একটি টপিক হল প্রাইম নাম্বার বা মৌলিক সংখ্যা। আজ প্রাইম নাম্বার বা মৌলিক সংখ্যার উপর কিছু বেসিক আলোচনা করবো আমরা। আচ্ছা তাহলে আগে জানা যাক মৌলিক সংখ্যা কি? যেসব সংখ্যাকে ওই সংখ্যা এবং ১ ছাড়া আর কোন সংখ্যা দিয়ে ভাগ করা যায়না সেগুলোই মৌলিক সংখ্যা। যেমন ঃ ২ , ৩ , ৫ ইত্যাদি। আজ আমরা দেখবো কিভাবে সহজেই আমরা একটি সংখ্যা প্রাইম কিনা তা বের করার কোড। এরপর দেখবো কিভাবে একটি সংখ্যার প্রাইম ফ্যাক্টরাইজেশন করা যায়।

আমরা যেহেতু ইতিমধ্যে জেনে গেছি যে প্রাইম কিভাবে বুঝতে হয় তাহলে আমরা বলতে পারি যে কোন সংখ্যা N প্রাইম কিনা তা জানার জন্য ২ থেকে N-১ পর্যন্ত সংখ্যা দিয়ে ভাগ করে যদি দেখি যে N কে ভাগ করা যাচ্ছেনা তাহলেই ধরে নেব সংখ্যাটি প্রাইম।

তাহলে কোডে দেখি প্রসেসটা।

আমরা একটি বুলিয়ান ভ্যারিয়াবল এ প্রথমে true নিয়ে নিচ্ছি। যদি প্রাইম চেক করার সময় দেখি যে N কোন সংখ্যা দ্বারা বিভাজ্য তাহলে তা false করে দিব। তারপর এর মানের উপর নির্ভর করে বুঝবো প্রাইম নাকি প্রাইম না। খুবই সোজা কোড।

এখন আমাদের শুধু কোড করলেই হবেনা। কোড কি Efficient কিনা তাও দেখতে হবে। খেয়াল করে দেখি আমরা প্রাইম বাদে কোন সংখ্যাকে সর্বনিম্ন দুই ভাগে ভাগ করতে পারি। জোড় সংখ্যা গুলো কে। তার মানে আমরা যে সংখ্যাই নেই না কেন তার অর্ধেক থেকে বড় সংখ্যা ( < N) ওই সংখ্যা কে ভাগ করতে পারবেনা। যেমন ঃ ধরা যাক ১০। এর অর্ধেক হল ৫। আমরা খেয়াল করলেই দেখবো ৬ ৭ ৮ ৯ এগুলো ১০ এর ভাজক না। তাহলে আমরা কোড এ একটু পরিবর্তন আনি।

আমরা তাহলে আগের থেকে Efficient একটা কোড পেলাম। আচ্ছা এর থেকেও কি Efficient কোড করা যায়? এই প্রশ্নের উত্তর একটু পরে খুঁজি । তার আগে আরেকটা ব্যাপার দেখি আমরা।

১০০ = ১ * ১০০

     ২ * ৫০

     ৪ * ২৫

৫ * ২০

১০ * ১০

এখানে আমরা ১০০ এর Divisor গুলো বের করলাম। আমরা যদি জোড়া করি Divisor গুলোর তাহলে দেখবো ১ , ২ , ৪ , ৫ , ১০ এই সংখ্যাগুলো দিয়ে ১০০ কে ভাগ করলে আমরা ১০০ , ৫০ , ২৫ , ২০ , ১০ এগুলো পেয়ে যাচ্ছি। মজার ব্যাপার। তাহলে আমি সর্বনিম্ন কোন সংখ্যা পর্যন্ত চেক করলে সবগুলো Divisor পেয়ে যাচ্ছি ? ১০ পর্যন্ত। লক্ষ্য করলেই দেখবো যে ১০ ১০০ এর বর্গমূলের সমান। আমরা চাইলে অন্যান্য সংখ্যা দিয়েও চেক করে দেখতে পারি। প্রতিবারই আমরা দেখবো যে আমরা কোন সংখ্যার বর্গমূলের ভেতর চেক করলেই সবগুলো Divisor বের করতে পারব। তাহলে আমরা আমাদের আগের প্রশ্নের উত্তর পেয়ে গেলাম।আমরা কোন সংখ্যার Square Root পর্যন্ত লুপ চালালেই বের করতে পারবো সংখ্যাটি প্রাইম কিনা। এবার কোডে আসি।

যাক, এতক্ষণে আমরা অনেক Efficient একটা কোড পেলাম। এভাবেই তাহলে আমরা কোন সংখ্যা প্রাইম কিনা তা বের করতে পারবো।

এখন আমরা জানবো কিভাবে একটা সংখ্যার প্রাইম ফ্যাক্টর গুলো প্রিন্ট করতে হয়। একটি সংখ্যা নেই। ধরলাম ৩৬০। এর প্রাইম ফ্যাক্টরগুলো হল ২ ২ ২ ৩ ৩ ৫। অর্থাৎ এই প্রাইম গুলো গুন করলে আমরা ৩৬০ পাবো। এখন আমরা কিভাবে প্রিন্ট এর কাজ টা করব? আমরা আগের মতই সংখ্যার Square Root পর্যন্ত লুপ চালাবো আর Divisor পেলেই সেটাকে ওই সংখ্যা থেকে বাদ দিয়ে দিব। কোডে দেখি ব্যাপার টা।

কোড দেখে ঘাবড়ানোর কিছু নেই। ধীরে ধীরে আমরা দেখি কোডের প্রসেস। আমরা আমাদের প্ল্যান অনুযায়ী Square Root পর্যন্ত লুপ চালালাম। তারপর যদি কোন Divisor পাই তাহলে চেক এর ভেতরের While লুপ এর মাধ্যমে আমরা ওই সংখ্যা থেকে Divisor টা সম্পূর্ণভাবে বাদ দিয়ে দিচ্ছি আর প্রিন্ট করতেসি প্রতিবার। এখন এই কোড দেখে অনেক প্রশ্নই মনে জাগবে। আমরা যে Divisor বাদ দিচ্ছি তা যে Prime Divisor / Factor তার গ্যারান্টি কি? বা কোড এর শেষে আমরা যে অতিরিক্ত ( N > 1 ) এর চেক দিলাম তার দরকারই বা কি?

প্রথম প্রশ্নের উত্তরে আসি। যদি সংখ্যাটি জোড় হয় তাহলে তার Divisor গুলোর মাঝে ২ অবশ্যই থাকবে। আমরা যদি সবগুলো ২ কেই বাদ দিয়ে দেই তাহলে নতুন করে আর কোন জোড় Divisor পাওয়ার সম্ভাবনা রইলনা। বাকি রইল বিজোড় Divisor গুলো। যদি ৩ থাকে তাহলে ৩ বাদ দেয়ার সময় ৩ এর গুণিতক থাকলে এগুলোও বাদ পরে যাচ্ছে। তাই পরবর্তীতে লুপ এ আমরা ৩ এর কোন গুণিতক কে Divisor হিসেবে পাবোনা। তাহলে বোঝাই যাচ্ছে যে আমরা লুপ এর কন্ডিশন অনুযায়ী শুধু প্রাইম সংখ্যাগুলো কে Factor / Divisor হিসেবে পাচ্ছি।

এবার দ্বিতীয় প্রশ্ন এর উত্তর। আমরা কোড থেকে এটুকু অবশ্যই বুঝতে পারছি যে N কে ভাগ করার পর N ছোট হয়ে যাচ্ছে। তার ফলে আমাদের বাইরের লুপটার কন্ডিশন ও ছোট হচ্ছে। তাহলে এমন একটা পর্যায় আসবে যখন দুইটা প্রাইম গুন আকারে থাকবে। অথবা একটা প্রাইম থেকে যাবে। ধরি P1 আর P2 দুইটা প্রাইম সংখ্যা (P1 <= P2)। এখন এদের গুনফলের Square root যদি আমরা বের করি তাহলে (P1 <= Square root(P1,P2) <= P2) হবে। লুপের কন্ডিশন অনুযায়ী P1 আমরা বাদ দিয়ে দিব। এখন P2 এর কি হবে ? এর Square root তো এর থেকে ছোট। তাই এইটা চেক হওয়ার আগেই লুপ Terminate হয়ে যাচ্ছে। তাই আমরা অতিরিক্ত একটি চেক দিলাম যে N ১ এর চেয়ে বড় থাকলে সেটাও আমরা প্রিন্ট করে দিব।

আজ তাহলে এ পর্যন্তই। এর পরের টিউটোরিয়াল এ আমরা দেখবো কিভাবে ১০^৭ পর্যন্ত প্রাইম সংখ্যা সহজেই বের করা যায়।

Euler's Totient or phi function φ(n)

phi ফাংশন কি?

phi ফাংশন একটি arithmetic function যেটি count করে একটি সংখ্যা N এর সমান বা ছোট কতটি ধনাত্মক সংখ্যা আছে যেগুলো N এর relative prime. অর্থাৎ 1 থেকে শুরু করে N পর্যন্ত মোট কতটি সংখ্যা আছে যেগুলোর সাথে N এর 1 বাদে অন্য কোন common divisor নেই, আরেকটু সহজ করে বলতে গেলে যাদের সাথে N এর GCD = 1. উদাহরন দিলেই ব্যাপারটা আরও পরিষ্কার হবে।

8(eight) সংখ্যাটিকে ধরি, এর সমান ও ছোট ধনাত্মক সংখ্যাগুলো হল,
1 2 3 4 5 6 7 8
এর মধ্যে থেকে 8 এর সাথে common divisor আছে এমন সংখ্যাগুলোকে বাদ দেই,
1 2 3 4 5 6 7 8
তাহলে 4 টি সংখ্যা অবশিষ্ট থাকে 1 3 5 7. অর্থাৎ φ(8) = 4.

আবার 15 সংখ্যাটি বিবেচনা করি,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
অবশিষ্ট থাকে 8 টি সংখ্যা – 1, 2, 4, 7, 8, 11, 13, 14
অর্থাৎ φ(15) = 8.

এখন চিন্তা করি prime number এর ক্ষেত্রে phi function এর চেহারা কেমন হবে। উত্তরটা খুব সহজ। কোন একটি সংখ্যা prime এর মানেই হল সংখ্যাটির 1 বাদে অন্য কোন divisor নেই যেটি সংখ্যাটি থেকে ছোট।
সুতরাং φ(prime) = prime-1.

7 সংখ্যাটি একটি prime number. তাহলে 7 এর জন্য,
1 2 3 4 5 6 7

so, φ(7) = 7-1
so, φ(prime) = prime-1

Some Properties

phi ফাংশনের কাজ করার মত algorithm লিখতে হলে আমাদেরকে এর কয়েকটি basic properties সম্পর্কে জানতে হবে।

1. প্রথমটি উপরেই বর্ণিত। φ(prime) = prime-1.

2. ধরি P একটি prime নাম্বার। P এর যেকোনো পাওয়ার a হলে,

3. অত্যন্ত গুরুত্বপূর্ণ। ফাংশনটি একটি multiplicative ফাংশন। ব্যাখ্যা করি।
ধরি a এবং b দুইটি relative prime number অর্থাৎ এদের মধ্যে 1 ব্যাতিত কোন common divisor নেই। তাহলে a*b এর জন্য ফাংশনটির চেহারা হবে,

Building an Algorithm

উপরের properties গুলোকে ব্যাবহার করে যেকোনো নাম্বারের phi function value বের করার মত পদ্ধতি বের করা যাক। প্রথমেই একটুখানি গনিত প্রয়োজন।

আমরা যেই নাম্বারটির phi function value বের করব সেটিকে তার prime factor এ ভেঙ্গে ফেলব। এটাই আমাদের algorithom এর ভিত্তি হবে।

ধরি একটি নাম্বার n. একে prime factor এ ভেঙ্গে লিখলে হবে,

এখানে n এর factor এর সংখ্যা k টি। এবং P একটি factor হলে a তার পাওয়ার। তাহলে,

এই শেষের লাইনটাই আমাদের দরকার।

আমরা লুপ চালিয়ে একটা একটা করে n এর prime factor গুলা (P1, P2, P3, ……, Pk) নিব এবং প্রত্যেকবার একটা অপারেশন করব। কি করব বলি, সুবিধার জন্য ধরি n এর factor এর সংখ্যা দুইটি। তাহলে,

এই অবশিষ্ট another_something ই হবে আমাদের রেজাল্ট।

অর্থাৎ আমরা একটা variable এ প্রথমে n এর value টা রাখব। ধরি variable টার নাম result। তারপর একটা একটা করে factor P ধরব এবং result কে P দিয়ে ভাগ করে ভাগফলটাকে result থেকে বাদ দিব। এভাবে ক্রমাগত factor গুলা দিয়ে ভাগ এবং বিয়োগ করতে থাকলে result এর ভ্যালু কমতে থাকবে। সবশেষে যা পড়ে থাকবে তাই আমাদের φ(n).

বিশেষ দ্রষ্টব্যঃ prime factor কিভাবে বের করতে হয় সেটা না জানলে পরের code টুকু বুঝতে কষ্ট হবে। সেক্ষেত্রে prime factor বের করাটা আগে শিখে নেওয়া ভাল। এটাই এই অ্যালগরিদমের ভিত্তি।

A possible C++ Implementation

Some UVA Problems

Happy coding.

Md. Fahim Mohiuddin Dhrubo
11 October 2014