این ریپو (Repository) برای ثبت سوال و جواب‌های قرار گرفته در تاپیک الگوریتم (DSA: Data Structures & Algorithms) گروه کانون برنامه‌نویسی پرند ایجاد شده؛ علاوه بر این‌ها، توضیح مختصر راجب ICPC و مسابقات الگوریتم، منابع موجود و بانک سوالات نیز تعبیه شده؛ سعی میشه با توجه به منابع روز و مورد نیاز استفاده کننده‌ها، لیست منابع و محتویات توضیحات نیز به روز بشن.
دوستانی که بار اولشونه از گیت‌هاب استفاده می‌کنن و می‌خوان با گیت و گیت‌هاب آشنایی پیدا کنن، می‌تونن از لینک‌های زیر کمک بگیرن:
https://www.theodinproject.com/lessons/foundations-setting-up-git
https://www.theodinproject.com/lessons/foundations-introduction-to-git
https://www.theodinproject.com/lessons/foundations-git-basics
سوال‌ها به ترتیب قرارگیری در گروه و ریپو شماره‌گذاری می‌شوند.
به طور مثال 01 به معنی فایل اولیۀ قرار داده شده در گروه و ریپو است؛ در ادامه به بقیۀ دسته‌بندی‌ها می‌پردازیم:
سختی سوال‌ها بعد از شماره‌ی آن در اسم ذکر شده که به ترتیب زیر است:
| پسوند | میزان سختی |
|---|---|
| A | آسان |
| B | متوسط |
| C | سخت |
01A
حرف (اِی) بعد از شماره‌ی سوال به معنای آسان بودن سوال است.
سوالات الگوریتم موضوع‌های زیادی دارن و درکل موضوع مهم در اون‌ها، طرز فکر و طریقۀ پیاده‌سازی هست. البته که گاهی یک مسئله می‌تونه به چند روش مختلف حل بشه، ولی به طور معمول در ۹ دسته زیر میشه اون‌ها رو طبقه‌بندی کرد (با اسم الگوریتم‌ها به مرور زمان آشنا می‌شین و جای نگرانی نیست؛ یه سری از اون‌ها رو شایدم استفاده می‌کنین و فقط اسمشونو نمی‌دونین):
الگوریتم‌های تغییر و پیمایش بر روی رشته‌ها، رابطه‌ی نزدیکی با الگوریتم‌های جستجو دارد؛ موضوع طریقۀ پیاده‌سازی در این نوع سوال‌ها پررنگ‌تر است؛ مثال الگوریتم‌ها:
Knuth Morris Pratt(KMP), Z algorithm, Suffix arrays/Suffix trees. These are bit advanced algorithms.
این دسته از سوالات ارتباط نزدیکی با نظریۀ ماتریس‌ها و ساختمان داده دارند؛ به ویژه درخت‌ها و الگوریتم جستجو در آنها؛ مثال الگوریتم‌ها:
Breadth first search(BFS), Depth first search(DFS), Strongly connected components(SCC), Dijkstra, Floyd-Warshall, Minimum spanning tree(MST), Topological sort.
برنامه‌نویسی پویا (Dynamic Programming) در کل درنظر دارد تا از محاسبه‌ی اضافی جلوگیری کند؛ اغلب سوالات برنامه‌نویسی پویا با تکرار و با استفاده از روابط بازگشتی (Recursion) قابل حل هستند، ولی اینگونه حل بهینه نبوده و با پیاده‌سازی‌های خاص، روش‌های بهینه برای اینکار وجود دارد؛ مثال الگوریتم‌ها:
Standard dynamic programming problems such as Rod Cutting, Knapsack, Matrix chain multiplication etc.
مجموعه روش‌های رسیدن به اعداد مورد نظر با توجه به تئوری‌های این حوزه؛ به جای استفاده از متد Brute-force (در نظر گرفتن تمام حالت‌ها و ادامه دادن تا رسیدن به جواب) و امتحان تمام حالت‌های مساعد با شرط سوال، از شرط سوال عددهای مدنظر را تولید می‌کنیم؛ این مجموعه روش‌ها ارتباط نزدیکی با برنامه‌نویسی پویا دارند؛ مثال الگوریتم‌ها:
Modular arithmetic, Fermat’s theorem, Chinese remainder theorem(CRT), Euclidian method for GCD, Logarithmic Exponentiation, Sieve of Eratosthenes, Euler’s totient function.
الگوریتم‌های حریصانه (Greedy algorithms) با توجه به اختصاص معیار (Heuristic value)، در هر مرحله سعی می‌کند بهترین گزینه برای الگوریتم را انتخاب کند؛ مثال الگوریتم‌ها:
Standard problems such as Activity selection.Standard problems such as Activity selection.
مجموعه الگوریتم‌های مربوط به جستجو در یک دنباله؛ مثال الگوریتم‌ها:
Binary search, Ternary search and Meet in the middle.
ساختمان‌های داده پایۀ حل مسائل الگوریتم هستند و انتخاب نوع داده درست در حل سوال آنچنان مؤثر است که معمولاً اینگونه سوال‌ها در دسته‌بندی مختص ساختمان داده قرار می‌گیرند؛ مثال از داده ساختارها:
Data structures (Basic): Stacks, Queues, Trees and Heaps. Data structures (Advanced): Trie, Segment trees, Fenwick tree or Binary indexed tree(BIT), Disjoint data structures.
بخشی از سوالات الگوریتم مربوط به مسائل ریاضی و به ویژه هندسه است؛ ولی به طور معمول دانش زیادی از ریاضی و هندسه مورد نیاز نیست و از قواعد ساده‌ی آن استفاده می‌شود؛ مثال:
Graham-Scan for convex hull, Line sweep.
مجموعه سوالات الگوریتم که با توجه به قواعد و شرط‌های زیاد برای اجرا در این دسته قرار می‌گیرند؛ سوالات مربوط به بازی‌هایی مثل شطرنج با شرایط خاص در این دسته هستند؛ مثال‌ها:
Basic principles of Nim game, Grundy numbers, Sprague-Grundy theorem.
| موضوع | پسوند |
|---|---|
| Graph | G |
| String | S |
| Search | R |
| Number Theory | N |
| Dynamic Programming | D |
| Greedy | G |
| Data Structure | T |
| Geometry | M |
| Game Theory | A |
01A-M
سوال هندسۀ ساده
04B-GT
سوال ساختمان داده و گراف متوسط
مسابقات بین‌المللی برنامه‌نویسی دانشجویی (ICPC) همه ساله به عنوان یکی از مهم‌ترین و معتبرترین مسابقات برنامه‌نویسی در سطح جهان برگزار می‌گردد؛ این مسابقات تا سال ۲۰۱۸ از سوی انجمن ماشین‌های محاسباتی و با پشتیبانی شرکت‌های بزرگی چون IBM برگزار می‌شد و با نام ACM-ICPC خوانده می‌شد. این مسابقات در ایران به اختصار به مسابقات ای‌سی‌ام معروف است. تیم‌های شرکت‌کننده در این مسابقات، دانشجویان دانشگاه‌های سرتاسر جهان هستند که ابتدا در مسابقات منطقه‌ای شرکت می‌کنند و سپس تیم‌های برگزیده جواز حضور در فینال را کسب می‌نمایند؛ مسابقۀ فینال معمولاً در اوایل بهار هر سال برگزار می‌شود؛ مسابقات منطقه‌ای غرب آسیا از سال ۱۳۷۸ تا کنون (به جز سال ۱۳۹۰) در دانشگاه صنعتی شریف برگزار شده است؛ مسابقه منطقه‌ای غرب آسیا عموماً در اواخر پاییز هر سال برگزار می‌شود.
ویدئوی (یوتیوب) کامل برگزاری مسابقات فینال ICPC 2022 Dhaka اینجا
در چنین مسابقاتی علاوه بر تسلط بر یکی از زبان‌های برنامه‌نویسی C++ ،Java ،Kotlin ،Python و C، (البته تضمین می‌شود تمام سوال‌ها به وسیلۀ C++ ،Java و C قابل حل باشند) مباحثی نظیر طراحی الگوریتم و ساختمان داده‌ها بسیار تأثیرگذار می‌باشند.
مسابقات بین‌المللی برنامه‌نویسی دانشجویی یک مسابقهٔ تیمی می‌باشد؛ قوانین موجود بیان می‌کنند که هر تیم باید شامل ۳ نفر باشد؛ شرکت‌کنندگان باید در دانشگاه مشغول به تحصیل باشند و کمتر از ۴ سال سابقهٔ حضور در دانشگاه داشته باشند؛ دانشجویانی که دو بار در مرحلهٔ جهانی حضور داشته‌اند نیز نمی‌توانند در مسابقه شرکت کنند؛ مدت مسابقه معمولاً ۵ ساعت (بسته به سختی و تعداد سوال می‌تواند تغییر کند) و تعداد سوالات، معمولاً بین ۸ تا ۱۲ سؤال می‌باشد؛ تیم‌ها که تنها یک رایانه در اختیار دارند، باید جواب‌های خود را در قالب کد به سیستم داوری خودکار ارسال کنند؛ سپس برنامه‌های ارسالی توسط داده‌ها مورد آزمایش قرار می‌گیرند؛ اگر برنامه‌ای نتواند در مقابل تمام داده‌ها پاسخ درستی بدهد مورد قبول قرار نمی‌گیرد و تیم با احتساب جریمه می‌تواند برنامه دیگری ارسال کند.
برندگان گذشتۀ مسابقات و اطلاعات رقابت آن سال اینجا
تیمی برنده است که بیشترین تعداد سوال‌ها را به درستی حل کند؛ اگر رتبه‌بندی تیم‌ها برای دریافت مدال و جوایز ضروری باشد، رتبه تیم با توجه به زمان سپری شده در هر مرحله برای ارسال پاسخ درست به علاوهٔ بیست دقیقه برای هر پاسخ نادرست که قبل از هر سوال حل شده ارسال شده، تعریف می‌شود.
به عنوان مثال شرایطی را برای دو تیم آبی و قرمز در نظر می‌گیریم؛ این دو تیم از نظر تعداد سوالات حل شده با یک دیگر برابر هستند؛ تیم قرمز پاسخ‌های خود را برای سوالات A و B به ترتیب در ۰۱:۰۰ و ۰۲:۴۵ پس از آغاز مسابقه ارسال کرده‌است؛ همچنین تیم قرمز یک پاسخ غلط برای سوال C ارسال کرده‌است اما چون نتوانستند سوال C را حل کنند این پاسخ غلط در نظر گرفته نمی‌شود. تیم آبی پاسخ‌های خود را برای سوالات A و C در ۰۱:۲۰ و ۰۲:۰۰ پس از آغاز مسابقه ارسال کرده‌است. همچنین تیم آبی یک ارسال غلط برای سوال C داشته‌است؛ نتیجه به این صورت ارزیابی می‌شود که تیم قرمز در مجموع ۳:۴۵ = ۰۱:۰۰ + ۰۲:۴۵ و تیم آبی در مجموع ۰۳:۴۰ = ۰۱:۲۰ + ۰۲:۰۰ + ۰۰:۲۰ زمان برای سوالات صرف کرده‌اند؛ در نتیجه تیم آبی برنده است. (برگرفته از ویکی‌پدیا و ICPC.global)
مسابقه‌ی منطقه‌ای تهران هر سال با شرکت ۸۰ تیم از دانشگاه‌های سراسر کشور برگزار می‌گردد؛ هرساله این مسابقات در پاییز در دانشگاه شریف برگزار می‌شود؛ برای شرکت تاریخ آن را با سایت مربوطه چک کنید؛ پس از پایان مهلت ثبت‌نام، نحوه‌ی انتخاب تیم‌ها از طریق ایمیل به شما اطلاع رسانی می‌شود.
قوانین مسابقات ICPC منطقه‌ای اینجا
قوانین مسابقات ICPC فینال اینجا
برای دانلود کتاب آموزشی می‌تونین از سایت Libgenesis استفاده کنین.
منابع آموزشی انگلیسی مربوط، خیلی زیاد هستن؛ منابع معروف که برای شروع مناسب هستن به صورت زیر طبقه‌بندی شدن:
تعداد سایت‌های برگزار کنندۀ مسابقات آنلاین بسیار زیاد است ولی سایت‌های معروف و آن‌هایی که مناسب دیده شده را اینجا ذکر کردیم:
-
سایت معروف و قدیمی مربوط به مسابقات الگوریتم که کامیونیتی بسیاز بزرگی دارد.
تعداد زیادی سوال در موضوعات مختلف در بایگانی دارد و مسابقات آن به صورت مداوم تشکیل می‌شود.
توصیه می‌شود حتما ثبت‌نام کرده و به آن برای حل سوال سر بزنید.
-
از سایت‌های محبوب حل سوال الگوریتم که بانک سوال قابل توجهی دارد و مسابقه‌ی آن به صورت مداوم و هفتگی، چهارشنبه‌ها برگزار می‌شود.
توصیه می‌شود در آن مسابقات هفتگی شرکت شود و برای رقابت بیشتر می‌توانید نام دانشگاه خود را نیز وارد کرده تا وضعیت حل سوال هم دانشگاهی‌های خود را نیز ببینید.
-
سایت کوئرا کار خودش رو در تابستان ۹۴ با یک تیم سه‌نفره از دانشجوهای شریف شروع کرد؛ که بعدها به سایت جامعه‌ای برای برنامه‌نویسان تبدیل شد.
این سایت علاوه بر بانک سوالات و مسابقات داخلی، دوره‌های آموزشی داشته و با تکمیل پروفایل می‌تونین برای شرکت‌ها رزومه بفرستین؛ وضعیت حل سوالات الگوریتم و رتبه مسابقات هم می‌تونه در قسمت رزومه از طرف کوئرا قرار بگیره.
-
از سایت‌های قدیمی بوده که دوره‌های آموزشی مناسبی داشته و بانک سوالات نسبتاً خوبی داره.
دسترسی به این سایت برای کاربران ایرانی گاهی می‌تونه مشکل باشه.
سایت هندی بسیار معروف بین برنامه‌نویسان. سه بخش جالب توجه برای مسابقات الگوریتم لینک‌های زیر هستن:
-
کدشف سایت هندی آموزشی، بانک سوال و برگزار کنندۀ مسابقات هفتگی در دسته‌های مختلف است؛ که از داوری (Judge) SPOJ استفاده می‌کند.
سایت بسیار مفیدی است و توصیه به شرکت در رقابت‌های آن می‌شود. آموزش‌های رقابتی آن به زبان‌های برنامه‌نویسی مختلف وجود دارد.
-
از سایت‌های قدیمی برگزاری رقابت‌های الگوریتمی و دوره‌های مربوط به آن برای مسابقات و مصاحبه‌های کاری است.
-
Other Sources
برای دانلود کتاب مورد نظر می‌تونین از سایت libgensis استفاده کنین.
کتاب‌های متنوعی در این زمینه وجود دارد ولی ۴ کتاب معروف که پرطرفدار هستند به صورت زیر است:
کتاب مناسبی برای شروع؛ همراه با تمرین‌ها.
بهترین کتاب برای یادگیری الگوریتم، ولی متن آسانی برای شروع ندارد؛ معمولاً توصیه می‌شود قبل از شروع این کتاب، کتاب‌های دیگری در این زمینه‌ها مطالعه کرده باشید.
.
همراه با توضیح ساده و مناسب برای شروع.
این کتاب مختص مسابقات بوده و به سبک ICPC نزدیک‌تر است.
توصیه می‌شود برای شروع از کتاب‌های ۱ و ۳ (Algorithms unlocked و Programming Challenges) شروع کرده و بعداً سراغ کتاب‌های ۲ و ۴ (Introduction to Algorithms و Competitive Programming) بروید.
این کتاب توسط یکی از شرکت کننده‌های ICPC نوشته شده و مطالعه‌ی اون مخصوصاً برای دوستانی که C و ++C کار می‌کنن توصیه میشه.
.البته فعالیت سایت نسبت به گذشته خیلی ضعیف شده
https://www.pirateproxy-bay.com/