یه مسیر برای یه المپیادی کامپیوتر :)

[Retr026]

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

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


یکم از خودم بگم
من هاشمی نژاد 1 درس میخوندم و از تابستون نهم به دهم المپیاد کامپیوترو رسما شروع کردم. سال دهم خیلی عجیبی داشتیم ولی گذشت و توی تابستون دهم به یازدهم فوق العاده خفن داشتم عمل میکردم و جلو میبردم و تا آخر تابستون همین وضع بود ولی به یه سری دلایل تقریبا شخصی المپیاد نخوندن برای من به صلاح بود

 

[Retr026]

المپیاد کامپیوتر یه المپیادیه که تا یه حد زیادی از بقیه المپیادا متفاوته و تنها وجه مشترکش اینه که ترکیبیات المپیاد ریاضی رو هم میخونن
المپیاد ها معمولا به دروس دانشگاهی و دروس مدرسه کمک خیلی خوبی میکنن. المپیاد کامپیوتر فقط و فقط توی دانشگاه کارتون رو آسون میکنه و کمکی به کنکور نمیکنه ولی از اون طرف مهمترین درس مهندسی کامپیوتر و علوم کامپیوتر که داده ساختار ها و طراحی الگوریتم میشه رو قورت دادین و خوراکتونه و بنیه برنامه نویسیتونو خیلی قوی میکنه و اگه مدال باشین و یه زبون برنامه نویسی بلد باشین تمام کمال که سه چهار ماه بیشتر طول نمیکشه بعدش میتونین توی یه شرکت همون اول ورود به دانشگاهتون به بازار کار برین و پول در بیارین
المپیاد کامپیوتر اصلا حفظی (اگه از قضایای گراف صرف نظر کنیم!) نیس و حجم مطالبی که یاد میگیرین کمه. اون چیزی که المپیاد کامپیوتر نیاز داره قدرت حل مسئله اس و ایده زدن و خلاقیت محض.
و خب اولین چیزی که به ذهنتون میرسه اینه که خب یعنی قراره 24 ساعته پای کامپیوتر باشیم؟
متاسفانه جواب سوالتون خیره و تقریبا نصف زمانتون صرف کد نویسی میشه و نصفه دیگه رو سوال تئوری حل میکنید
اما این تئوری و ترکیبیات المپیاد ریاضی که درس میدن و مجبوریم برای مرحله 1 و مرحله 2 و حتی نهایی دوره بخونیم ولی تو جهانی اصلا نیستن چه فایده ای دارن؟ مرض دارن گذاشتن؟

 

[Retr026]

خب بزارین اول مباحث المپیاد کامپیوتر رو براتون بگم
مثل باقی المپیاد که درساشون شاخه شاخه میشن مثلا المپیاد شیمی میشه شیمی تجزیه و آلی و....
کامپیوتر 4 دسته داره :
1- برنامه نویسی
2- الگوریتم
3- ترکیبیات
4- گراف
که به اولی و دومی میگن عملی و به سومی و چهارمی میگن تئوری
برنامه نویسی شامل یاد داشتن کامل سینتکس سی پلاس پلاسه (نکته : برای برنامه نویسی فقط میتونین از C++ استفاده کنید! پایتون و جاوا و یا چمیدونم هر زبان دیگه ای مورد قبول نیست در المپیاد) و داده ساختار های اون مثل هیپ و کتابخونه های معروف و فانکشن های باینریش و خب نسبت به بقیه حجمش کمتره واقعا و سینتکس رو راحت میشه یاد گرفت
الگوریتم که واقعا مفصله و برای شروع یه بیسیک از تعاریف گراف بلد باشین واقعا عالیه
چهارمی گراف برای م1 و م2 و م3 نیازی ندارید و فقط برای نهایی دوره شما میخونید. گراف در اصل زیرمجموعه گسسته محسوب میشه و وقتی یاد میگیرنش دید فوق العاده ای توی حل مسئله بهتون میده.
سومی ترکیبیات که دو دسته میکننش :
1- ترکیبیات تشریحی
2-ترکیبیات شمارشی(تستی هم بهش میگن به خاطر اینکه فقط توی م1 و م2 به کارتون میاد)
اول از همه شما باید ترکیبیات شمارشی رو فول باشید و بعدش میتونید ترکیبیات تشریحی رو شروع کنین و غول اصلی ترکیبیات تشریحیه

 

[Retr026]

خب ببینین الگوریتم رو واقعا نمیتونم دونه دونه بیام توضیح بدم و صرف نظر میکنم
ولی لیست الگوریتم هایی که هستن و لازم هستن برای دوره و اونایی که لازم نیستن رو از مهدی خاوری طلا دوره 32 و نقره دوره 31 پرسیدم و اینجا میزارم :

divide and conquer میخواد
DFS, bfs, MST میخواد
تور اویلری میخواد
djikstra میخواد
spfa نمیخواد
bellman ford میخواد
Floyd Marshall خیلییی میخواد
topological sort میخواد
scc میخواد
2-sat میخواد
backtrack برای م3
maximum matching تطابق توی نهایی ها ازش سوال نیومده ولی ممکنه بیاد
meet in middle آره تقریبا
sos میخواد
submask میخواد
دیپی درختی میخواد
bitmask میخواد
Rmq میخواد
dsu میخواد
lca میخواد
sack , gooni میخواد
Fenwick میخواد
sqrt میخواد
mo میخواد
sweep line ایده اش رو بلد باشیم
heavy light ایده اش رو بلد باشیم
centroid decomposition شاید
seagment tree بایدیه
bitset باید بلد باشیم
trie میخواد
kmp میخواد
z نمیخواد
hash میخواد
suffix array میخواد
lcp میخواد
suffix tree میخواد
aho میخواد
fft نمیخواد
flow برای دوره طلا شاید
A* نمیخواد
Kuhn نمیخواد

 

[Retr026]

خب برای گراف (و ترکیبیات) کلا کلاس برید و تک و تنهایی خوب نیس جلو ببرید
برای گراف منبع اصلی و مهمترینش که باید تا قبل دوره همه تمرین هاشو بزنید کتاب گراف وست هست
ترجمه هم داره ولی به درد نمیخوره و باید زبون اصلی بخونید و حل کنید
کتاب گراف علیپور که جلدش آبی هستش و یه گراف 5 ضلعی روشه هم کتاب فوق العاده ای هستش

 

[Retr026]

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

 

[Retr026]

خب بعد المپیاد کامپیوتر برای رسیدن به دوره اش باید سه مرحله رو رد کنید!
م1 : واقعا ساده اس. اگه سوالای سال قبل هم زده باشین قبل آزمون که نور الا نوره و 15 سوال خیلی ساده اس و 2 ساعت وقت
م2 : از 160 نمره محاسبه میشه . 80 نمره اش میشه 20 تا سوال تستی روز اول و 4 تا سوال تشریحی روز دوم
تستیش رو واقعا باید کار کنید و ساده نیستن ولی میتونین صد بزنین و خودم 70 تا 75 درصد زده بودم یادم میاد
برای تشریحیش واقعا باید نوشتارتون دقیق و کامل و عالی باشه و نه اینکه بد بنویسین یا بدخط باشه
ولی میشه ازشون گذشت به سلامتی
کف م1 حدود 20 تا 35 درصده . یعنی 6 تا درست بزنی قبولی! و خب انتظارم اینه بالا 10 تا درست زده باشین
کف م2 متغیره . سال های پیش حدود 67 و خرده ای بودن حدودا و امسال که واقعا ساده تر بود 83 بود
ولی سال های پیش اگه شما تستی رو صد میزدین و تشریحی برگه خالی تحویل میدادین قبول بودین ))))))))
اما هدفتون توی م2 باید گرفتن نمره خیلی خوب باشه چون رو نمره م3 تون تاثیر داره
م3 : این مرحله 3 تنها کاربردش اینه المپیادی های ریاضیو فیلتر کنه و کد نویسیتون آغاز میشه )))) و دو سوم سوالا رو حل کنی کف رو آوردی
مباحث مرحله 3 فقط دانش ترکیبیاته و سی پلاس پلاس و اگه بک ترک و دیپی بلد باشین عالی میشه
م1 حدود 800 تا 1000 نفر قبول میشن
م2 از بین تستی ها 200 نفر برتر برگه تشریحیشون تصحیح میشه و از بین 200 تای برتر 80 نفر انتخاب میشن برای م3
م3 هم نصف این 80 نفر فیلتر میشن و میرن برای دوره تابستونه
البته بگم المپیاد کامپیوتر یه میان ترم داره به اسم کات برنز که چهار درس اصلی دوره اس و باید پاس کنیشون
اگه دو تا از چهار درس بیفتی برنز آخر بهت میدن و نمیتونی نهایی شرکت کنی . اگه بیشتر از دو درس باشه فک کنم دیپلم بشی
آره خلاصه

 

[Retr026]

و خب کتاب چیا بزنیم ؟ :)
تا قبل م1 شما باید کتابای آنالیز ترکیبی خوشخوان و روش های ترکیبیات 1 رو کامل بزنید
روش های ترکیبیات 2 و آنالیز ترکیبی قدیمی ثروتی رو بزنید قشنگ به علاوه فصل های آخر آنالیزترکیبی الگو. همه اش رو نمیرسید ولی تا جایی که میتونید بزنید
البته اینا برای سال دهمه
به قول یه نفر بهترین منابع م3 خود سوالای م3 هستش
از 14 روز مونده به م3 شروع کنید بزنیدشون تموم کردینشون و آماده اید

 

[Retr026]

برای یازدهم :
گراف وست - روش 2 - روش 3 - گراف علیپور - ترکیبیات زرد کامل - تمرین های معلمتون رو بزنید حتما

 

[Retr026]

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

 

[Retr026]

و کانال https://t.me/Retr026_inoi هم توش لینکا و کتابا رو گذاشتم و نابه
البته دیگه قرار نیستش آپدیت بشه این کانال

 

[Retr026]

برای ویدیو دیدن :
ترکیبیات تشریحی : آفتاب
رابطه بازگشتی و لانه کبوتری : ویدیو های آلا با تدریس فیروزی
الگوریتم : ویدیو های دوره سال 96
گراف : ویدیو های دوره سال 96 + آفتاب
خفن شدن تو سی پلاس پلاس : ویدیو های دوره سال 96
لینک همه اینا رو من توی کانالم بالا گذاشتم

 

[Retr026]

خب یکم از منابع هم تحلیل کنم براتون

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

روش های ترکیبیات علیپور
این کتاب هیچ توضیحی درباره اون سرفصل یا ابزار نداده و فقط سواله. فقط اول هر بخشش یه سوال حل کرده که با نحوه حلش آشنا بشین و منطقا قبلش برید اون ابزار یا بخش رو یاد بگیرین و بعد برین سراغش
روش 1 خیلی ساده اس
اما روش 2 به طرز عجیبی یهو سخت میشه و گیرپاژ میکنین
روش 3 از روش 2 سختتره و اگه دو بار روش 2 رو زدین برین روی روش 3
روش 4 هم اصلا ندیدم کسی حل کنه حتی طلا های ریاضی

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

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

محافل ریاضی :
برای ترکیبیات و شمارش و م1 واقعا کتاب خوبیه و اگه نمیخواین بخرینش دستکم قسمت مبناش رو برید حل کنید حتما

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

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

 

[Retr026]

خب در مورد کلاسا هم بگم یکم
اگه کلاس المپیاد داره مدرسه تون حتما حتما شرکت کنیدش
اگه دنبال کلاس آنلاین هستید :
به هیچ وجه سمت جاهایی مثل طلایی ها و آیریسک نرید! این ها بیشتر هدفشون خالی کردن جیب شمایه
بهترینی که من دیدم بینشون ابرکلاس بوده که هم قیمتش خوبه و هم کیفیت کلاساش
برای تئوری پیشنهاد من اینه برید ابرکلاس
و اگه میتونین بیشتر هزینه کنید برید کلاس های آقای کاملی https://t.me/math_computer_olympiad شرکت کنید
برای عملی هم پیشنهاد میکنم دوره برنامه نویسی الگوریتمی گرینولی (اگه ++C بلدین که فقط پیشرفته اش رو شرکت کنید) رو شرکت کنید و هر مبحثیو بخونین و بعد برید تا سر حد مرگ ازش سوال حل کنید تا یاد بگیرینش
دوره های دیگه گرینولی واقعا به درد نمیخورن به استثنا این دوره برنامه نویسیش و دوره پاسخنامه م2 اش و یه دوره ترکیبیات که قرار بوده بزارن ولی نمیدونم الان هست یا نه و اگه بود چیز قشنگی میشه ولی خب فعلا نیس.

و همینا

 

[Retr026]

یکم هم درمورد جو بگم :

توی المپیاد کامپیوتر یه چیز داریم تحت عنوان دلقک
خب به یه سری از آدما که توی المپیاد میان مسخره بازی در میارن و چه مدونم درباره م2 فلان آدم میان صحبت میکنن و پر از مطالب اضافه ان و توی غاززز فعالن میگیم دلقک و فقط ک*شعر میگن
و خب این دلقک ها بعضی هاشون طلا هم هستن ولی عمدتا آدم های جالبی نیستن و سعی کنین ازشون دوری کنید چون خیلی تو حاشیه میپلکن
و خب این دلقک ها توی بقیه المپیاد ها هم هستن ولی توی کامپیوتر به لطف غاززز و کانتست و نمایان بودن روند کد زنی هر کس توی codeforces باعث شده که راحت درباره اینا بحث کنن که مثلا آی اگه X سابمیت بد نمیکرد الان لجندری گرند مستر بود یا اگه کل گرند مستر ها رو ازشون بپرسین حفظه اونا رو
و این آدما خیلی منو اذیت میکردن توی المپیاد
سعی کنید دلقک نباشید چون یه دلقک که کلی از حاشیه ها رو میدونه وقتش رو تلف زیاد میکنه

 

[Retr026]

سعی کنید یه هم المپیادی خوب پیدا کنید واقعا
که پیشرفت کنین نه اینکه دلقک بازی در بیارین

امیدوارم توی مسیری که به صلاحتونه و عاشقشید قدم بردارید! چه با المپیاد چه بی المپیاد