At Coder - Grand Contest 001 - Shorten Diameter Tutorial

Problem Description here

প্রবলেমঃ প্রবলেমটিতে মূলত বলা হয়েছে, n সংখ্যক নোডের একটি ট্রি দেয়া থাকবে। সর্বনিম্ন কতগুলো নোড বাদ দিলে ট্রি এর ডায়ামিটার সর্বোচ্চ k হবে। 

একটি ট্রি এর ডায়ামিটার বলতে বুঝানো হয় ট্রি এর যেকোন দুইটি নোডের মধ্যবর্তী দূরত্বগুলোর সর্বোচ্চ মান। 

সল্যুশন আইডিয়াঃ 

১) প্রতিটি ডায়ামিটার এর একটা সেন্টার থাকে। সেন্টার থেকে দুইদিকের দূরত্ব সমান হয়। 

২) ডায়ামিটার এর দৈর্ঘ্য জোড় হলে সেন্টার হবে একটা নোড। আর বিজোড় হলে সেন্টার হবে একটা এজ। 

৩) এখন, ট্রি এর প্রতিটি নোড অথবা এজকে (k এর মান এর উপর নির্ভর করে) ডায়ামিটার এর সেন্টার ধরে দেখবো এই নোড বা এজ সেন্টার হলে কতগুলো নোড রাখা যায় অথবা কতগুলো নোড বাদ দিতে হয়?

এভাবে, প্রতিটি নোড হিসেব করে সর্বনিম্ন কয়টা বাদ দেয়া যায় সেটা বের করা সম্ভব। 



Comments

Trending Post

At Coder Educational DP-A | DP Series(Episode-1)

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