Bappy's Blog

যদি a^b = x হয়, তবে a^x = b  এবং b^x = a হবে।  খাতায় কয়েকটি সংখ্যা নিয়ে হিসেব করে দেখতে পারো। এবার বিষয়টি বুঝতে পারলে ঝটপট এই  প্রব্লেম  টি সলভ করে ফেলো। 

Topics of this problem: Binary Search + Greedy ১) এই প্রব্লেমে আমরা শুরুতে একটা ফাংশন বানাবো যার কাজ হবে একটা ভ্যালু প্যারামিটার হিসেবে নিয়ে দেখা যে প্রত্যেক লেখক কে দিয়ে সর্বোচ্চ এতোগুলো পেইজ লিখালে K সংখ্যক লেখক m টি বই লিখে শেষ করতে পারবে কি না। যদি পারে তাহলে True রিটার্ন করবে নাহয় False  রিটার্ন করবে। ২) এরপর বাইনারী সার্চের কাজ করবো। বাইনারী সার্চের Low হবে ১টি বইয়ে সর্বোচ্চ যতগুলো পেইজ আছে ততো। High হবে 5e9 । এবার বাইনারী সার্চের মাধ্যমে বের করবো সর্বনিম্ন কোন ভ্যালুর জন্য Valid ফাংশন True রিটার্ন করে। প্রত্যেক লেখক কে দিয়ে সর্বোচ্চ ততোগুলো পেইজ লিখানো যাবে। ৩) সলুশ্যন এর বাকি অংশ গ্রীডি পার্ট। এবার শেষ বই থেকে শুরু করে প্রথম বই পর্যন্ত লুপ চালিয়ে দেখবো ১ জন লেখক কে সিকুয়েন্সিয়ালি সর্বোচ্চ যতো পেইজ লিখতে দেয়া যায়। শেষ থেকে লুপ চালাবো এজন্য যাতে করে ১ম দিকের লেখক দের কে যতো সম্ভব কম সংখ্যক পেইজ লিখতে দেয়া যায় যেভাবে প্রব্লেমে বলা আছে।  

একটি 2D গ্রিডে এক পজিশন থেকে অন্য পজিশনের ক্ষুদ্রতম দূরত্ব বের করতে হবে যখন বর্তমান পজিশন থেকে সম্ভাব্য সকল দিকে(৮ দিকে) মুভ দেয়া যায়। এমন প্রব্লেম দেখলে অনেকেই এক দেখাতে সল্যুশন বলে দিবে যে একটা 2D BFS চালিয়ে বের করে নিলাম সিম্পল। কিন্তু এই প্রব্লেম টি যখন অন্য কোন প্রব্লেম এর সাবটাস্ক হিসেবে আসবে তখন MLE অথবা TLE খাওয়ার সম্ভাবনা প্রবল। এক্ষেত্রে এই প্রব্লেম টি O(1) কমপ্লেক্সিটি তে সলভ করা সম্ভব। আর সেটি হলো P1 (x1,y1)  থেকে p2(x2,y2) বিন্ধুর ক্ষুদ্রতম দূরত্ব হচ্ছে distance = max( abs(x1-x2) , abs(y1-y2) )