Bappy's Blog

Problem Description  here প্রব্লেমটিতে বলা হয়েছে, একটা n*n গ্রীড দেয়া থাকবে। সেখানে k সংখ্যক রুক বসাতে হবে যাতে তারা একে অন্যকে এটাক করতে না পারে। আমরা জানি, গ্রীডের যেকোন সেল রিপ্রেজেন্ট করতে দুইটা ভ্যালু লাগে। একটা সারি নং , অন্যটা কলাম নং। একটা রুক অন্য রুককে তখনই এটাক করে যখন অন্য রুক এর সাথে তার সারি নং অথবা কলাম নং মিলে যায়। সল্যুশন আইডিয়াঃ  আমাকে এমনভাবে, k সংখ্যক রুক বসাতে হবে যাতে একই সারিতে দুইটা রুক বসতে না পারে এবং একই কলামে দুইটা রুক বসতে না পারে।  ডিপি'র স্টেট নিবো দুইটা।  স্টেট-১ঃ এখন আমি কত তম সারি তে আছি। স্টেট-২ঃ কয়টা রুক বসানো এখনো বাকি আছে। প্রতিটি অবস্থানে আমার সর্বোচ্চ দুই ধরনের অবস্থা দাঁড়াতে পারে। ১) আমি ভিজিট করি নি এমন সারির সংখ্যা যদি বাকি থাকা রুকের সংখ্যা থেকে বেশি হয়, তবে আমি বর্তমান সারি ব্যাবহার করতেও পারি। নাও করতে পারি।  ২) আমি যদি বর্তমান সারি ব্যাবহার করি, তাহলে এই সারি থেকে আমাকে একটি কলাম বাছাই করে নিতে হবে। সোজা কথায় এই সারির একটা সেল বাছাই করতে হবে। যেহেতু, বর্তমানে অব্যাবহৃত রুকের সংখ্যা আমার...

Problem Description  Click here প্রব্লেমটিতে বলা হয়েছে, একটা n*n গ্রীড দেয়া থাকবে। সেখানে k সংখ্যক রুক বসাতে হবে যাতে তারা একে অন্যকে এটাক করতে না পারে। আমরা জানি, গ্রীডের যেকোন সেল রিপ্রেজেন্ট করতে দুইটা ভ্যালু লাগে। একটা সারি নং , অন্যটা কলাম নং। একটা রুক অন্য রুককে তখনই এটাক করে যখন অন্য রুক এর সাথে তার সারি নং অথবা কলাম নং মিলে যায়। সল্যুশন আইডিয়াঃ  তার মানে আমাকে এমনভাবে, k সংখ্যক রুক বসাতে হবে যাতে একই সারিতে দুইটা রুক বসতে না পারে এবং একই কলামে দুইটা রুক বসতে না পারে।  ১ম ক্ষেত্রঃ   k>n হলে আমি কোনভাবেই রুকগুলোকে নন-এটাকিং পজিশনে বসাতে পারবো না। যেকোন সারি কিংবা কলাম বরাবর আমাকে একাধিক রুক বসাতেই হবে। তাই, সেক্ষেত্রে এন্সার হবে ০।  ২য় ক্ষেত্রঃ   আমাকে প্রথমে বেছে নিতে হবে যে আমি কোন কোন সারিগুলোতে রুক বসাবো। আর n সংখ্যক সারি থেকে k সংখ্যক সারি বাছাই করা যায় কতো উপায়ে? সেটা নাহয়, তুমিই বের চিন্তা কর। এবার, সারিতো বেছে নিলাম। সেই সারিগুলোর কোন কোন কলাম বরাবর আমি রুক বসাবো? ১ম সারির ক্ষেত্রে আমার হাতে অপশন আছে n টি কলাম। যেক...

Problem Description   Click Here Topic Of This Problem: Segment Tree with Offline Query n সংখ্যক ভিন্ন ভিন্ন সংখ্যার একটি অ্যারে দেয়া থাকবে এবং q সংখ্যক কুয়েরী দেয়া থাকবে। প্রতি কুয়েরী তে l থেকে r ইনডেক্সের মাঝে এমন কয়টা পেয়ার (ara[i] , ara[j]) আছে যেখানে ara[i] সংখ্যাটি ara[j] এর একটা ডিভিজর। প্রথমে এই প্রব্লেমটাকে একটু জেনারেলাইজ করা যাক, তোমাকে একটা দ্বিমাত্রিক তল দেয়া আছে। এই তলে অনেকগুলো অনুভূমিক রেখা আছে। বের করতে হবে, X অক্ষ বরাবর l to r ইনডেক্সের মাঝে কয়টা রেখা সম্পূর্ণভাবে অবস্থান করে। সল্যুশন আইডিয়াঃ ১) জেনারেলাইজ প্রব্লেম অনুযায়ী, প্রতিটা অনুভূমিক রেখার স্টার্টিং আর এন্ডিং পয়েন্ট আমার জানা লাগবে। এজন্য, ১ থেকে n পর্যন্ত প্রতিটি সংখ্যার জন্য তার মাল্টিপল এর ইনডেক্স বের করবো। যেমন, ২ এর ইনডেক্স যদি x হয় এবং ৪ এর ইনডেক্স যদি y হয় তার মানে অনুভূমিক রেখাটি X অক্ষের সমান্তরালে x থেকে y পর্যন্ত অবস্থিত। এভাবে, প্রতিটি সংখ্যার ইনডেক্স এর জন্য তার মাল্টিপলগুলোর ইনডেক্স গুলো বের করে রাখবো। ২) এবার কুয়েরী ইনপুট নেয়ার সময় একটি পেয়ার এর ভেক্টরে প্রত্যেক প...

Problem Description  here Topic Of This Problem: Dijkstra ১) এই প্রব্লেম সলভ এর জন্য আমরা দুইটা গ্রাফ বানাবো। একটা গ্রাফ ইনপুটে দেয়া থাকবে। আরেকটা গ্রাফ হবে ইনপুটে দেয়া গ্রাফটার রিভার্স(উল্টো) গ্রাফ। ২) অরিজিনাল গ্রাফ ব্যাবহার করে সোর্স থেকে সকল নোডে যাওয়ার ক্ষুদ্রতম দূরত্ব বের করে নিবো। আর রিভার্স গ্রাফ ব্যাবহার করে ডেস্টিনেশন থেকে সকল নোডে যাওয়ার ক্ষুদ্রতম দূরত্ব বের করে নিবো। ৩) এখন, ইনপুটে দেয়া সকল এজ [ U,V ] এর জন্য দেখবো, সোর্স থেকে U নোডের দূরত্ব + [U,V] এজ এর কস্ট + ডেস্টিনেশন থেকে V নোডের দূরত্ব <= P হয় কি না। যদি হয় তার মানে, [U,V] এজ ব্যাবহার করে একটা পসিবল পাথ আছে যার মোট কস্ট P এর সমান অথবা ছোট। তখন, Cost  [U,V] আমার একটা পসিবল এন্সার। এভাবে, সর্বোচ্চ কস্টের যে এজ টা নিয়ে পাথ সম্ভব সেই এজের কস্ট ই হবে আউটপুট। ডায়াক্সট্রা সম্পর্কে জানতে  ক্লিক করুন Happy Coding -_-