কম্পিউটার বিজ্ঞান

আমরা জানি ম্যাপ ডিফল্ট ভাবে তার key অনুসারে অ্যাসেন্ডিং অর্ডারে সর্ট হয় । কিন্তু আমরা যদি key অনুসারে  সর্ট না করে value অনুসারে সর্ট করতে চাই তখন এই কাজটা কি ভাবে করা যায় আজকে আমরা সেটা দেখব ।    সাধারণ ভাবে ম্যাপ কে তার ভেলু অনুসারে সর্ট করা যায় না । ম্যাপ কে তার value অনুসারে সর্ট করার জন্য প্রথমে ম্যাপ  এর সবগুলো element [ key, value ] কে একটা vector এ কপি করে রাখতে হবে । এবং আমাদের কে সেই vector কে সর্ট করতে হবে । মনে করি আমাদের এই রকম একটা ম্যাপ আছে এবং তার মধ্যে এই ভেলুগুলো আছে । 1 2 3 4 5 map < string, int > mp; mp[ "ABC" ] = 10 ; mp[ "DEF" ] = 9 ; mp[ "GHI" ] = 5 ; ম্যাপের এই ডাটা গুলো কে আমরা একটা vector এ কপি করে রাখব । 1 2 3 4 5 6 vector < pair < string, int >> v; for ( auto it = mp.begin(); it != mp.end(); ++ it) { v.push_back( * it); // or we can use // v.push_back(make_pair(it->first, it->second));   } আমাদের ম্যাপের যেহেতু key, value দুইটা ভালু থাকে তাই এই দু...

Magic Square এমন একটি Square যার যেকোনো row, column, diagonal ভেলু গুলো যোগ করলে যোগফল সবসময় একই হবে ।  এই সমস্যা তে আমাদের কে Magic Square এ সাইজ দেয়া থাকবে প্রিন্ট করতে হবে Magic Square টি ।  Siamese (De la Loub`ere) method ব্যবহার করে এই সমস্যার সমাধান করা যায় ।  কোড :

আমাদের প্রথম ইনপুট দেয়া আছে { 0000, 0001, 10101, 010 } . এই সেটের প্রথম ২ টা থেকে ৩ টা করে নিলে আমরা যে Prefix পাব সেটাই আমাদের Prefix goodness . কারণ । ৩ * ২ = ৬ ।  Prefix Tree ব্যবহার করলে খুব সহজেই এই সমস্যা সমাধান করা যায় । কোড :

এই সমস্যা টি prefix tree ব্যবহার করে খুব সহজেই সমধান করা যায় ।  কোড :

এই সমস্যা টা মিনি-ম্যাক্স টাইপের সমস্যা ।  এই সমস্যা সমাধান করার জন্য প্রথমে আমাদের কে প্রত্যেক বিল্ডিং থেকে প্রত্যেক বিল্ডিং এ যাওয়ার মিনিমাম পাথ বের করতে হবে এই জন্য আমরা Floyd Warshall ব্যবহার করতে পারি ।  এর পর আমাদের কে যে source ও destination দেয়া থাকবে ।  আমরা প্রত্যেক বার source থেকে i হয়ে destination এ যেতে চেষ্টা করবে । যদি আমরা যতগুলি i ব্যবহার করে আমাদের লক্ষ্যে যেতে পারব তাদের মধ্যে যেটা ম্যাক্সিমাম সেটাই আমাদের কে প্রিন্ট করতে হবে ।   কোড :

এই সমস্যা তে আমাদের কে এমন একটা সিটি বের করতে হবে যে জায়গা তে আমরা প্রফেসারের সাথে দেখা করতে পারব ।  এবং আমাদের খরচ হবে মিনিমাম হবে যদি প্রফেসারে সাথে আমাদের দেখা করা সম্ভব হয় ।  এই জন্য আমরা আমাদের অবস্থান থেকে সবচেয়ে কম খরচে কোথাই  কোথাই যেতে পারি সেটা বের করতে হবে ।  এরপর প্রফেসর তার অবস্থান থেকে সবচেয়ে কম খরচে কোথাই  কোথাই যেতে পারে সেটা বের করতে হবে ।  এখন যে সকল সিটি তে প্রফেসর ও আমরা উভয়ে যেতে পারি সেই সিটি গুলো একটা ভেক্টরে জমা রাখতে হবে ।  ভেক্টরের যে সিটির খরচ সবচেয়ে কম হবে । সেটই আমাদের ও প্রফেসসের মিটিং করা জন্য সবচেয়ে ভাল জায়গা এবং  সেটাই প্রিন্ট করতে হবে । যদি এই রকম একাধিক জায়গা থাকে তবে সবগুলি শহর কে lexicographical order এ প্রিন্ট করতে হবে ।  যদি প্রফেসরের সাথে দেখা করা সম্ভব না হয় তবে প্রিন্ট আমরা You will never meet. প্রিন্ট করব । কোড :

এই সমস্যাতে আমাদের কে একটা নেটওয়ার্ক দেয়া থাকবে । এই নেটওয়ার্কে n সংখ্যক প্রসেস থাকবে ।  আমাদের কে বের করতে হবে ১ নং প্রসেস থেকে অন্য অন্য প্রসেসে কোন ম্যাসেজ পাঠাতে হলে মিনিমাম কত সময় খরচ করতেই হবে । অর্থাৎ আমাদের কে minimax বের করতে হবে ।  যেহেতু ম্যাক্সিমাম ১০০ টি প্রসেস থাকতে পারে সেহেতু আমরা Floyd Warshall ব্যবহার করে খুব সহজেই এই সমস্যার সমাধান করতে পারি ।  কোড :

Floyd Warshall's  এলগরিদম ব্যবহার করে খুব সহজেই এই সমস্যা সমাধান করা যায় ।  আমাদের ইনপুট গ্রাফে যদি u থেকে v তে যাওয়ার জন্য একবার টাইম দেয়া থাকল ২০ সেকেন্ড পরে আবার u থেকে v তে যাওয়ার টাইম দেয়া থাকল ৩০ সেকেন্ড । সেই ক্ষেত্রে আমাদের কে মিনিমাম টাইম অর্থাৎ ২০ সেকেন্ড কে নিতে হবে ।  কোড :

এই সমস্যা টি 2nd best MST বের করা সম্পর্কিত সমস্যা ।  এই সমস্যা সমাধান করার জন্য প্রথমে MST বের করতে হবে । MST বের করার পর আমরা চেক করবো সবগুলি নোড একই সেটে আছে কি না ? যদি না থাকে তবে No way প্রিন্ট করতে হবে ।  আর যদি সবগুলি একই সেটে থাকে তবে দেখব মোট নোড সংখ্যা ইনপুট দেয়া এজের থেকে ১ বেশি কি না? যদি কেবল মাত্র ১ বেশি হয় তবে 2nd best MST খুজে দেখার দরকার নাই । কারণ 2nd best MST পাওয়া যাবে না। এবং আমদের কে No second way প্রিন্ট করেতে হবে । যদি নোড থেকে এজের পার্থক্য ১ না হয় তবে আমাদের কে 2nd best MST খুজে বের করতে হবে । এবং আমাদের কে সেটাই প্রিন্ট করেতে হবে ।  এখন দেখা গেলও যে MST এবং 2nd best MST এর খরচ একই সেই ক্ষেত্রে আমদের কে প্রথমে পাওয়া MST খরচকেই প্রিন্ট করতে হবে । এই ক্ষেত্রে No second way প্রিন্ট করলে WA খেতে হবে ।  কোড :

আমরা MST তে যে কাজটা করি এই সমস্যাতে তার উল্টা কাজটা করতে হবে । অর্থাৎ আমাদের কে Maximum Spanning Tree বানাতে হবে ।  যে যে এজ নিয়ে আমাদের Maximum Spanning Tree গঠিত হবে । সেই এজ গুলির মধ্যে যে এজের ওয়েট সবচেয়ে কম সেই ওয়েট কে প্রিন্ট করতে হবে ।  এই সমস্যা তে আমাদের কে কিছু কর্নার কেইস বিবেচনা করতে হবে । যেমন : আমাদের ইনপুটে যদি  m = 0 হয় তবে max_cost কত হবে ? max_cost হবে int এর ম্যাক্সিমাম ভেলু অর্থাৎ INT_MAX = 2147483647  যদি একই এজ একের অধিক বার ইনপুটে দেয়া থাকে তবে তাদের মধ্যে যেটার ওয়েট ম্যাক্সিমাম সেই এজেটি নিয়ে বাকি গুলো বাদ দিতে হবে ।  [ প্রথম ইনপুট লক্ষণীয় ] যদি একই নোড থেকে একই নোডে আসার কোন পাথ থাকে অর্থাৎ যদি u == v হয়ে তবে আমাদের কে সেই এজটি গ্রাফ থেকে প্রথমেই বাদ দিতে হবে :)   কোড :

Just count the number of edges not taken by Kruskal's 😘 কোড : Happy Coding :)

এই সমস্যা তে আমাদের কে 2nd best MST বের করেত হবে ।  এই সমস্যা সমাধান করার জন্য আমাদের কে প্রথমে MST বের করতে হবে । এবং এই MST তে যে এজ গুলি নেয়া হয়েছে সেগুলো ইন্ডিকেট করে রাখতে হবে ।  এখন এই MST এর এজগুলি থেকে প্রতিবার একটা করে এজ বাদ দিয়ে নতুন MST গঠন করার চেষ্টা করবো । এবং সেটার মোট খরচ কত হয় সেটা হিসাবে করে রাখব ।  আমরা যখন আমাদের MST থেকে কোন এজ বাদ দিয়ে নতুন একটা ST বানাতে চেষ্টা করবো তখন শেষে আমাদেরকে চেক করতে হবে যে এই এজ টি বাদ দিয়ে আসলেই MST বানানো সম্ভব কি না ?  এটা নিশ্চিত করার জন্য যখন আমাদের MST বানানো শেষ হবে তখন দেখতে হবে যে আমাদের সবগুলি নোড একই সেটের মধ্যে আছে কি না ? যদি সবগুলি একই সেটের মধ্যে না থাকে তবে বুঝতে হবে । আমরা যে এজ কে বাদ দিয়ে MST বানানোর চেষ্টা করেছি । সেই এজ কে বাদ দিয়ে আসলে MST বানানো সম্ভব না । এই ভাবে যতগুলো MST গঠন করা যাবে তাদের মধ্যে যেটার খরচ সবচেয়ে কম সেটাই আমাদের 2nd best Minimum Spanning Tree .   কোড : Happy Coding :)

আমাকে কোন একটা শহরের একটা জায়গা থেকে অন্য একটা জায়গায় যেতে হবে । আমি বিভিন্ন রাস্তা ব্যাবহার করে আমার  কাঙ্ক্ষিত জায়গায় যেতে পারি । কিন্তু আমাকে এমন রাস্তা ব্যাবহার করে যেতে হবে যে রাস্তা দিয়ে গেলে আমাকে সবথেকে কম decibels এর শব্দ শুনতে হবে ।   এই সমস্যা টি সমাধান করার জন্য আমাদের কে  গ্রাফের ইনফরমেশন দেয়া হবে সেগুলো নিয়ে একটা Minimum Spanning Tree বানাতে হবে ।  এখন এই MST র উপর query করতে হলে আমাদের কে DFS/BFS চালাতে হবে ।  এইখান থেকে আমরা যে একটা নোড থেকে অন্য একটা নোডে যাওয়ার রাস্তা পাব তার মধ্যে খুজে দেখব কোন এজের ওয়েট সবথেকে বেশি । সেটাই আমাদের কে প্রিন্ট করেত হবে ।  যদি কোন রাস্তা না থাকে তবে no path প্রিন্ট করতে হবে ।  কোড : হ্যাপি কোডিং :)

আমাদের কে গ্রফল্যান্ডের শহরগুলির যে co-ordinate দেয়া থাকবে  তাদের সবগুলি থেকে সবগুলির দূরত্ব বের করে সেটা কে ওয়েট ধরে একটা গ্রাফ বানাতে হবে ।  এই গ্রাফ থেকে MST বের করেত  হবে ।  আমাদের মূল গ্রাফ থেকে MST বের করার সময় যখন প্রতিবার একটা করে নতুন এজ নিব তখন চেক করতে হবে নতুন এজটার ওয়েট আমাদের Threshold ( r )  থেকে বড় কি না ?  যদি সেটা r থেকে বড় হয় তবে সেই এজটা ওয়েট rail roads extension এ যোগ করতে হবে । আর যদি সেটা r থেকে ছোট হয় তবে সেটা state roads extension এ যোগ করতে হবে ।  মোট states সংখ্যা = mst তে  মোট node সংখ্যা - মোট এজ সংখ্যা [ rail road এজ বাদে ]  প্রিন্ট Extension rounded to the nearest integer ;)  কোড :  হ্যাপি কোডিং :D