استراتژی مسابقه دادن
یک مسابقه المپیاد معمولا شامل سه سوال الگوریتمی است که باید در مدت زمان ۵ ساعت حل شود. یکی از عوامل اصلی موفقیت در هر آزمون داشتن برنامه و استراتژی مشخص و احترام گذاشتن به آن در زمان آزمون است. برخی از سوال‌هایی که قبل از آزمون باید به آن‌ها فکر کرده باشید و جوابی برای آن داشته باشید از این قرار است:
- چگونه شروع کنم؟
- آبا بهتر نیست که در اول مسابقه به حل تئوری مسائل بپردازم و بعد به کد زدن؟
- برای حل هر مسئله از ابتدای خواندن سؤال تا انتهای کار، چه فرایندی را طی کنم؟
- اگر به باگ برخورد کردم برای رفع باگ چه میزان وقت بگذارم؟
- در ساعت پایانی مسابقه اگر بیش از یک مسئله حل نشده داشته باشم چه کار بکنم؟
- چه زمانی به جای حل مسئله اصلی به سراغ زیر مسائل ساده‌تر آن بروم؟
- در زمان آزمون اگر موضوعی غیر مرتبط، مثل سرفه کردن دیگران، اذیتم کرد چه کار باید بکنم؟
- اگر در روز ازمون بیمار بودم چه کار بکنم؟
- و سوال کلی‌تر؛ کارهایی که در هر ساعت آزمون باید انجام بدهم چیست؟
شما باید سعی کنید در آزمون‌های تمرینی جواب سوال‌های بالا و سوال‌های مشابه را پیدا کنید. یعنی باید در هر آزمون تمرینی یک استراتژی خاص را تجربه کرده و در نهایت ۲ یا ۳ استراتژی را که متناسب با روحیه و شخصیت شما هست و در آزمون‌های تمرینی جواب خوبی داده را انتخاب کرده و به آن استراتژی و برنامه‌ها در زمان آزمون‌های اصلی پایبند باشید. بی‌برنامه بودن در حین آزمون قریب به یقین می‌تواند منجر به شکست‌های بزرگی شود. در ادامه، توصیه‌هایی برای کمک در طراحی استراتژی آزمون ارائه شده است.
مسائل حاشیه‌ای مسابقه
- خواب کافی: اگر قبل مسابقه، به‌اندازه‌ی کافی نخوابیده باشید، ناخواسته، سرعت و دقت ذهن‌تان پایین می‌آید. در صورت غیرمتعارف بودن زمان مسابقه یا تغییر time-zone، اهمیت این موضوع بیشتر می‌شود. برای آزمون‌های مهم، سعی کنید زودتر از ساعات عادی برای خواب اقدام کنید تا در صورت دیرتر به‌خواب رفتن، دچار مشکلی نشوید. از طرف دیگر لااقل دو ساعت قبل آزمون از خواب بیدار شوید تا از هوشیاری کامل در طول آزمون برخوردار باشید.
- عادات غذایی: به عادت‌های غذایی خود قبل و حین مسابقه توجه داشته باشید. اگر وجود خوراکی خاصی را حین مسابقه لازم می‌دانید، از فراهم بودن آن مطمئن باشید، ولی باید شرایط فراهم نشدن آن به‌هر دلیلی را هم درنظر بگیرید. سعی کنید این‌گونه وابستگی‌ها را در خود کم کنید. بهتر است در طول آزمون‌های بلند، در فاصله‌های زمانی نیم تا یک ساعت، چیز شیرینی مانند شکلات مصرف کنید. چون اگر به مرحله‌ی خستگی یا سردرد ناشی از کاهش قند خون رسیدید، از زمان صرف شیرینی مدتی طول می‌کشد تا رفع کسالت شود.
- قدرت تایپ سریع: برنامه‌نویسان خوب برای تایپ به صفحه‌کلید نگاه نمی‌کنند و از همه‌ی انگشتان برای تایپ استفاده می‌کنند. سایت‌ها و نرم‌افزارهای زیادی برای آموزش تایپ انگلیسی ده‌انگشتی وجود دارد. سرعت بالای تایب بدون نیاز به توجه به صفحه‌کلید، باعث می‌شود بتوانید روی محتوای برنامه‌ای که می‌نویسید تمرکز بیشتری داشته باشید.
- صفحه‌کلید: تایپ سریع و بدون نیاز به نگاه به صفحه‌کلید، مستلزم استفاده از صفحه‌کلید استاندارد است. با انتخاب یک صفحه‌کلید استاندارد مناسب خود، در همه‌ی آزمون‌ها (آزمایشی و اصلی) از همان صفحه‌کلید استفاده کنید. خوش‌بختانه در همه‌ی مسابقات مطرح برنامه‌نویسی، امکان استفاده از صفحه‌کلید شخصی به مسابقه‌دهندگان داده می‌شود. در تصویر زیر، چینش استاندارد صفحه کلید را مشاهده می‌کنید.
- ماوس: با توجه به این که در مسابقات رسمی ماوس در اختیارتان هست ولی touch-pad نیست، سعی کنید حین برنامه‌نویسی از touch-pad استفاده نکنید تا به آن عادت نکنید. این مشکل بیشتر در افرادی ظاهر می‌شود که با لپ‌تاپ کار می‌کنند. اگر عادت به استفاده از touch-pad دارید، در زمان برنامه‌نویسی و مسابقه‌دادن آن را غیرفعال نمایید.
آغاز مسابقه
-
مجموعه‌کارهایی که در آغاز هر مسابقه باید روی کامپیوتر تازه انجام دهید از قبل مشخص کنید. مواردی از این قبیل:
- نوشتن اسکریپت‌های کمکی و Makefile
- تنظیمات سیستم عاملی
- تنظیمات IDE
- شاخه‌بندی برای نوشتن برنامه‌ها
- یک قالب (template) کد برای خود طراحی کنید تا برای هر کد جدید لازم نباشد از صفر شروع کنید.
- قالب کد برای زمینه‌های مختلف می‌تواند متفاوت باشد. مثلا قالب کد برای برنامه‌های هندسی می‌تواند توابع پایه‌ای هندسی را هم شامل شود.
- باید در نوشتن قالب کد خود کاملا روان باشید، به‌طوری که از درستی آن اطمینان داشته باشید.
- می‌توان قالب کد را در ابتدا یک بار به‌طور کامل نوشت. هم‌چنین می‌توان به‌شکل افزایشی آن را کامل کرد، یعنی در ابتدای هر برنامه‌ی جدید، موارد لازم آن برنامه را به قالب اضافه کرد.
خواندن سوال‌ها
- در اول کار بهتر است که همه سوال‌ها را روی کاغذ (نه روی صفحه نمایش) بخوانید.
- در خواندن دقیق سوال‌ها کوتاهی نکنید چرا که بعضا دیده شده که به خاطر ناقص خواندن سوال‌ها٬ یک شخص یک یا دو ساعت از وقت آزمون را از دست داده است. مواردی وجود داشته که یک سؤال به‌خاطر درست خوانده نشدن، بسیار ساده‌تر و در مواردی بسیار پیچیده‌تر از نسخه‌ی اصلی سؤال درک شده است. در حالت اول، مسابقه‌دهنده وقت خود را صرف راه‌حلی درست برای سؤال خودش کرده و از قابل قبول نبودن آن در مسابقه متعجب شده است. و در حالت دوم، مسابقه‌دهنده از حل سؤال درمانده شده یا درگیر راه‌حلی پیچیده گشته است. (که با این درد اگر در بند درمانند درمانند!)
- بعضی عادت دارند زیر نکات مهم سؤال خط بکشند یا با مارکرهای رنگی آن‌ها را high-light کنند. کار خوبی می‌تواند باشد ولی مواظب باشید نکات high-light نشده از قلم نیفتند.
- سعی کنید با توجه به تجریبات و دانش خود مسائل را به لحاظ مرتبه سختی مرتب کنید. هر چقدر شما در حل مسئله تجربه بیشتری داشته باشید ترتیب شما به واقعیت نزدیک‌تر خواهد بود.
حل مسائل
- معمولا اولین قدم از حل مسائل المپیاد کامپیوتر، مدل‌سازی مسئله به فرم ریاضی و حذف زوائد آن است. هزینه‌ی اشتباه در این قدم کمتر از اشتباه در خواندن صورت سؤال نیست. کافی است یکی از شرط‌های صورت سؤال در مدل جدید دیده نشود.
- یکی از روش‌های حل مسئله، حذف جزئیات بی‌مورد و تبدیل آن به مسائل ساده‌تر است که به آن کاهش (Reduction) هم گفته می‌شود. خیلی مسائل که در ابتدا پیچیده به‌نظر می‌رسند، با چند مرحله ساده‌سازی، به مسائلی آسان تبدیل می‌شوند. ولی این ساده‌سازی‌ها خطرات خودشان را هم دارند. کافی است گزاره یا شرط خاصی از مسئله‌ی اولیه را در مسئله‌ی ثانویه لحاظ نکنیم یا فرض اضافه‌ای را در مسئله‌ی ثانویه در نظر بگیریم تا دیگر کاهش ما به کلی نادرست باشد. به‌اصطلاح، مسئله‌ی ثانویه‌ی انتخابی باید «سخت‌ترمساوی» مسئله‌ی اولیه باشد. ولی گاهی در رعایت این نکته، خطر افتادن از طرف دیگر بام وجود دارد و مسئله‌ی ثانویه‌ی انتخابی، چنان تعمیم‌یافته و پیچیده‌تر از مسئله‌ی اولیه می‌شود که دیگر به‌راحتی قابل حل نیست، مثلاً مسئله‌ی اولیه «شناسایی بلندترین مسیر در DAG» بوده (که الگوریتم چندجمله‌ای ساده‌ای دارد)، و مسئله‌ی ثانویه «شناسایی بلندترین مسیر در گراف جهت‌دار دلخواه» شده (که مسئله‌ای NP-Complete است). گاهی با استفاده از یک «کاهش» معکوس (حل مسئله‌ی ثانویه با مسئله‌ی اولیه) می‌توان تضمین کرد که دچار چنین اشتباهی نشده‌ایم.
- با نگاه به پارامترهای ورودی زیرمسائل یک مسئله، سعی کنید زمان اجرایی را که برای هر زیر مسئله مدنظر است پیدا کنید. به عنوان مثال اگر مسئله فقط یک پارامتر ورودی به نام n دارد و دارای دو زیر مسئله است که در زیر مسئله اول n≤104 است و در زیر مساله دوم n≤108 است (با این فرض که کامپیوتر شما حدودا 108 عمل در ثانیه انجام می‌دهد)، احتمالا در زیر مسئله اول باید به دنبال راه‌حلی با زمان اجرای O(n2) باشید و برای زیرمسئله دوم، راه‌حلی با زمان اجرای O(nlogcn) مناسب است (0≤c). البته باید توجه کرد که این مرتبه‌های زمان اجرا تنها حدبالا را نشان می‌دهند و ممکن است مسئله راه‌حل‌های ساده با زمان اجراهای بهتر هم داشته باشد.
- با ساده‌ترین زیرمسئله شروع کنید و برای آن راه‌حلی پیدا کنید. معمولا در چند دقیقه می‌توان راه‌حلی تئوری برای ساده‌ترین زیر مسئله پیدا کرد. این به شما کمک می‌کند که درک درستی نسبت به مسئله پیدا کنید و از بیراهه رفتن شما جلوگیری می‌کند.
- بعد از به‌دست آوردن درک درست از مسئله به دنبال بهترین راه‌حل برای آن باشید. اگر چندین راه‌حل به ذهن شما زد٬ آن راه‌حلی را انتخاب کنید که پیاده‌سازی ساده‌تری داشته باشد.
- حتما درستی الگوریتم خود را بررسی کنید و آن را روی ورودی‌های کوچک و ساده تست کنید.
- اگر راه‌حلی که در ذهن دارید حریصانه است٬ با دیده شک به آن نگاه کنید و کمی به دنبال مثال نقض برای آن بگردید. در اکثر موارد برای الگوریتم‌های حریصانه‌ای که به ذهن می‌آید می‌توان به سادگی مثال نقض پیدا کرد.
- حالت‌های تریکی را سعی کنید پیدا کنید و بر اساس آن‌ها الگوریتم خود را به قسمت‌های مختلف بشکنید.
- پس از طراحی الگوریتم، ترجیحا قبل از شروع به کد زدن، یک دور دیگر صورت سؤال را بخوانید تا مطمئن شوید راه‌حل‌تان برای سؤال درست است و چیزی از قلم نیفتاده. اگر صورت سؤال بلند و دارای جزئیات است، با توجه به بالا بودن خطر فراموش شدن نکته‌ای، مرور مجدد صورت سؤال ارزشش را دارد. و اگر صورت سؤال کوتاه بود، هزینه‌ی این کار کم است!
- تا نسبت به الگوریتم خود مطمئن نشدید٬ کد نویسی را شروع نکنید. وقتی کد نویسی را شروع کردید دیگر نمی‌توانید به درستی فکر کنید.
کد نویسی
- هدف از کد زدن٬ صرفا سریع کد زدن نیست. هدف آن است که در انتها شما یک کد صحیح و تمیز داشته باشید. صرف وقت برای زدن کد صحیح و تمیز٬ شما را از مواجهه با باگ نجات می‌دهد مخصوصا باگ‌هایی که در دقایق پایانی به آن‌ها پی می‌برید و دیگر فرصتی برای رفعشان نیست.
-
قبل از شروع کد، حتما ساختار کلی آن را در ذهن خود (و در موارد پیچیده، حتما روی کاغذ) مرور کنید. به سؤالات از این دست باید پاسخ‌های مشخصی داشته باشید:
- هر قسمت از برنامه چه چیزهایی را (به‌عنوان ورودی و داده‌های کمکی) نیاز دارد و چه چیزهایی را (به‌عنوان خروجی) فراهم می‌کند؟
- متغیرهای سراسری برنامه کدام‌ها خواهند بود و چه چیزهایی تنها در یک قسمت خاص برنامه کاربرد دارد؟
- گلوگاه‌های زمان اجرا و حافظه‌ی برنامه کجاها خواهند بود؟
- اگر لازم شود زمان اجرای برنامه را بهبود دهیم کجاهای برنامه تغییر می‌کنند و این تغییرات چه‌قدر در بخش‌های دیگر برنامه تأثیر می‌گذارند؟
- قسمت‌های پیچیده‌تر برنامه و جاهایی که احتمال باگ زدن در آن‌ها بیشتر است کدام‌اند؟
- هر قسمت از کد را که می‌نویسید آن قسمت را تست کنید که از درستی آن مطمئن شوید. تست کردن قسمت‌های کوچک برنامه خیلی ساده‌تر از تست کردن یک برنامه بزرگ چندقسمتی است. هرچه در برنامه‌ی خود از بلوک‌هایی استفاده کنید که قبلا تست شده‌اند، بیشتر می‌توانید توجه و تمرکز خود را صرف بخش‌های دیگر برنامه کنید.
- اگر به‌ترتیب روند اجرای برنامه کدتان را بنویسید، می‌توانید از داده‌های ورودی نمونه که در اختیارتان گذاشته شده برای تست هر قسمت جدیدی که می‌نویسید استفاده کنید.
- برای قسمت‌هایی که احساس می‌کنید به خاطر سپردن‌شان سخت است حتما کامنت بگذارید. چرا که بعضی وقت‌ها بعد از مدت طولانی به آن قسمت برمی‌گردید و اگر کامنتی ننوشته باشید فهم آن قسمت از کد٬ از شما زمان زیادی خواهد گرفت.
- هرگاه قرار است بخشی از کدتان را با کد جدیدی جای‌گزین کنید (مثال وقتی باید یک قسمت از کد خود را بهینه بکنید)٬ حتما یک کپی از کد فعلی خود را در یک فایل دیگر ذخیره کنید. فایل اصلی خود را که در حال نوشتن در آن هستید، هیچ‌گاه تغییر نام ندهید و تنها نسخه‌های پشتیبان را با نام‌های مشخص بسازید. مثلا اگر در حال نوشتن در book.cpp هستید، همیشه برنامه‌ی اصلی خود را که در حال ویرایش و تست(و نهایتا submit)ش هستید در همین فایل بگذارید و نسخه‌های پشتیبان را با نام‌هایی مانند book0.cpp یا book-n2.cpp ذخیره کنید. این قرارداد باعث می‌شود از خطاهای رایج جابه‌جا گرفتن فایل‌ها در زمان اجرا و تست و ارسال برنامه‌ها جلوگیری شود.
- اگر در هر قسمتی از کد، نکته‌ای از جای دیگر کد به‌ذهن‌تان خطور کرد، حتما در جایی یادداشت کنید. استفاده از حافظه در این موارد اصلا توصیه نمی‌شود. داشتن یک TODO-List برای هر سؤال مفید است.
- به قوانین مهندسی نرم‌افزاری در زمینه‌ی کد‌زدن حتما در طول زمان اصلی کدزنی پایبند باشید. فقط در فاز نهایی و رفع باگ، اجازه‌ی شکستن قواعد را به‌خود بدهید.
تست کردن
- هیچ‌گاه برای دادن تست‌ها به برنامه‌تان از تایپ با صفحه‌کلید یا copy-paste در کنسول استفاده نکنید. هر تست را در یک فایل متنی ذخیره کنید و با redirection آن را به‌برنامه‌ی خود دهید. با این کار ممکن است هزینه‌ی اجرای هر تست برای بار اول، کمی بیشتر از حالت عادی باشد، ولی امکان اجرای سریع تست‌ها در دفعات بعدی، این هزینه‌ی زمانی را به‌سرعت جبران می‌کند. معمولا در شروع تست برنامه، یک احساس نادرست می‌گوید دفعه‌ی بعدی‌ای درکار نیست و در نتیجه رعایت این قاعده لازم نیست. ولی کافی است به تجربه‌ی خود مراجعه کنید تا ببینید احتمال این چه‌قدر است که برنامه‌تان در اولین اجرا همه‌ی تست‌ها را به‌درستی جواب دهد و دیگر نیاز به تغییر و تست مجدد نداشته باشد. علاوه‌بر آن، تست‌های ذخیره‌شده هستند که تست بلوک‌بلوک برنامه را امکان‌پذیر می‌کنند.
- حتما وقت مناسبی در حد نیم ساعت (در یک آزمون ۵ ساعته) برای تست برنامه خود بگذارید.
- اگر فرصت دارید یک راه‌حل صحیح و ساده (هرچند کند) برای مسئله بنویسید و در ضمن یک تولید کننده تست‌دیتا نیز آماده کنید.
- خروجی برنامه اصلی و برنامه کندی که آماده کرده‌اید را روی تست دیتاهایی که آماده کرده‌اید مقایسه کنید. برای انجام این مقایسه هم کافی است که یک برنامه کوچک بنویسید یا آن را با دستورهای موجود در سیستم‌عامل موجود انجام دهید.
- تست حالت‌های خاص فراموش نشود. باگ‌ها بیشتر در گوشه و کنارها دیده می‌شوند!
- در یک مجموعه تست خوب، هر خط و هر عبارت برنامه لااقل در یک تست اجرا می‌شود.
- حتما روی چند تست نمونه‌ی بزرگ برنامه خود را تست کنید که مثلا به خاطر overflow برنامه شما اشتباه کار نکند، یا اگر به‌خاطر اشتباه، زمان اجرا یا حافظه برنامه‌تان خارج از حد مجاز می‌شد، متوجه این موضوع بشوید.
- اساسا تست یک برنامه توسط سازنده‌اش خلاف فطرت اوست! هرچه احساس گریز بیشتری نسبت به تست برنامه‌تان دارید، احتمال داشتن باگ در آن برنامه بیشتر است!
برطرف کردن باگ
- اگر نمی‌خواهید زیاد با باگ مواجه شوید حتما در حین کد زدن اجزای برنامه خودتان را تست کنید.
- اگر وقت زیادی را صرف رفع باگ کردید حتما به زمان نیم نگاهی داشته باشید تا ببینید ادامه این روند مفیدتر است یا سراغ سوال دیگر رفتن.
- بعضی وقت‌ها دوباره کد زدن یک جزء از برنامه زمان کم‌تری نسبت به رفع باگ آن می‌گیرد.
- شما می‌توانید از ابزارهای موجود مثل gdb برای پیدا کردن محل خطای حافظه استفاده کنید.
- شما می‌توانید با گذاشتن دستورهایی در لابه‌لای کد مقدار پارامترها را بررسی کنید تا شاید از طریق آن‌ها بتوانید باگ را پیدا کنید.
- اگر بعد از مدتی مشخص نتوانستید باگ را برطرف کنید٬ سراغ مسئله دیگر بروید و بعد از حل آن با انگیزه و انرژی بیشتر مجددا به رفع باگ مسئله اول برگردید.
ارسال راه‌حل
- اگر فرآیند درست و مشخصی داشته‌باشید، در ارسال فایل برنامه‌ی خود اشتباه نمی‌کنید.
- قبل از ارسال راه‌حل، حتما یک بار دیگر برنامه را کامپایل و تست کنید.
- داشتن یک چک لیست برای زمان ارسال راه‌حل، شامل باگ‌ها و خطاهای رایج احتمالی و کارهای لازم پیش از ارسال توصیه می‌شود.
توصیه‌های تکمیلی
- در آزمون‌های تمرینی حتما یک لاگ از کارها و زمانی که برای آن‌ها صرف کرده‌اید را نگه دارید. این کار به شما کمک می‌کند که بتوانید استراتژی خود را بعد از آزمون ارزیابی کرده و احتمالا استراتژی خود را بهبود ببخشید.
- حفظ آرامش در آزمون حتی در بدترین شرایط نتیجه بهتری را برای شما رقم خواهد زد.
- از تصمیم‌گیری احساسی بپرهیزید و از سوئیچ سریع بین مسائل خودداری کنید.
- اگر زیرمسائل سخت یک مسئله قابل حل نیست حتما به سراغ زیر مسائل ساده‌تر بروید و به هیچ وجه از نمرات بدیهی که می‌توانید در آزمون کسب کنید نگذرید.
- آزمون‌های اصلی محل امتحان کردن ابزارهای برنامه‌نویسی، کتاب‌خانه‌ها، و الگوریتم‌هایی نیست که جدیداً یاد گرفته‌اید و بر آن‌ها مسلط نیستید.
- اصرار بی‌جا بر حل یک مسئله و رها کردن بقیه مسائل در حین آزمون اصلی شدیدا نهی می‌شود. قرار نیست روی یک مسئله یا یک زیرمسئله را حتما کم کنید!
