دومین آزمون کات برنز دوره 27

سلام

دومین آزمون برنز کات دوره 27 رو هم میخوایم بزاریم براتون.

آزمون جمعه، 11 اسفند، ساعت 9 صبح شروع میشه. مدت آزمون 5 ساعته و 3 تا سوال که هرکدوم میتونن چندبخش داشته باشن داره.

این آزمون هم مثل قبلی با همکاری کوئرا هست و از این لینک هم میتونین بدین آزمون رو.

از آزمون قبلی که خوب استقبال کردین موشالا دمتون گرم🙃، این رو هم سعی کنین بدین.

راستی اگه سوالی چیزی هم دارین کلا کامنت بزارین (میتونین کامنت خصوصی هم بدین اگه میخواین ملت نبینن😈). اگه چیز مهمی هم مد نظرتون هست که دوس دارین دربارش بلاگ بزاریم و صحبت کنیم، بگین که درنظر بگیریم.

همین دیگه خوش باشین.😉

* واسه سوالا یه راهنمایی کوتاه هم میگیم. (با تشکر از Smss)

سوال 1 : مسئله معادل این است که k راس انتخاب کنیم به طوری که هیچکدام جد دیگری نباشد. راس ها را بر اساس starting time سورت می کنیم (ترتیبی که در زمان dfs زدن از ریشه راس ها را می بینیم). یک زیردرخت را در نظر بگیرید که ریشه این زیر درخت v و اندازه زیر درخت sz باشد. starting time راس هایی که در این زیردرخت هستند می شود بازه
(starting time(v),starting time(v)+sz].

سوال 2 : با دی پی حل کنید. بر اساس bi ها غول ها را مرتب کنید. اگر در لحظه ای قدرتمان بیشتر از 2000 شد می توانیم فرض کنیم قدرتمان 2000 است چون تمام bi ها کمتر مساوی 2000 هستند.

سوال 3 : فرض کنین لازم نباشه از z به x برگردیم، یعنی قراره از x به y و بعدش از y به z بریم. مسیر y به x و مسیر y به z رو در نظر بگیرین. این دوتا مسیر تا یه جایی رو باهم دیگه طی میکنن (یعنی یال های دو تا مسیر یکی هستن) و بعدش از هم جدا میشن. حالا سعی کنین ثابت کنین که یک جواب بهینه وجود داره که وقتی این دوتا مسیر برای اولین بار از هم جدا میشن، دیگه هیچوقت یال مشترک با هم طی نمیکنن.

دیدین چقد به نظراتون اهمیت میدیم؟ دیدین؟ دیدین؟😊 پس تا درودی دیگر، بدرووود.😉