Light OJ - 1005 - Rooks Tutorial(DP)

-
Problem Description here

প্রব্লেমটিতে বলা হয়েছে, একটা n*n গ্রীড দেয়া থাকবে। সেখানে k সংখ্যক রুক বসাতে হবে যাতে তারা একে অন্যকে এটাক করতে না পারে। আমরা জানি, গ্রীডের যেকোন সেল রিপ্রেজেন্ট করতে দুইটা ভ্যালু লাগে। একটা সারি নং , অন্যটা কলাম নং। একটা রুক অন্য রুককে তখনই এটাক করে যখন অন্য রুক এর সাথে তার সারি নং অথবা কলাম নং মিলে যায়।
সল্যুশন আইডিয়াঃ 

আমাকে এমনভাবে, k সংখ্যক রুক বসাতে হবে যাতে একই সারিতে দুইটা রুক বসতে না পারে এবং একই কলামে দুইটা রুক বসতে না পারে। 

ডিপি'র স্টেট নিবো দুইটা। 
স্টেট-১ঃ এখন আমি কত তম সারি তে আছি।
স্টেট-২ঃ কয়টা রুক বসানো এখনো বাকি আছে।

প্রতিটি অবস্থানে আমার সর্বোচ্চ দুই ধরনের অবস্থা দাঁড়াতে পারে।

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

এখন, ব্যাবহারযোগ্য কলামগুলো থেকে একটি কলাম কতভাবে বাছাই করা যায়? সেই সংখ্যার সাথে গুণ হবে পরবর্তী স্টেট থেকে যেসব ভ্যালু পাবো। 

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

Happy Coding -_-

Comments

Post a Comment

Trending Post

Shortest distance between two point in a grid when you can move all 8 sides from a position

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

DP Optimization(Part-4) | Longest Increasing Subsequence | DP Series(Episode-18)

-
 এই পর্বে আমরা মূলত ডাটা স্ট্রাকচার ব্যাবহারের মাধ্যমে কিছু কিছু ডিপি প্রব্লেমের কমপ্লেক্সিটি কিভাবে কমিয়ে আনা সম্ভব তা দেখবো।  Problem: মনে কর, তোমাকে একটি n<=10^4 সাইজের অ্যারে দেয়া আছে। এই অ্যারের দীর্ঘতম ক্রমবর্ধমান অনুক্রমের দৈর্ঘ্য বের করতে হবে😛 ইংরেজীতে বললে Longest Increasing Subsequence এর Length বের করতে হবে। তাহলে এই প্রব্লেমের সল্যুশন কি হতে পারে?  Hints: শেষ থেকে শুরুর দিকে প্রত্যেক পজিশনে দাঁড়িয়ে দেখবো এই পজিশনের ভ্যালুটি অবশ্যই নিলে আমি সর্বোচ্চ কত লেন্থ এর LIS বানাতে পারবো। এভাবে সবগুলো রেজাল্ট এর মধ্যে ম্যাক্সিমাম টা এন্সার।  কোডটি হলোঃ  এখন, কী হবে যদি n<=10^5 এবং a[i]<=10^5 হয়?  উপরের সল্যুশন এ ভালো করে লক্ষ্য করলে দেখবে যে, প্রত্যেক পজিশন i তে দাঁড়িয়ে আমরা দেখি i এর ডানে যেসব ভ্যালু আছে a[i] এর সমান অথবা বড় তাদের মধ্যে কার DP এর ভ্যালু সর্বোচ্চ? যেখানে, dp[i] বলতে বোঝায় ith to nth ইনডেক্সের ভ্যালুগুলো কনসিডার করে সর্বোচ্চ কত লেন্থ এর LIS বানানো যায়।  একটু ভালো করে চিন্তা করলে দেখবে ১৫ নম্বর লাইনের ইনার লুপের ক...
Read more