مسابقات جهانی ICPC یا ACM
این شماره از رایانش برای من خیلی جالب بود؛ چون کلی چالش و یسری ناهماهنگی بطرز جالبی باعث شد که من این متن رو به موقع بنویسم و توی نشریه چاپ بشه!
این دومین متنی هست که برای رایانش نوشتم؛ اولی راجع به بازی‌گونه‌سازی یا Gamification بود که بصورت پادکست منتشر شده بود. ایشالا اونو هم بزودی ادامه میدم و اینجا هم می‌ذارم.
این پست بصورت متن هم در ادامه‌ی مطلب هست.
فرصتی پیش آمده تا کمی راجع به مسابقه‌ی ICPC و یا ای‌سی‌ام نوشته شود. در این متن ابتدا کمی تاریخچه و توضیحات مربوط به سبک سوال‌ها و مسابقه آمده است، و سپس مقداری دل‌نوشته راجع به تجربه‌ی دو سال اخیر در این مسابقات می‌یابید.
تاریخچه
اولین دوره‌ی مسابقه‌ی ICPC یا “مسابقه‌ی بین‌المللی برنامه‌نویسی دانشجویی”، در سال ۱۹۷۰ با شرکت ۷ تیم برگزار شد. این تیم‌ها می‌بایست برنامه‌های خود را به زبان Fortran روی “برگه‌های کدزنی” پانچ می‌کردند! امسال ۱۷هزار تیم از ۳۲۰۰ دانشگاه در ۴۳امین دوره‌ی این مسابقات شرکت کردند.
شرکت IBM از سال ۱۹۹۷ تا ۲۰۱۷ حامی این مسابقات بود و سپس جای خود را به JetBrains و Huawei داد. انجمن ACM (که از معتبرترین انجمن‌های علمی کامپیوتر می‌باشد) نیز از سال ۱۹۷۷ تا ۲۰۱۸ پشتیبانی و حمایت خاصی از این مسابقه انجام می‌داد. بخاطر حضور ACM در برگزارکننده‌های مسابقه، آن را ACM ICPC می‌نامیدند که در ایران این مسابقه به نام ACM شناخته میشد. حال که ACM نقشی در برگزاری مسابقه ندارد چالش بامزه‌ای رخ داده‌است، که اگر مسابقه ACM نامیده شود درست نیست و اگر ICPC نامیده شود هیچ‌کس آن را نخواهد شناخت. از این رو ما مسابقه را به فارسی ای‌سی‌ام و به انگلیسی ICPC معرفی می‌کنیم!
هیجان
مسابقه‌های ای‌سی‌ام با تیم‌های سه‌نفره برگزار می‌شود که هر تیم یک کامپیوتر در دسترس دارد و باید در ۵ ساعت با ۱۰ الی ۱۳ سوال برنامه‌نویسی دست و پنجه نرم کند. رتبه‌بندی مسابقه بر اساس تعداد سوال‌های حل شده است، و تیم‌هایی که تعداد برابری سوال حل کنند بر اساس مجموع زمان ارسال‌های درست‌شان مرتب می‌شوند. هم‌چنین هر ارسال غلط، ۲۰ دقیقه به زمان ارسال‌های بعدی آن سوال اضافه می‌کند! یعنی برای کسب رتبه‌ی خوب باید تعداد زیادی سوال را سریع و با دقت پیاده‌سازی کرد.
زمان کم، تعداد زیاد سوال‌ها، اهمیت دقت، و محدود بودن تیم به یک کامپیوتر باعث می‌شوند شرکت در چنین مسابقه‌ای بسیار هیجان‌انگیز و پرشور باشد. تیم دانشگاه مسکو در سال ۲۰۱۸، در ۳ دقیقه‌ی پایانی مسابقه نمره‌ی یک سوال را گرفت که باعث شد قهرمان جهان بشوند. ۳ دقیقه در بین ۳۰۰ دقیقه گم است! در نظر بگیرید کافی بود هر ۹۰ دقیقه (طول یک بازی فوتبال) به میزان یک دقیقه وقت تلف می‌کردند، مثلا باقی تیم‌ها یا رتبه‌بندی مسابقه توجهشان را جلب می‌کرد، تا قهرمانی را از دست می‌دادند. یا مثلا کافی بود در صدها خط کدی که برای ۱۰ سوالی که حل کردند نوشتند، یک کاراکتر ‘+’ را به اشتباه ‘-‘ می‌نوشتند و یافتن و تصحیح این ایراد بیش ۳ دقیقه از وقتشان را می‌گرفت.
کار تیمی
موضوعی که این مسابقه را دوست‌داشتنی‌تر می‌کند، تیمی بودن آن است. برای نتیجه گرفتن باید اعضای تیم توانایی‌ها و ویژگی‌های یکدیگر را خوب بشناسند و به بهترین شکل همکاری کنند. یک مزیت مهم تیم ما نسبت به دیگر تیم‌ها، همین همکاری تیمی بود. مثلا در حین مسابقه یک بار من و سیدپارسا سوال‌هایی که به آن‌ها فکر می‌کردیم را با هم عوض کردیم، و در نهایت این تعویض سوال و صحبت‌های در ادامه‌ی آن باعث شد که پس از دقایقی راه حل هر دو سوال را بیابیم. هم‌چنین آخرین سوالی که در مسابقه حل کردیم نتیجه‌ی همکاری سه‌نفره‌ی ما بود؛ به این صورت که علی در ۹۰ دقیقه‌ی آخر مسابقه سوال را بصورت نظری حل کرد و پیاده‌سازی کد آن را به من سپرد، و یک تابع مهم از کد را سیدپارسا پیاده‌سازی کرد و من در باقی کد از آن تابع استفاده کردم.
حل مسئله
از موارد جذابیت‌زا برای این مسابقه، نداشتن چارچوب برای سوال‌ها است.هرگونه سوالی که بتوان برنامه‌ای برای حل آن نوشت، می‌تواند یک سوال ای‌سی‌ام باشد! البته بیشترین سوال‌ها در زمینه‌ی طراحی الگوریتم و داده‌ساختارها هستند، اما چند مثال از سوال‌های غیرعادی در ادامه آمده است.
سوال‌های فیزیکی در چندین سال در مسابقه آمده‌اند. مثلا در یک سوال از سال‌های قبل، یک جسم سه‌بعدی توصیف شده بود و برنامه باید محاسبه می‌کرد چه نیرویی به آن جسم وارد شود تا در حالت تعادل بایستد. در سوالی دیگر نقشه‌ی کوه یک مسابقه‌ی اسکی داده شده بود و برنامه باید با شیب مشخص کوه و محدودیت شتاب حرکت اسکی‌باز، مسیری پیشنهاد می‌داد که اسکی‌باز بتواند از بیشترین تعداد پرچم گذر کند.
زمینه‌های هندسی خاص نیز در این مسابقات دیده می‌شود؛ مثلا بررسی تعداد راه‌های رنگ‌آمیزی یک ۶۰-وجهی مشابه لوگوی سایت wolfram-alpha، و یا بدست آوردن محل برخورد دو سفینه‌ی فضایی که با یک بردار در فضای سه‌بعدی در حرکتند، و یا نحوه‌ی کنار هم گذاشتن دو قطعه پازل بصورتی که بیشترین اشتراک محیط را داشته باشند.
برخی سوال‌ها نیز از زمینه‌های جالب علوم کامپیوتر طرح می‌شوند؛ مثلا بدست آوردن تعادل نش در بازی‌هایی روی گراف، و یا مرتب‌سازی تعدادی رشته بر اساس احتمال رخداد آن‌ها در یک رشته‌ی محدود تصادفی، و یا توصیف نوار بدست آمده از برش یک نوار موبیوس در راستای امتداد نوار.
برای رتبه گرفتن در این مسابقات نیاز است فرد بتواند یک مسئله را تحلیل بکند، تا حد زیادی مستقل از این که مسئله در چه موضوع و زمینه‌ای است.
حرف دل
خیلی خوش‌حال و مفتخریم که امسال توانستیم به لطف خدا با کسب مدال مسابقه شما را خوش‌حال کنیم. درسی که من از این مدال آوردن گرفتم این بود: “می‌شود!”
در صحبت‌های اوایل دی‌ماه تیم ما، مدال گرفتن در ای‌سی‌ام بیشتر رویا و آرزو بود تا یک هدف. ما سال گذشته هم برای مدال تلاش کرده بودیم و نتیجه‌ای نداشت. در سال‌های گذشته هم افراد بسیار توانمندتر از ما در این مسابقات نتوانستند مدال بگیرند، پس مدال دست‌نیافتنی به نظر می‌رسید. حال با این نتیجه‌ی کسب شده، آیا تیمی که سال بعد برای مسابقه‌ی جهانی می‌رود شکی در مصمم بودنش برای دریافت مدال رنگی‌تر از ما خواهد داشت؟
این پیش‌فرض اشتباه ذهنی ما بود که بدلیل ندیدن این نتیجه در سال‌های اخیر آن را دور از دسترس فرض کردیم. تیم سال بعد مدال را در دسترس خواهد دید (و قطعا با تلاش و تمرین به آن دست‌خواهد یافت)، زیرا دیدگاه “نمی‌شود” در این زمینه از بین رفته است. حال بیایید تصور کنیم در هر موضوع دیگری از قبیل زمینه‌های علمی، صنعتی، اقتصادی یا حتی سیاسی، “نمی‌شود”ها را کنار گذاشته‌ایم و بدنبال راهی برای ورود به لیست بهترین‌ها باشیم. خودباوری‌مان بیشتر شود تا بتوانیم با تلاش و کوشش، کشور را بیش از پیش به بالای رتبه‌بندی‌ها برسانیم.
