دوشنبه, مرداد 28. 1387
IAUM CCC 5
بالاخره، مرحله نهایی مسابقه ی IAUM CCC 5 برگزار شد، و تنها چیزی که برای من به جا ماند، خاطره ای نسبتا خوش بود! هرچند از چند روز قبل از مسابقه تا اتمام مسابقه ی نهایی استرس شدیدی داشتم و آرزوی اتمام این لحظات را داشتم، ولی پس از اتمام مسابقه ی نهایی و شنیدن نظرات شرکت کنندگان، احساس رضایت کردم. من فقط یک طراح سوال و داور بودم، و عضو هیئت اجرایی نبودم، با این حال، در این مدتی که در مشهد بودم، تلاش قابل تقدیر دانشجویان دانشگاه آزاد مشهد را مشاهده کردم، و از ته دل آرزو کردم که این مسابقات باز هم ادامه داشته باشد. احتمالا مهم ترین دلیل اینکه هر سال شرکت کنندگان این مسابقات بیشتر می شود، و افراد قوی تری هر سال جذب این مسابقات می شوند، برگزاری بسیار خوب این مسابقات است.
به نظر من، یکی از نکات مثبت حضور داشتن در این مسابقات آشنا شدن با افرادی است که علايقم با علايق آن ها همپوشانی دارد، ولی قبلا با آن ها آشنا نبودم، و این احساس خوبی در من ایجاد می کند.
نظرم در رابطه با نتیجه ی مرحله ی نهایی: گمان کنم چند نفر از افراد، احتمالا به علت عوامل جانبی (مانند استرس سر مسابقه، ...)، و نه به علت ضعف در حل مساله و توانایی علمی، ضعیف تر از توان واقعی خود عمل کردند و نتیجه نهایی کمی اعجاب انگیز بود. برنده ی نهایی مسابقه، آقای نیما احمدی پور بود، که بسیار خوب عمل کرد، و توانست همه ی مسائل را حل کند. به هر حال، تعداد زیادی از شرکت کننده ها را می شناختم و با تعدادی از آن ها دوست بودم، و از خوب عمل کردن خیلی های خوشحال شدم، و از بد عمل کردن خیلی ها ناراحت.
با این حال، عادی است که شدیدا دوست داشته باشم که کسی که دو سال هم تیمی ام بود، و یک ترم هم اتاقی، و برای باقی عمرم یک دوست بسیار خوب، یعنی محمدرضا خانی، خیلی خوب عمل کند. نتیجه نهایی او (یعنی چهارم) خوب بود، ولی با توجه به اینکه به نظر من باهوش ترین عضو تیم Dreamers United بود، گمان می کنم می توانست بهتر از این هم عمل کند. احتمالا یکی از دلایل اینکه خیلی خوب عمل نکرد، کمبود تمرین در چند ماه اخیر بود. امیدوارم هر روز موفق تر از دیروز باشد.
در ادامه به توضیح مختصر در مورد سوالاتی که من طرح کرده بودم می پردازم:
مسابقه نیمه نهایی صفر(لینک سوالات)
سوال C - کوتاه ترین زیر رشته ی نا مشترک : این سوال را با استفاده از Trie و مرتبه ی زمانی (O(n^2 حل کرده بودم، ولی راه حل های با مرتبه ی زمانی (O(n^2 log n نیز پذیرفته می شدند.
سوال D - مربع ها : هدف این بود که راه حل های (O(n^2 (برنامه نویسی پویا) و (O(n^2 log n (تبدیل به هیستوگرام و مرتب سازی و ...) پذیرفته شوند، ولی متاسفانه داده های تست ضعیف بود و راه حل (O(n^3 نیز پذیرفته می شد.
سوال E - تطبیق الگو : این سوال قرار بود سخت ترین سوال مسابقه باشد، ولی به علت عدم دقت در تنظیم محدودیت ها، آسان ترین سوال مسابقه بود! (مثلا باید اگر طول الگو 20000 بود و تعداد علامت سوال ها حداکثر 100، در آن صورت، بازهم راه حل خوبی برای حل مساله وجود داشت، ولی راه حل بدیهی خوب عمل نمی کرد.) با همین محدودیت ها، راه حل بدیهی به خوبی جواب می دهد. ولی اگر محدودیت ها خیلی سخت تر از این بودند، نسخه ی تغییر یافته ای از KMP، یا استفاده از Aho-Corasick می توانست مساله را به خوبی حل کند.
سوال F - شمارش جفت ها : قرار بود راه حل (O(n log n پذیرفته شود، ولی ظاهرا برخی از شرکت کننده ها با راه حل (O(n^2 محدود شده نیز توانسته بودند این سوال را حل کنند.
جمع بندی :در مجموع، از این مسابقه چندان راضی نبودم! چون زیاد اشتباه کرده بودیم! در انتها نیز دو نفر (نیما احمدی پور، و حامد احمدی) توانستند تمام سوالات را حل کنند، و حامد احمدی عنوان اول این مسابقه را کسب کرد.
مسابقه نیمه نهایی یک(لینک سوالات)
سوال B - علی کوچولو و کلمات متقارن : راه حل داور دارای مرتبه ی زمانی متناسب با مجموع طول کلمات بود.
سوال C - تجزیه ی گراف ها : تبدیل می شود به مساله ی 2SAT . تنها یک نفر موفق شد این مساله را سر مسابقه حل کند (مهدی صفرنژاد) ولی حداقل دو نفر دیگر به ایده ی این سوال رسیده بودند ولی از آن جایی که بلد نبودند کد 2SAT را بنویسند، موفق به حل آن نشدند. ظاهرا محمدرضا خانی راه حل دیگری برای این سوال داشت، که به علت خستگی، از او خواستم بعدا توضیح دهد!
سوال F - یافتن زیر درخت : بیش از یک راه حل با مرتبه ی زمانی خطی برای حل این مساله وجود دارد.
جمع بندی : این مسابقه راضی کننده تر از مسابقه ی قبلی بود، و تقریبا هیچ مشکل خاصی پیش نیامد. در انتها مهدی صفر نژاد با حل 5 سوال نفر اول این مسابقه شد.
مسابقه ی نهایی(لینک سوالات)
سوال A - شمارش درخت های پوشا : این مساله را می توان با استفاده از قضیه ی Matrix-Tree حل کرد. ولی از آن جایی که اصولا نباید انتظار داشته باشیم شرکت کننده ها چنین قضایایی را بلد باشند، من خودم این مساله را با استفاده از یک الگوریتم برنامه سازی پویای (O(n^2 3^n حل کرده بودم. سر مسابقه سه نفر این مساله را حل کردند که دو نفر از قضیه ی مذکور استفاده کردند، و یک نفر از راه حل برنامه سازی پویا (نمی دانم راه حلش شبیه مال من بود یا نه).
سوال B - کوچک ترین مثلث : با راه حل (O(n^3 ای که خوب پیاده سازی شده باشد حل می شود، ولی احتمالا راه حل های بهتری نیز وجود دارند!
سوال C - رشته های امن : برنامه سازی پویا با استفاده از آرایه ی overlap الگوریتم KMP!
سوال D - مسافرت های تصادفی : راه حل من یک DFS بود، ولی ظاهرا اکثر شرکت کنندگان از راه حل دیگری استفاده کردند.
سوال E - انتخاب پروژه ها : تبدیل می شود به مساله ی مشهور Minimum Cut در گراف. تنها یک نفر (نیما احمدی پور) موفق به حل این مساله شد، ولی حداقل یک نفر دیگر ایده ی درست برای حل این مساله را داشت (مهدی صفرنژاد)، که متاسفانه راه حلش جواب درست را نمی داد.
سوال F - پارادوکس : راه حل این مساله ترکیبی است از پیدا کردن مولفه های همبند، Brute Force، و برنامه سازی پویا. باز هم تنها یک نفر موفق به حل این مساله شد (نیما احمدی پور) ولی راه حل مهدی صفرنژاد هم اکثر تست ها را درست جواب می داد و تنها در چندین تست با پاسخ داور تفاوت داشت.
سوال G - طولانی ترین زیردنباله ی مشترک : برنامه سازی پویا. نکته ی اساسی این مساله این بود که هر عدد حداکثر یک بار در هر دنباله وجود دارد. چندین نفر تلاش کردند که از چندین LCS دو به دو استفاده کنند که مسلما راه حل درستی نیست و با کمی تامل می توان مثال نقضی برای آن پیدا کرد.
جمع بندی : از آن جایی که مشکل خاصی وجود نداشت، و شرک کنندگان هم از سطح و نوع سوالات راضی بودند، مسابقه ی خوبی بود، و باعث شد که مسابقات به خوشی برای من تمام شود. در انتها نیز نیما احمدی پور با حل 8 سوال مقام اول را کسب کرد.
Me
Me = {
"Name": "Hadi",
"Job": "Programmer",
"Hobbies": [
"Thinking",
"Reading",
"Walking",
"Living" ],
... }
Favorite Links
Friends
Categories
Syndicate This Blog
Blog Administration
Powered by
