صفحه ۶
الگوریتم هفتگی-نظریه اعداد
این پست یکم سنگینه. چون نظریه اعداد مبحث کوچیکی نیست. اما سعی کردیم جمعش کنیم. لازمه لینک هایی که گفته شده ر بلد باشید تا بتونید سوال ها ر حل کنید. همچنین تو خود لینک ها هم سعی کنید چندتا از سوالای انتهای صفحهشون ر بزنید!
مباحثی که خوبه بلد باشید:
سوالات ترتیب خاصی ندارن!
مهدی جعفری :(
۱۳۹۷/۱۲/۲۶ · ۱۶:۲۴
الگوریتم هفتگی-مولفه های قویا همبند و مرتبسازی توپولوژیک
۱۳۹۷/۱۲/۱۶ · ۱۸:۲۰
راه حل های آزمون عملی دوم شاززز
پیشنهاد میشه اگه آزمون رو ندادید اول سوالا رو بخونید و خودتون روش فکر کنید!
سوال اول:
اول باینری سرچ روی جواب میزنیم. فرض کنید میخوایم چک کنیم که آیا جواب مسئله میتونه کمتر مساوی 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) میشه.
۱۳۹۷/۱۲/۱۰ · ۲۱:۱۴
آزمون عملی دوم شااززز
سلام. جمعه ی این هفته ساعت ۹ صبح میخوایم یه آزمون عملی ۵ ساعته ی دیگه برگزار کنیم.
ذره ای تضمین وجود نداره که سوالای آزمون ر قبلن ندیده باشید! پس احیانن تلف شدن وقتتون ر گردن ما نندازید.
آزمونی که قراره بذاریم یکی از آزمون های مدرسه علامه حلی تهرانه.
آپدیت: متاسفانه سرورمون از دسترس خارج شد و نتونستیم روی cms آزمون رو برگزار کنیم. کوئرا بهمون کمک کرد و آزمون روی سایت کوئرا برگزار خواهد شد که از اینجا میتونید ثبت نام کنید.
۱۳۹۷/۱۲/۰۸ · ۲۳:۲۲
الگوریتم هفتگی-کوتاهترین مسیر
مباحثی که لازمه برای این پست بلد باشید (به ترتیب):
الگوریتم دایکسترا (دایجسکترا دایجسترا)
حالا میریم سراغ سوالا که بازم (تقریبن) به ترتیب سختی مرتب شدن. اگه حس میکنید این مبحث ر به خوبی بلدید از آخرین سوال شروع کنید.
۱۳۹۷/۱۱/۲۷ · ۰۸:۰۰
سوال شب چهاردهم
۱۳۹۷/۱۱/۱۵ · ۲۲:۱۸
سوال شب سیزدهم
سلام به المپیادی های عزیزمون. خوبین؟ خوشین؟سلامتین؟ خدا رو شکر.
۱۳۹۷/۱۱/۱۳ · ۰۱:۲۰
cf extension
سلام ملت.
حال می کنین امسال چقد فعالیم؟
در همین راستا امروز بعد جدیدی از شاز رو افتتاح می کنیم. ما استارت یه سایت رو زدیم که هدفش اینه که مطالبی که بهمون کمک می کنه رو جمع کنیم و از زبون های دیگه ترجمه کنیم به فارسی که بتونیم راحت تر ازشون استفاده کنیم. فعلا هم بنا به اینه که سوال های CF رو که می زنیم ترجمه کنیم تا کسایی که بعد از ما می زنن بتونن راحت تر باشن. ( در همین راستا یه اکستنشن زدیم که اگه نصبش کنین و برین تو CF ، سوالایی که ترجمه شدن به فارسی میان براتون ) از این لینکه می تونین اکستنشن رو نصب کنین.
نکته : این یه کار همگانیه و اگه مشارکت شما کم باشه سریع شکست می خوره ( و ما هم دیگه از این همه شکست خسته می شیم و شاز رها میشه ). ولی اگه این ۳۰۰ دنبال کننده شاز هر کدوم ۵ تا سوال ترجمه کنن کسر خوبی از CF ترجمه می شه ! برای ترجمه سوال هم بعد نصب اکستنشن بالای سوال یه دکمه ترجمه داره که هدایتتون می کنه به گیت هاب . اگه سوالی حین ترجمه پیش اومد تو دیسکورد بپرسین جواب میدیم . بازم می گم که اگه هر سوالی که میزنید رو ترجمه کنید سال پایینی هاتون CF فارسی خواهند داشت!
احتمالا با گیت هاب به مشکل بخورید ولی خوبه که باهاش ور برید چون بعدا هم ممکنه به دردتون بخوره.
حرف دیگه ای نیست. خدافظ
آپدیت ۱:
SGU هم هندل شد!
نویسنده: حمیدرضا کلباسی (با کاپی میکائیل)
۱۳۹۷/۱۱/۱۰ · ۲۰:۰۴