راه حل های آزمون عملی دوم شاززز

پیشنهاد میشه اگه آزمون رو ندادید اول سوالا رو بخونید و خودتون روش فکر کنید!

سوال اول:

اول باینری سرچ روی جواب میزنیم. فرض کنید میخوایم چک کنیم که آیا جواب مسئله میتونه کمتر مساوی x باشه یا نه.

ماکسیمم جفت کفش ها واضحه که min(n , m) هستش و بدون کم شدن از کلیت مسئله فرض کنید n<=m ینی کفش پای راست کمتر مساوی کفش های پای چپن.

کفش های پای راست و چپ رو بر اساس سایزشون سورت میکنیم. بعد شروع میکنیم از کفش با سایز مینیمم پای راست و سعی میکنیم با کفش با مینیمم سایز پای چپ جفتش کنیم. اگه در مرحله ای نتونستیم برای یه کفش پای راست جفت پیدا کنیم ینی جواب کمتر مساوی ایکس نمیتونه باشه. وگرنه هم که هست!

اگر سورت ها رو قبل از باینری سرچ انجام بدیم پیچیدگی زمانیمون (O(nlogn + nlog (max_size_kafsh) هستش.

کد

سوال دوم:

ثابت میشه که همیشه جواب وجود داره. اول کسایی رو در نظر بگیرید که انتخابشون یکتاست ینی اگه مجاور دو ظرف با تعداد a,b باشه که a/2<=b این شخص انتخابش یکتاست و ظرف با سایز b رو انتخاب میکنه چون در هر صورت از اون ظرف بیشتر سیب زمینی میخوره.

حالا بقیه افراد رو بگیرید، اگه هیچکس انتخابش یکتا نباشه و همه از سیب زمینی خودشون بخورن، یک جواب داریم.

پس حداقل یه نفر هست که انتخابش یکتا باشه. وقتی بقیه افراد رو در نظر میگیریم این افراد یه سری بازه روی دایره‌ن. با یکم حالت بندی هر بازه هندل میشه. برای بهتر فهمیدن حالت ها خوبه که کد رو بخونید!

کد

سوال سوم:

از اینجا میتونید  راه حل رو بخونید. (صفحه ی ۱۳)

کد

سوال چهارم:

برای کمینه کردن جواب، دوبخشی درخت ر در نظر بگیرید. (درخت ها دوبخشین!! واو) همه یال ها رو از یه بخش به بخش دیگه جهت دار کنید. اینطوری جواب برابر تعداد یال های درخت میشه که به وضوح از این بهتر هم نمیشه کرد جوابو.

تو گراف به راسی که جمع فاصله هاش تا بقیه رئوس مینیممه میگیم سنتروید. اینجا میتونید یکم بیشتر دربارش بخونید.

برای بیشینه کردن جواب، فرض کنید سنتروید درخت راس c باشه. ثابت میشه حالتی از جواب بیشینه وجود داره که به ازای هر راس v توی درخت یا v به c مسیر داره یا c به v. درخت رو از سنتروید آویزون کنید. طبق چیزی که گفتیم اگه یال بین c,v رو از c به v بدیم باید تو کل زیردرخت راس v هم یالا رو به پایین باشن.

فرض کنید کسایی که به c مسیر دارن a تا باشن. جواب برابر (a)*(n-1-a) + n-1 هستش. همچنین a*(n-1-a) وقتی ماکسیمم میشه که a نزدیک ترین حالت به n-1/2 باشه. (کتاب سوم دبستان)

پس میتونیم زیردرخت ها رو به شکل یه سری دسته ببینیم که دسته iام اندازه‌ش برابر با سایز زیردرخت iامه. بعد روی نصف مجموع این دسته ها باید knapsack بزنیم که از اینجا میتونید مشاهده کنید.

پیچیدگی زمانیمون میشه O(n^1.5) که اگه با بیت‌ست نپسک رو بزنیم O(n^1.5/32) میشه.

کد