نباید از حل سوالات مرحله 3 ها هم غافل شد ما اینجا روز دوم دوره 25 رو بررسی می کنیم.
فایل سوالات : دریافت
آزمون رو توی یه تایم 3 ساعته با یه دلتای مشخص بدید بعد به ادامه مطلب بیاید
1- خب سوال اول رو میخوایم با هم بررسی کنیم سابتسک الف رو که میشه با یه سگمنت جوابشو به دست آورد ولی برای بخش ب و ج باید چه کرد ؟ خب منطقیه که ذهنمون سمت dp بره به این علت که اگه شما درخت سوال رو نگاه کنید درخت با ارتفاع n درخت ارتفاع n - 1 رو در سمت چپ ریشه خودش و باز هم همون درخت رو سمت چپ میبینید که به هر کدوم از برگ ها  اضافه شده میتونید بررسی کنید که در مجموع  به رئوس سمت راست اضافه میشود پس اگر [dp[i را عدد روی ریشه درخت با ارتفاع i تعریف کنیم :
خلاصه که با این راه سابتسک الف تا ج حل میشه میمونه بخش د سوال رو هم باید جداگونه حل کرد که باید با توجه به هر راس یه ضریبی بهش بدید که حالا اون ضریبه چیه ؟ با توجه به این که هر مرحله میرید بالا راس دوبرابر شده این راس هست یا نه و در نهایت باید از بزرگ به کوچیک اعداد رو توی این ضریب ها قرار بدید کد دوتا راه حل هم اینجاس:
الف تا ج : دریافت
د : دریافت

2- این سوال مبحث خاصی نداره و صرفا دوتا سابتسک اول فقط با زدن کد چیزی که خواسته شده هندل میشه و میمونه سابتسک آخر
توی اون اول هدف رو بگیم که هدفمون اینه که تایم رو بتونیم کامپرس کنیم و همین کار کمک میکنه بتونیم سوال رو هندل کنیم حالا اگه بتونیم در هر مرحله اولین خونه ای که اشباع میشه رو پیدا کنیم کار تمومه دیگه :دی. خب پس هر مرحله جای اینکه یک ثانیه جلو بریم میایم اینقد تایم رو جلو میبریم که یه خونه اشباع شه اولین خونه که اشباع شد همون مقدار تایم رو میبریم جلو هر بار که تایم میره جلو باید مینیمم   رو برای هر خونه که هنوز اشباع نشده پیدا کنیم (t همون تعداد خونه هاییه که به خونه ما از چپ و راست و بالا و پایین باکتری اضافه میکنن) مینیمم اینا تا باید به تایممون اضافه شه این جوری بعد از بار انجام این کار سوال هندل میشه و کار تمامممممه.
الف : دریافت
ج : دریافت

3- خب میرسیم به سوال سوم. برای این سوال بخش الفش که با (brute force) روی کل زیرمجموعه ها که بزنید میتونید اولی رو اکسپت کنید. ولی برای بخش دوم و سوم این کار میسر نیست، حالا واسه اونا باید چه کرد ؟ خب ما میتونیم سوال رو یه ذره بخش بندی کنیم اونم اینجوری که حساب کنیم به ازای هر عدد i از 1 تا n تو چنتا از f های زیرمجموعه ها این عضو میاد! اینو حساب کنیم خیلی خوب میشه دیگه حالا اگه بیایم حساب کنیم که تو چنتا نمیاد و متمم کنیمش بازم هندله دیگه D: ، خب حالا میایم به ازای هر x از 1 تا n اعداد رو دسته بندی میکنیم به این صورت : 
حالا چون هر کدوم از زنجیر ها از هم مستقلن هر کدوم جدا حل میشن بعد طبق اصل ضرب، تو هم ضرب میکنیمشون حالا مسئله تبدیل میشه به چی ؟ همینطوری که می بینید قدرنسبت هر دو عضو تو این زنجیر ها میشه x پس از هر زنجیر میخوایم یه تعدادی انتخاب کنیم که هیچ دوتایی متوالی نباشن. این با dp راحت در میاد و میشه فیبوناچی حالا به ازای هر x باید بتونیم طول زنجیرهارو در بیاریم برای سابتسک ب که مشکلی نداره و میتونیم فور بزنیم و حساب کنیم ولی برای سابتسک ج نمیشه پس باید تو یه اردر نسبتا خوبی اینارو سایز زنجیرهارو هم در بیاریم که تمام شه کارمون. اینکار رو میتونید تو اردر بد در بیارید یه ذره خوب کردن اردرش ریزه کاری داره چون دیگه سخت بود اونو استثنا حذف کردیم و با یه 20 مین منتظر موندن میتونید جواب رو ببینید
الف : دریافت
ب و ج : دریافت
**حواستون باشه که mod رو تو هر کد متناسب با دلتایی که دارید عوض کنید وگرنه جواب غلط میگیرید ;)