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 এর সব ফাইল দেখে ফেলতে পারবে।