هویج شگفت انگیز

نوشته های محمد مهدی شکری

هویج شگفت انگیز

نوشته های محمد مهدی شکری

برای ICPC چه می‌بایست کرد؟

جمعه, ۱۴ تیر ۱۳۹۸، ۰۸:۳۷ ق.ظ

برای ICPC یا بطور کلی Competitive Programming، سه تا موضوع هست که به ترتیب اهمیت میتونیم بگیم: توانایی حل مسئله ، توانایی پیاده سازی الگوریتم (سریع و بی باگ)، دونستن راه حل مسئله‌های معروف.

در ادامه‌ی مطلب اول جزئیات هر کدوم و منابعش و نحوه‌ی تمرینش رو میگم، آخرش هم اولویت‌بندی و مراحل پیشنهادیم رو میگم.



بخش سوم که دونستن راه‌حل مسئله‌های معروفه خودش دو بخش الگوریتم و غیر الگوریتم (گراف و ترکیبیات و اینا) داره. برای بخش ترکیبیاتیش، خوبه که با یسری چیزا حداقل آشنایی وجود داشته باشه؛ مثلا سرفصل‌های کتاب‌های "ترکیبیات علیپور" و "استراتژی‌های حل مسئله" (بجز بخش های ریاضیش البته! مثل جبر و هندسه و نظریه اعداد) و "گراف وست" (تا آخر ۳.۳). به نظرم این‌ها چون پایه‌ای هستن باید زودی بسته بشن. این سرفصل‌ها توی درس‌هایی از دانشگاه مثل "ساختارهای گسسته" و "ترکیبیات" و "گراف" هستن؛ اگه هنگام اون درس‌ها این کتاب‌ها هم مطالعه بشه خیلی بهتر هم هست چون منظم‌تر پیش میره.


حالا برای تمرین بیشتر غیر الگوریتم و خارج از کلاس‌های دانشگاهی، برای گرافش فقط کتاب وست رو توصیه میکنم... تا آخر بخش ۳.۳ میشه همه‌ی مسائلش رو حل کرد و خوب هم هست واقعا. برای ترکیبیات و اینا ترکیبیات علیپور، بعد استراتژی حل مسئله و "۱۰۲ مسئله ی ترکیبیات" خوبه چون پر از سوالای سخت هستن (این توانایی حل مسئله رو هم قوی میکنه!)

البته "روش‌های ترکیبیاتی" هم خیلی شنیدم کتاب‌های خوبی هستن، من چون نمی‌شناسمشون نگفتم؛ میشه معادل‌سازی کرد!


برای پیاده سازی و همچنین دیدن راه حل های مسئله ی معروف برنامه نویسی، اول از همه برنامه‌نویسی رو خوب یاد بگیر! طوری باشه که اگه راه حلی برای یک سوال پیدا کردی، دیگه توی پیاده‌سازیش مشکلی نداشته باشی. این فرایند یادگیریه بدون تمرین نمیشه...  اگه خواستی می‌تونی Quera College رو شروع کنی و پیش بری که هم آموزش داره و هم تمرین، می‌تونی هم از منابع دیگه‌ی آنلاین و غیر آنلاین یاد بگیری زبان رو و خودت کنارش تمرین کنی.

 برای تمرین تا می‌تونی از سوال‌های آنلاین که پیدا میشه (مثل Codeforces و Quera) بزن! از سوال‌های مسابقات قبلیشون بزن برای تمرین برنامه‌نویسی. بعدش برای حرفه‌ای شدن، از مهم‌ترین کارایی که باید بکنی اینه که همه‌ی مسابقه‌ها رو بدی! تلاش کن تا می‌تونی مسابقه‌های برنامه‌نویسی رو بدی، حالا codeforces هست، quera هست، atcoder و csacademy هست، ... بعد و شاید مهم‌تر از دادن کانتست‌ها، اینه: سعی کن از همه ی سوال های کانتست ها استفاده کنی! موقع کانتست هرچند تا سوال حل کردی به کنار، مهم‌تر از اون اینه که بعدش بشینی رو بقیه سوال های کانتست که حل نکردی فکر کنی. هرجا خیلی به یه سوال فک کردی حل نشد و ناامید شدی ازش، tag سوال رو ببین یا از یکی که حل کرده پیش نیاز های سوال رو بپرس اگه چیزی بود که بلد نبودی برو یاد بگیر. ترجیح خیلی زیاد بر اینه که نری راه حل بخونی. اگه کسی رو میشناختی که سوالی که روش گیر کردی رو زده باشه، ازش کمک بگیر که بت بگه چجوری فک کنی که به جواب برسی، نه اینکه جوابو بت بگه. این برای توانایی حل مسئلس!


برای این که بتونی ICPC بدی بطور خاص، باید روی خیلی از الگوریتم‌ها تسلط داشته باشی. یسری جاها تو Quora و Codeforces لیست مباحث ICPC رو نوشتن؛ اونا رو خوبه که یک نفر از هر تیم حداقل بلد باشدش. کتاب Competitive Programming هم هست که لیست کرده و همرو درس داده و از همشون سوال داده. سایت cp-algorithms هم خیلی خوب و کامل به همراه پیاده‌سازی خوب الگوریتم‌ها رو توضیح داده؛ مشکلش اینه که بیشتر مرجع هست تا منبعی که سیر یادگیری داشته باشه؛ یعنی وقتی یه الگوریتمی رو خواستی بیاموزی از اون خوبه بیاموزی ولی اگه بری و شروع کنی همه مباحثش رو یاد بگیری خب فایده‌ای نخواهد داشت، چون خیلی ترتیب خوبی نداره.

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


توانایی پیاده سازی ۷۰٪ به مجموع تعداد خط های کدی ربط داره که زدی! نه تعداد کد هایی که accept کردی. خلاصه که هر الگوریتم یا چیز برنامه نویسی ای که یاد گرفتی برو کدشو بزن و حداقل ۵-۶ تا سوال ازش accept کن. اون ۳۰٪ دیگه به گرم بودن ربط داره! مثلن یکی دو ماه قبل از مسابقه اصلی خوبه کل‍لی کد بزنی که گرم باشی اون موقع! گرم کردن هم کار خاصی نمیخواد، همینجوری کد بزنی گرم میشی. مثلن بچه های تیم المپیاد جهانی یه سالی، یه دوره‌ای برای گرم کردن نشستن یه تعداد زیادی a, b دیو۲ از codeforces رو زدن با این سعی که رانگ نخورن اصلن (هرچی کد می‌فرستن اولین بار نمره کامل رو بگیره).


توانایی حل مسئله ۱۰۰٪ به مجموع ساعت هایی ربط داره که به سوال ها فکر کردی! نه تعداد یا نوع سوال هایی که حل کردی. اگه یه سوالی کلللی فکر کردی و حس کردی دیگه هیچ ایده ای نداری (و سواله پیش نیازی نخواد که بلد نباشی!)، تلاش کن ولش نکنی! چون که اونموقس که تازه ذهنت شروع میکنه ایده های جدید زدن و این از هر چیز دیگه ای برای پیشرفت توانایی حل مسئلت مفید تره!


یچیز دیگه که توی ICPC مهمه استراتژی مسابقه دادن و هم‌چنین شناختن هم‌تیمی‌هاست، که راهش اینه که تعداد خیلی زیادی مسابقه‌ی تیمی مشابه مسابقه اصلی بدید. یعنی حضوری و با ۱ کامپیوتر و با صورت سوال‌های پرینت شده و اینا. راجع به استراتژی این‌جا هم می‌تونید بخونید.



حالا که همه‌ی سرفصلا و موضوعا و منابع رو گفتم، راجع به اولویت‌بندی بین مباحث و موضوعات مختلف، من به نظرم این‌طوری هست:


۱. یاد گرفتن برنامه‌نویسی به زبان Cpp

۲. توانایی برنامه‌نویسی و ترکیبیات و گراف پایه‌ی همه‌ی اعضای تیم، در حدی که توی کانتستای Div2 کدفرسز همه بتونن ۳ تا سوال رو حل کنن. تا به این برسید باید همش تمرینای آنلاین و کتابا رو حل کنید.

۳. بعد از دو تای بالا، دیگه باقی وقت رو باید روی تقویت حل مسئله و مباحثی که بلدید بذارید و استراتژی، با تمرکز خیلی زیاد روی الگوریتم و برنامه‌نویسی. مثلا اگه اون آشنایی کلی با ترکیبیات و گراف رو پیدا کردید، ۸۰٪ وقتتون رو روی برنامه‌نویسی و الگوریتم و اینا بذارید، ۲۰٪ روی ترکیبیات و گراف.


در نهایت، من مدیر محصول Quera College هستم و به نظرم این دو دوره‌‌ی تفکر الگوریتمی مقدماتی و پیشرفته که تازه حاضر شده منابع مفیدی هستن.(انصافاً!) دیروز یک پست ویرگول راجع به ۶ ماهی که از کالج گذشت و توضیحات قالبش نوشتم، اگه خواستید ببینید.

البته به سطحتون بستگی داره. اگه خیلی خوب برنامه‌نویسی رو بلدین (بخش ۱ و ۲ لیست بالا رو اوکی‌اید) دوره‌ی اول به دردتون نمی‌خوره؛ ولی اگه نه می‌تونم بگم خوب شما رو به تقریبا آخر بخش ۲ می‌رسونه. دوره‌ی تفکر الگوریتمی پیشرفته هم برای یاد گرفتن پیشرفته‌تر و عمیق‌تر خوبه و شما رو تا جای خوبی از الگوریتم‌ها جلو می‌بره. شاید بهترین ویژگیش هم سرفصل‌بندی و سِیر آموزشی‌اش به همراه تمرین‌هاش هست که براش خیلی صرف شده تا هر قدمش مفید باشه. من فکر می‌کنم تیمی که همه‌ی اعضاش این دو تا دوره رو خوب و کامل بگذرونن راحت می‌تونه توی ۲۰-۳۰ تا تیم اول regional ایران بشه. ولی خب تموم کردن این دوره‌ها کار کمی نیست... کلی وقت و تمرکز می‌خواد!


امیدوارم مفید واقع بشه. 😊

۹۸/۰۴/۱۴ موافقین ۲ مخالفین ۰

نظرات  (۱)

خیلی ممنون از اینکه این پست رو گذاشتید
پاسخ:
خواهش می‌کنم!
امیدوارم به درد بخوره.

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی