Aggressive Cows | Binary Search Problem

Aggressive Cows - Spoj

সহজ এবং সুন্দর প্রবলেম ডেসক্রিপশন

N টা পজিশন দেয়া আছে আর C গরু দেয়া আছে। এই পজিশন গুলাতে এমন ভাবে এই গরু গুলাকে বসাইতে হবে যেনো যেটা মিনিমাম ডিস্টেন্স ঐটা যেনো ম্যাক্সিমাম হয়।
আরো সুন্দর ভাবে বোঝায়,

ধরি আমাদের পজিশন দেয়া আছে, [1, 2, 4, 8, 9] এইখানে আমাদের কে 3 টা গরুকে বসাইতে হবে।

1	2	4	8	9	Min Distance
C1	C2	C3			2-1 = 1
C1	C2		C3		2-1 = 1
C1	C2			C3	2-1 = 1
C1		C2	C3		4-1 = 3
C1		C2		C3	4-1 = 3
	C1	C2	C3		4-2 = 2
	C1		C2	C3	9-8 = 1

এইখানে আমরা ৩ টা গরুকে ৫ টা পজিশনে বিভিন্ন ভাবে বসানোর চেষ্টা করেছি । ছয় নাম্বার কলামে আমরা ছোটো একটা হিসাব করেছি, মিনিমাম ডিস্টেন্স অর্থ্যাত যেকোনো দুইটা গরুর পজিশনের মিনিমাম দুরুত্ব। এখন সব গুলা মিনিমাম ডিস্টেন্স এর দিকে খেয়াল করলে দেখা যাবে 3 হচ্ছে আমাদের ম্যাক্সিমাম নাম্বার। এটাই আমাদের কাঙ্ক্ষিত উত্তর।

সুতরাং আমাদেরকে C টা গরুকে N টা পজিশনে এমনভাবে বসাইতে হবে যেনো তাদের মিনিমাম দুরত্ব টা ম্যাক্সিমাম হয়, আর সেই ম্যাক্সিমাম টাই আমাদের উত্তর।




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


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

যদি আমরা একটু সুন্দর মত চিন্তা করি তাহলে বুঝতে পারবো এন্সার কখনোও প্রথম পজিশন ও শেষ পজিশনের যোগফলের বেশি হবে না। উপরের উদাহরন থেকে শর্ট করার পরে প্রথম পজিশন ১ এবং শেষ পজিশন ৯ , এদের যোগফল ১০ । আমরা কোনো ভাবে ই ১০ এর বেশি উত্তর করতে পারবো না।

এতক্ষনে হইতো বোঝা হয়ে গেছে, আমরা এখানে বাইনারি সার্চ এপ্লাই করবো, কিন্তু কথা হচ্ছে আমরা কিসের উপর বাইনারি সার্চ এপ্লাই করবো ? পজিশন গুলার উপর নাকি গরু গুলার উপর ?

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

আচ্ছা এতক্ষন বুঝলাম আমরা কোথায় বাইনারি সার্চ এপ্লাই করবো, এখন প্রশ্ন হচ্ছে উত্তরের উপর বাইনারি সার্চ এপ্লাই করে আমরা করবো টা কি ? আর কেনই বা আমরা এমন টা করতেছি ?

ধরি আমরা বাইনারি সার্চ কিভাবে কাজ করে সেটা আগে থেকেই জানি, এইখানে আমরা প্রত্যেকবার একটা মিডিল পজিশন হিসাব করি, এরপর ঐ মিডিল পজিশনের উপর ভিত্তি করে আমরা চেইক করি আমাদেরকে লেইফ সাইডে যাইতে হবে নাকি রাইট সাইডে যাইতে  হবে।

এই প্রবলেম এর ক্ষেত্রেও জিনিস টা সেইম, আমরা উত্তরের উপর বাইনারি সার্চ এপ্লাই করে মিডিল বের করবো আর চেইক করবো এই মিডিল কে গ্যাপ রেখে আমরা আমাদের গরু গুলাকে পজিশনে বসাইতে পারি কিনা।

তাহলে সল্যুশন সামারি কি দাড়াইলো ?

আমরা একটা রেঞ্জ ধরে নিবো, যেই রেঞ্জ এর মধ্যেই আমাদের উত্তর থাকবে, এর পর একে একে আমরা আমাদের রেঞ্জ এর ভ্যালু গুলা চেইক করবো, তাদেরকে গ্যাপ হিসেবে গরুগুলার  মাঝে ব্যবহার করা যাইকিনা, এই ভাবে আমরা আমাদের মিনিমাম গ্যাপ টা পেয়ে যাবো, যেটা কিনা সব গুলা কম্বিনেশন এর মধ্যে ম্যক্সিমাম।

তাহলে আমাদের টাইম কমপ্লেক্সিটি কি দাড়াইলো ?

আমারা বাইনারি সার্চ করতেছি, এটার জন্য log(N)
একই সাথে প্রত্যেকবার আমরা গ্যাপ চেইক করতেছি ঐটাকে ব্যাবহার করা যাবে কিনা, এটার জন্য O(N)

তাহলে ওভারওল কমপ্লেক্সিটি দাড়াইলো O(NlogN)
N এর রেঞ্জ সর্বোচ্চ 100,000 হইতে পারে, যেটা ইজিলি পাস করবে।


বুঝতে না পারলে কোড