Problem link
This is a 'simple' BFS or 'DFS' problem, at the beginning I approached it by using DFS but I got TLE
so I change it to BFS and result easier. First, for the read, I had to use a map, cuz' the nodes could be greater than the total number of nodes. (Ej. 3 nodes = 20233,892832,3289), then I used another map to count the number of moves from the query node to every other node in the graph and finally I count the number of nodes where the moves are less than the 'ttl'. BUT, There could be no-connected nodes so you have to verify that you're counting all the nodes.
Sources
প্রবলেম : এই প্রবলেমটিতে মূলত বলা হয়েছে, আমাদের কিছু ভার্টেক্স আর তাদের মধ্যে এজ দেয়া থাকবে । আর এগুলো দেয়ার পর আমাদের টেস্ট কেস হিসেবে দেয়া নোড গুলোর মধ্য থেকে কিছু নোড আর তাদের মধ্যের টাইম টু লিভ বা টিটিএল (TTL) দেয়া থাকবে । এই নোড থেকে শুরু করে আমাদের বের করতে হবে টিটিএল এর উপর বেস করে সর্বোচ্চ কয়টা নোড ভিজিট করা যাবে আর কতগুলো যাবে না । যতগুলো যাবে না আমাদের মূলত ঐ সংখ্যাটাই প্রিন্ট করতে হবে । টিটিএল বলতে বুঝিয়েছে আমরা স্টার্টিং নোড থেকে শুরু করে সর্বোচ্চ কতগুলো নোড একটানা ভিজিট করতে পারব বা একই পথে আমরা টানা কয়টা নোড পর্যন্ত যেতে পারব ।
এ প্রবলেমটির মূল অ্যাালগরিদম খুবই সোজা । শুধুমাত্র বিএফএস/লেভেল বাই লেভেল সার্চ করে আমাদের টিটিএল এর নম্বর যত তত লেভেল পর্যন্ত গেলে কতগুলো ভার্টেক্স ভিজিট করতে পারছি আর কতগুলো করতে পারছি না এটা বের করতে পারলেই যথেষ্ট ।
কিন্তু এর মূল সমস্যা হচ্ছে ইনপুটে । এখানে সব আর্বিটারি নোড দেয়া । এগুলোকে গ্রাফে গুছিয়ে স্টোর করাটাই এ প্রবলেম এর সবচাইতে বড় চ্যালেঞ্জ । আমি যেটা করেছিলাম সবগুলো ইনপুট নিয়ে ঐগুলো কে স্ট্রাকচারে রেখেছিলাম যেখানে মোটামুটি ৪টার মত উপাদান ছিল । ২টি হচ্ছে ২টি ভার্টেক্স যেগুলো দেয়া আর বাকি ২টা হচ্ছে আমরা এই ভার্টেক্স গুলোকে আমাদের সুবিধার জন্য কোন নাম দিচ্ছি সেটা । আমি নামটা এভাবে বার করেছিলাম, আমি প্রথমেই দেখেছিলাম আমার ইনপুট এর মধ্যে একদম ভিন্ন নাম্বার কয়টি আছে , সেই নাম্বারটিই নোড কয়টা আছে সেটা বুঝায় । এরপর ছোট থেকে বড়তে সর্ট করেছিলাম আর এদের ইনডেক্স নাম্বরটিকেই এদের নতুন নাম্বার দিয়েছিলাম যেটা নতুনভাবে নোড হিসেবে তাদেরকেই বুঝাবে ।
এভাবে আমি সব আর্বিটারি নোডগুলোকে একটা গুছানো অর্ডারে নিয়ে এসে গ্রাফে স্টোর করেছিলাম । তারপর খুবই সাধারণ ভাবে বিএফএস করে আমাদের আউটপুটটি বের করেছিলাম ।
Sources
ব্রেডথ ফার্স্ট সার্চ Breadth-first search (BFS) (Tutorial)
A solution in c++
প্রবলেম : এই প্রবলেমটিতে মূলত বলা হয়েছে, আমাদের কিছু ভার্টেক্স আর তাদের মধ্যে এজ দেয়া থাকবে । আর এগুলো দেয়ার পর আমাদের টেস্ট কেস হিসেবে দেয়া নোড গুলোর মধ্য থেকে কিছু নোড আর তাদের মধ্যের টাইম টু লিভ বা টিটিএল (TTL) দেয়া থাকবে । এই নোড থেকে শুরু করে আমাদের বের করতে হবে টিটিএল এর উপর বেস করে সর্বোচ্চ কয়টা নোড ভিজিট করা যাবে আর কতগুলো যাবে না । যতগুলো যাবে না আমাদের মূলত ঐ সংখ্যাটাই প্রিন্ট করতে হবে । টিটিএল বলতে বুঝিয়েছে আমরা স্টার্টিং নোড থেকে শুরু করে সর্বোচ্চ কতগুলো নোড একটানা ভিজিট করতে পারব বা একই পথে আমরা টানা কয়টা নোড পর্যন্ত যেতে পারব ।
এ প্রবলেমটির মূল অ্যাালগরিদম খুবই সোজা । শুধুমাত্র বিএফএস/লেভেল বাই লেভেল সার্চ করে আমাদের টিটিএল এর নম্বর যত তত লেভেল পর্যন্ত গেলে কতগুলো ভার্টেক্স ভিজিট করতে পারছি আর কতগুলো করতে পারছি না এটা বের করতে পারলেই যথেষ্ট ।
কিন্তু এর মূল সমস্যা হচ্ছে ইনপুটে । এখানে সব আর্বিটারি নোড দেয়া । এগুলোকে গ্রাফে গুছিয়ে স্টোর করাটাই এ প্রবলেম এর সবচাইতে বড় চ্যালেঞ্জ । আমি যেটা করেছিলাম সবগুলো ইনপুট নিয়ে ঐগুলো কে স্ট্রাকচারে রেখেছিলাম যেখানে মোটামুটি ৪টার মত উপাদান ছিল । ২টি হচ্ছে ২টি ভার্টেক্স যেগুলো দেয়া আর বাকি ২টা হচ্ছে আমরা এই ভার্টেক্স গুলোকে আমাদের সুবিধার জন্য কোন নাম দিচ্ছি সেটা । আমি নামটা এভাবে বার করেছিলাম, আমি প্রথমেই দেখেছিলাম আমার ইনপুট এর মধ্যে একদম ভিন্ন নাম্বার কয়টি আছে , সেই নাম্বারটিই নোড কয়টা আছে সেটা বুঝায় । এরপর ছোট থেকে বড়তে সর্ট করেছিলাম আর এদের ইনডেক্স নাম্বরটিকেই এদের নতুন নাম্বার দিয়েছিলাম যেটা নতুনভাবে নোড হিসেবে তাদেরকেই বুঝাবে ।
এভাবে আমি সব আর্বিটারি নোডগুলোকে একটা গুছানো অর্ডারে নিয়ে এসে গ্রাফে স্টোর করেছিলাম । তারপর খুবই সাধারণ ভাবে বিএফএস করে আমাদের আউটপুটটি বের করেছিলাম ।
Sources
ব্রেডথ ফার্স্ট সার্চ Breadth-first search (BFS) (Tutorial)
A solution in c++
0 Comments
If you have any doubts, Please let me know