مدرسه

آغاز مسابقه المپیاد کامپیوتر و خواندن سوالها و حل مسائل-اول مشاور
آغاز مسابقه
• مجموعهکارهایی که در آغاز هر مسابقه باید روی کامپیوتر تازه انجام دهید از قبل مشخص کنید. مواردی از این قبیل:
o نوشتن اسکریپتهای کمکی و Makefile
o تنظیمات سیستم عاملی
o تنظیمات IDE
o شاخهبندی برای نوشتن برنامهها
• یک قالب (template) کد برای خود طراحی کنید تا برای هر کد جدید لازم نباشد از صفر شروع کنید.
• قالب کد برای زمینههای مختلف میتواند متفاوت باشد. مثلا قالب کد برای برنامههای هندسی میتواند توابع پایهای هندسی را هم شامل شود.
• باید در نوشتن قالب کد خود کاملا روان باشید، بهطوری که از درستی آن اطمینان داشته باشید.
• میتوان قالب کد را در ابتدا یک بار بهطور کامل نوشت. همچنین میتوان بهشکل افزایشی آن را کامل کرد، یعنی در ابتدای هر برنامهی جدید، موارد لازم آن برنامه را به قالب اضافه کرد.
خواندن سوالها
• در اول کار بهتر است که همه سوالها را روی کاغذ (نه روی صفحه نمایش) بخوانید.
• در خواندن دقیق سوالها کوتاهی نکنید چرا که بعضا دیده شده که به خاطر ناقص خواندن سوالها٬ یک شخص یک یا دو ساعت از وقت آزمون را از دست داده است. مواردی وجود داشته که یک سؤال بهخاطر درست خوانده نشدن، بسیار سادهتر و در مواردی بسیار پیچیدهتر از نسخهی اصلی سؤال درک شده است. در حالت اول، مسابقهدهنده وقت خود را صرف راهحلی درست برای سؤال خودش کرده و از قابل قبول نبودن آن در مسابقه متعجب شده است. و در حالت دوم، مسابقهدهنده از حل سؤال درمانده شده یا درگیر راهحلی پیچیده گشته است. (که با این درد اگر در بند درمانند درمانند!)
• بعضی عادت دارند زیر نکات مهم سؤال خط بکشند یا با مارکرهای رنگی آنها را high-light کنند. کار خوبی میتواند باشد ولی مواظب باشید نکات high-light نشده از قلم نیفتند.
• سعی کنید با توجه به تجریبات و دانش خود مسائل را به لحاظ مرتبه سختی مرتب کنید. هر چقدر شما در حل مسئله تجربه بیشتری داشته باشید ترتیب شما به واقعیت نزدیکتر خواهد بود.
حل مسائل
• معمولا اولین قدم از حل مسائل المپیاد کامپیوتر، مدلسازی مسئله به فرم ریاضی و حذف زوائد آن است. هزینهی اشتباه در این قدم کمتر از اشتباه در خواندن صورت سؤال نیست. کافی است یکی از شرطهای صورت سؤال در مدل جدید دیده نشود.
• یکی از روشهای حل مسئله، حذف جزئیات بیمورد و تبدیل آن به مسائل سادهتر است که به آن کاهش (Reduction) هم گفته میشود. خیلی مسائل که در ابتدا پیچیده بهنظر میرسند، با چند مرحله سادهسازی، به مسائلی آسان تبدیل میشوند. ولی این سادهسازیها خطرات خودشان را هم دارند. کافی است گزاره یا شرط خاصی از مسئلهی اولیه را در مسئلهی ثانویه لحاظ نکنیم یا فرض اضافهای را در مسئلهی ثانویه در نظر بگیریم تا دیگر کاهش ما به کلی نادرست باشد. بهاصطلاح، مسئلهی ثانویهی انتخابی باید «سختترمساوی» مسئلهی اولیه باشد. ولی گاهی در رعایت این نکته، خطر افتادن از طرف دیگر بام وجود دارد و مسئلهی ثانویهی انتخابی، چنان تعمیمیافته و پیچیدهتر از مسئلهی اولیه میشود که دیگر بهراحتی قابل حل نیست، مثلاً مسئلهی اولیه «شناسایی بلندترین مسیر در DAG» بوده (که الگوریتم چندجملهای سادهای دارد)، و مسئلهی ثانویه «شناسایی بلندترین مسیر در گراف جهتدار دلخواه» شده (که مسئلهای NP-Complete است). گاهی با استفاده از یک «کاهش» معکوس (حل مسئلهی ثانویه با مسئلهی اولیه) میتوان تضمین کرد که دچار چنین اشتباهی نشدهایم.
• با نگاه به پارامترهای ورودی زیرمسائل یک مسئله، سعی کنید زمان اجرایی را که برای هر زیر مسئله مدنظر است پیدا کنید. به عنوان مثال اگر مسئله فقط یک پارامتر ورودی به نام n
دارد و دارای دو زیر مسئله است که در زیر مسئله اول n≤104 است و در زیر مساله دوم n≤108 است (با این فرض که کامپیوتر شما حدودا 108 عمل در ثانیه انجام میدهد)، احتمالا در زیر مسئله اول باید به دنبال راهحلی با زمان اجرای O(n2) باشید و برای زیرمسئله دوم، راهحلی با زمان اجرای O(nlogcn) مناسب است (0≤c).
• البته باید توجه کرد که این مرتبههای زمان اجرا تنها حد بالا را نشان میدهند و ممکن است مسئله راهحلهای ساده با زمان اجراهای بهتر هم داشته باشد.
• با سادهترین زیرمسئله شروع کنید و برای آن راهحلی پیدا کنید. معمولا در چند دقیقه میتوان راهحلی تئوری برای سادهترین زیر مسئله پیدا کرد. این به شما کمک میکند که درک درستی نسبت به مسئله پیدا کنید و از بیراهه رفتن شما جلوگیری میکند.
• بعد از بهدست آوردن درک درست از مسئله به دنبال بهترین راهحل برای آن باشید. اگر چندین راهحل به ذهن شما زد٬ آن راهحلی را انتخاب کنید که پیادهسازی سادهتری داشته باشد.
• حتما درستی الگوریتم خود را بررسی کنید و آن را روی ورودیهای کوچک و ساده تست کنید.
• اگر راهحلی که در ذهن دارید حریصانه است٬ با دیده شک به آن نگاه کنید و کمی به دنبال مثال نقض برای آن بگردید. در اکثر موارد برای الگوریتمهای حریصانهای که به ذهن میآید میتوان به سادگی مثال نقض پیدا کرد.
• حالتهای فریبنده را سعی کنید پیدا کنید و بر اساس آنها الگوریتم خود را به قسمتهای مختلف بشکنید.
• پس از طراحی الگوریتم، ترجیحا قبل از شروع به کد زدن، یک دور دیگر صورت سؤال را بخوانید تا مطمئن شوید راهحلتان برای سؤال درست است و چیزی از قلم نیفتاده. اگر صورت سؤال بلند و دارای جزئیات است، با توجه به بالا بودن خطر فراموش شدن نکتهای، مرور مجدد صورت سؤال ارزشش را دارد. و اگر صورت سؤال کوتاه بود، هزینهی این کار کم است!
• تا نسبت به الگوریتم خود مطمئن نشدید٬ کد نویسی را شروع نکنید. وقتی کد نویسی را شروع کردید دیگر نمیتوانید به درستی فکر کنید.