صفحه ۵
الگوریتم هفتگی-درخت بازه‌ای
پس از سال ها پست الگوریتم هفتگی ر میذاریم :)) این پست قراره خیلی طولانی باشه چون سگمنت‌تری سوالاش متفاوت و زیاده.
پیشنهاد میشه که اگه سوالیو نمیتونید حل کنید توتوریالش ر بخونید.
مطالبی که خوبه بخونید اگه سگمنت‌تری بلد نیستید:
سوالات آسون تو لینک۳ گذاشته شدن و ما از سوالات متوسط شروع میکنیم. ترتیب خاصی هم ندارن سوالا.
۱۳۹۸/۰۲/۲۸ · ۱۳:۵۳
قبل مرحله ۲
خب سلاام! خوبین؟
حس میکنم که این دو روز باید تایم مهمی برای المپیادیا باشه و خب روحیه خوب داشتن، یه چیزیه که حداقل من فک میکنم خیلی مهمه تو المپیاد کامپیوتر و اساتید دوره هم همین رو میگفتن بهمون! روحیه هم بحثش فک نمیکنم خیلی مخصوص به یه گروه خاص باشه! هم کسایی که مثلا تهرانین و معلم و دوست المپیادی زیاد دارن درگیرش ممکنه باشن چون آدمای قوی تر از خودشون رو احتمالا زیاد دیدن، هم آدمایی که معلم کم داشتن یا نداشتن و دوست المپیادی هم همینطور، چون سطح خودشونو سخته بسنجن.
خب من تقریبا آدم موفقی نبودم تو مرحله دو، واقعا لب مرز قبول شدم، ولی خب شاید بتونم یه چیزایی بگم که بدرد بخوره!
اول از اینکه پست های قدیمی شاززز واقعا پست های خفنی هستن بابت روحیه دادن و این حرفا! مثلا این پست خیلی خوبه. یکی از چیزایی که برای من خیلی جالب بود این لینک هستش. الان متاسفانه پست مربوط بهشو پیدا نکردم شما وقت داشتین میتونین یه سرچی بزنین.
دوم اینکه زمان درس خوندن و تلاش برای قوی شدنتون تموم شده الان برای مرحله 2، الان به نظر من نباید دیگه درسی چیزی بخونین، صرفا چیزایی که الان میتونین یا ممکنه بتونین تغییر بدین تو خودتون یکی اعتماد به نفس هستش، یکی روحیه و انگیزه ی خوب داشتن و حال خوب، و یکی هم استراتژی خوب داشتن.
که دو مورد اول رو خودتون میتونین تلاش کنین براش یا بخواین از دوستاتون و استاداتون یا افراد رندم حتی که کمک کنن بهتون، اگه کمکی از من هم بر میومد بهم بگین حتما! اینکه حالتون خوب باشه به نظرم خیلی مهمه، چه قبول بشین چه نشین چند ماه یا سال دیگه که به قضیه نگاه کنین خیلی دید خوشگل تری دارین نسبت به مرحله دو اگه الان حالتون خوب باشه!
مورد سوم که استراتژی خوب داشتن هست برای افراد مختلف فرق میکنه و اگه تا حالا تو آزمونای آزمایشی یه سری چیز رو تست کردین خیلی خوبه میتونین بهترینشو انتخاب کنین، کسایی هم که اینکارو نکردن میتونن از افرادی که با تجربه ترن نظر بخوان تا کمک کنن بهشون.
چیزایی که من حس میکنم باید رعایت کنین ایناست:
تایم خوااب خیلی مهمه فک میکنم، اگه شب دارین این پستو میخونین که واقعا . بگیرین بخوابین، من اینجور موقع ها یکم بیخوابی و اینا میزد به سرم و میتونستم نیم ساعت یه ساعت اینا بیشتر از حد معمول برنامه ریزی کنم برای خواب که کم نخوابم مثلا.
خوراکی و شوکولات خیلیییی مهمه، اینجوریه که ملت ممکنه ازین شوکولات خفنا بیارن و شما دلتون بخواد بعد ناراحت شین که شوکولات ندارین یا خفن نیست شوکولاتتون که این خیلی بده، سعی کنین شما اون آدم شوکولات خفن آورنده هه باشین. آب هم ببرین و هر از چندگاهی مقداری بنوشید چون استرستون را کاهش میده. البته زیادیشم خوب نیست :)
این مورده یکم شخصیه ولی پیشنهاد میکنم چک نکنین برگتونو بعد آزمون تستی، من خودم هر دو سال فک کنم چک کردم ولی اگه چک نمیکردم حس میکنم ممکن بود نتیجم بهتر شه. چون شما دارین دو تا آزمون مستقل میدین که توش باید مستقل از اون یکی آزمون بهترین خودتون باشین.
برای اینکه رو هر سوال تستی چقد فک کنید و چجوری مطمعن شین از جوابتون و چقد تایم بزارین و چجوری ددلاین بزارین برای تست ها فک کنین قبل آزمون خوبه. حواستون باشه که زمان کم نیارید و روی همه سوالا به اندازه کافی وقت بذارید.
برای آزمون های تشریحی هم خیلی مدیریت وقتتون مهمه، سعی کنین براش برنامه ریزی کنین!
سومین و مهم ترین نکته ای که میشه در مورد این دو روز بهتون گفت اینه که استرس نداشته باشید. آروم آروم آروم. دلیلی برای نگرانی و استرس وجود ندارد. شما تمام تلاشتون را کردید و اگر برگردید به عقب هم دوباره همین مسیر را میایید. وقتی بهترین کاری که می تونستید را انجام دادید چرا می خواهید با اضطرابب، بیخودی خرابش کنید. مطمئن باشید اگر یه دلیل وجود داشته باشه که شما نتونید نتیجه زحماتتون را بگیرید همین استرسه. اصلا به آزمون فکر نکنید و بیخودی برای خودتون بزرگش نکنید. یه آزمون معمولیه مثل بقیه آزمونا. شما درس خواندید و تلاش کردید و الان می خواهید خودتون را یه محکی بزنید. همین و فقط همین. زندگیتونو بکنید و از این دو روزتون لذت ببرید. وسطش یه ازمونی هم بدید.
باز با تموم این حرفا می دونم که هم قبل از آزمون استرس دارید و هم وقتی آزمون شروع میشه و هم وقتی تموم میشه. بالاخره کاریش نمیشه کرد. این استرس را هر چه قدر هم کنترل کنید تا یه حدیش واقعا اجتناب ناپذیره. در این مواقع فقط یک توصیه میشه کرد و اونم اینه که به خدا توکل کنید. مطمئن باشید که هیچ کس جز خدا نمی تونه ارامتون کنه و بهتون ارامش بده و واقعا هم اگر کمک بخواهید ازش و به یادش باشید حتما اروم تر میشید و ازمون بهتری میدید. اگر دوست داشتید گوش دادن به قران هم ادمو اروم می کنه :)))
وقتی رفتید سر آزمون اگر سوالا سخت بود هول نشید. بدونید وقتی یه سوال سخته برای همه سخته و نه فقط برای شما. البته جا داره بگم که اگر سوالا براتون راحت بود هم مغرور نشید. شما برای گرفتن نتیجه زحماتتون موظفید که برید سر آزمون و بدون توجه به هیچ عامل خارجی، بهترین خودتون را سر آزمون بذارید و مطمئنم که اگر روی همین کار تمرکز کنید، به خوبی انجامش می دید و حسابی می ترکونید. برید و بترکونید. بهترین ها منتظرتونه :))))
نویسنده ها: میکائیل قربانی و امیرمحمد ایمانی
۱۳۹۸/۰۲/۱۰ · ۱۲:۲۳
اتماام آزمون ۴ ام شاززز
سلاام،
بالاخره آزمون 4 ام شاززز تموم شد (تمومممم شد)،
خوشبختانه (و بدبختانه برای مصحح) تعداد شرکت کننده های این آزمون به نسبت خوب بود. تقریبا 80 نفر از طریق بات تلگرام آزمون دادن و نزدیک 45 نفر هم از طریق مدرسشون. برگه ها تصحیح شدن و نمره ها اعلام شد به هر فرد!
در کل آزمون روز اول (تستی) طبق نظر اکثریت نسبت به تستی مرحله دو آسون تر بود. و تشریحی هم تقریبا هم سطح یا یکم سخت تر از تشریحی پارسال بود.
۱۳۹۸/۰۱/۲۴ · ۱۵:۵۸
تئوری ۴
سلاااام.
ما میخوایم تو این نوروز (البته با تاخیر:D) یه آزمون مرحله 2 ای بگیریم.(احتمالا تستی هم داشته باشیم)
این آزمون نسبت به سه تای قبلی ای که گرفتیم فرقش اینه که احتمالا جامع تره و اطلاع رسانی بیشتری احتمالا بشه.
امیدوارم بتونیم تهش یه رنکینگ از نمره های نفرات برتر داشته باشیم. پس حتما این آزمونو بدین که بتونین خودتونو بسنجین و مقایسه کنید با دیگران.
اگه از مدرستون بیشتر از یک نفر میخوان این آزمون رو بدن سعی کنید که تو مدرسه آزمون بدین و از طرف مدرستون ثبت نام کنید تا یکم رسمی تر بشه آزمون براتون.
احتمالا تایم این آزمون 17 ام تا 19 ام فروردین 98 باشه.
اگه تغییری پیش اومد اطلاع میدیم. در مورد نحوه ی ثبت نام هم همینطور:))
موفق باشین:D
آپدیت 1: هووراااا بالاخره آزمون شروع شد. حداقل 4 روز برای دادن آزمون فرصت دارید. به نفرات اول تا دهم به صورت تصادفی پیتزا داده میشه:D
آپدیت 2: حتما حتما اسماتونو واقعی بنویسید. اگه از اسم های فیک استفاده کنید خوب نیست:(
آپدیت 3: هیچوقت قبول نکنین که برگه تصحیح کنین:( میمیرین:(
میکائیل قربانی
۱۳۹۸/۰۱/۰۸ · ۲۳:۱۷
الگوریتم هفتگی-نظریه اعداد
این پست یکم سنگینه. چون نظریه اعداد مبحث کوچیکی نیست. اما سعی کردیم جمعش کنیم. لازمه لینک هایی که گفته شده ر بلد باشید تا بتونید سوال ها ر حل کنید. همچنین تو خود لینک ها هم سعی کنید چندتا از سوالای انتهای صفحه‌شون ر بزنید!
مباحثی که خوبه بلد باشید:
سوالات ترتیب خاصی ندارن!
مهدی جعفری :(
۱۳۹۷/۱۲/۲۶ · ۱۶:۲۴
الگوریتم هفتگی-مولفه های قویا همبند و مرتب‌سازی توپولوژیک
۱۳۹۷/۱۲/۱۶ · ۱۸:۲۰
راه حل های آزمون عملی دوم شاززز
پیشنهاد میشه اگه آزمون رو ندادید اول سوالا رو بخونید و خودتون روش فکر کنید!
سوال اول:
اول باینری سرچ روی جواب میزنیم. فرض کنید میخوایم چک کنیم که آیا جواب مسئله میتونه کمتر مساوی 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 آزمون رو برگزار کنیم. کوئرا بهمون کمک کرد و آزمون روی سایت کوئرا برگزار خواهد شد که از اینجا میتونید ثبت نام کنید.
۱۳۹۷/۱۲/۰۸ · ۲۳:۲۲