IAUM CCC 6 - Online Round 0

امروز مسابقه ی آنلاین اول IAUM CCC 6 برگزار شد. سه سوال از 7 سوال توسط من طرح شده بود. در این پست، ابتدا انتقاداتی از طرز انتقاد مسابقه دهندگان می کنم، و سپس به توضیح کوتاهی در باره ی سوال ها می پردازم.

سه سوال A و B و G توسط من طرح شده بود. برای دریافت صورت سوال ها، به آدرس http://pykello.net/iaumc3-6-0.tar مراجعه کنید. البته صورت سوال B در مسابقه یک اشتباه تایپی داشته که در این نسخه درست شده است.

سوال A مشکل خاصی نداشت، راه حل من که سعی کردم کندترین راه حل معقول باشد( از مرتبه ی زمانی (O(n^2 بود)، در کمتر از یک ثانیه اجرا می شد. سوال آسانی بود، و وقتی کد طولانی برخی شرکت کنندگان را دیدم بسی تعجب کردم. و واقعا چگونگی دست یافتن برخی شرکت کننده ها به نتیجه ی Time Limit Exceeded واقعا حیرت آور بود. به هر حال، عده ای به طرز Judge شدن این سوال معترض بودند که دلیلش را نمی دانم. من هم جزو Judge ها نبودم تا دلیل اعتراض آن ها را بدانم. داده های تست مشکلی نداشت. تعداد زیادی از افراد با اینکه در صورت سوال ذکر شده بود نقطه ای با مختصات (0,0) در ورودی نیست، باز هم وجود چنین نقطه ای را سوال می کردند.

سوال B ... معترضین به این سوال سه دسته بودند. دسته ای که معنی "متوسط" را بلد نبودند، و صورت سوال را مبهم می دانستند. اولا اینکه در صورت تمایل دوستان، می توانم بیش از 10 سوال مشابه پیدا کنم که بدون تعریف معنی متوسط، مقدار متوسط را خواسته بودند. پس اینکه تعریف "متوسط" را شخصی بلد نیست، ضعف در صورت سوال محسوب نمی شود. مبهم دانستن این مساله مانند این است که عدم ذکر معنای کوتاه ترین مسیر در مساله ی گراف را دلیل مبهم دانستن آن سوال بدانیم.
دسته ای دیگر، به clarification ها با دقت کافی نگاه نکرده بودند، و با اینکه به تعداد مراتبی زیادی ذکر کردم که k بار شیر افتادن باید "پشت سر هم" باشند، باز هم با اعتماد به نفس این مساله را ندیده می گرفتند و ورودی و خروجی نمونه را اشتباه می دانستند!
دسته ای دیگر، راه حل اشتباهی را انتخاب کرده بودن و مساله را به تعداد تکرار زیادی شبیه سازی کرده بودند، و مسلما جواب اشتباه می گرفتند. جالب این بود که انصاف را رها کرده بودند، و چون از 2-3 سوال دیگر و همچنین از نتیجه ی خودشان ناراضی بودند، با اعتماد به نفس زیادی می گفتند: "سوال گیر الکی داشت". مطمئنا کسانی که راه حل درست را پیدا کرده بودند، به مشکل خاصی برنخوردند.

سوال G، تقریبا کسی به طور جدی به این سوال نپرداخت، با اینکه از لحاظ ایده ای سخت نبود، ولی شاید پیاده سازی اش کمی طول می کشید و سوال های دیگر زمانی برای این سوال باقی نگذاشته بودند.

در باره ی ایده ها:

تنها به توضیح مختصری و کدها بسنده می کنم. ممکن است در آینده توضیح بیشتری بنویسم!

سوال A: برای دیدن کد من برای این سوال به http://wiki.pykello.net/doku.php?id=implementation:iaum_c3_6_sight مراجعه کنید. تنها نکته ای باید در نظر می گرفتید این بود که مثلا اگر دو نقطه در (1,1) و (1-,1-) قرار داشته باشند، هر دو نقطه را می بینیم، با اینکه نسبت x/y هر دو یکسان است.

سوال B: برای مشاهده کد من برای این سوال به http://wiki.pykello.net/doku.php?id=implementation:iaum_c3_6_kconsecutive مراجعه کنید.

کسانی که با معنای "متوسط" یا "امید ریاضی" در نظریه ی احتمال آشنا نیستند، به http://en.wikipedia.org/wiki/Expected_value مراجعه کنند.

فرض کنید [expDays[i برابر با تعداد متوسط روزهای لازم برای اینکه عمل سکه انداختن تمام شود با فرض اینکه i دفعه ی قبلی نتیجه سکه انداختن ها شیر بود، باشد. همانطور که معلوم است، expDays[k] = 0 است، چون k بار شیر پشت سر هم رخ داده است و بازی تمام شده است. در غیر اینصورت، expDays[i] = expDays[i+1] * p + expDays[0] * (1-p) + 1 است. عدد 1، برای این است که حتما یک بار سکه پرتاب می کنیم. با احتمال p، به حال [expDays[i+1 میرویم، یعنی به تعداد شیرهای پشت سرهم یکی اضافه می شود. و با احتمال q=1-p، به حالت [expDays[0 می رویم، یعنی تعداد شیرهای پشت سرهم به صفر می رسد. تابع calcDays در واقع این دنباله را محاسبه می کند. تابع calcMoney نیز از روشی مشابه ولی کمی پیچیده تر برای محاسبه متوسط پول استفاده می کند.

سوال G: برای مشاهده ی کد من برای این سوال، به http://wiki.pykello.net/doku.php?id=implementation:iaum_c3_6_grid مراجعه کنید.

راه حل مطلوب این سوال، از نوع برنامه سازی پویا بود. حالت برنامه سازی پویا نیز (شماره سطر، شماره ستون، بیت های لازم از وضعیت سطر بالا، بیت های لازم از وضعیت سطر فعلی) است. اگر این مدل را بصورت بدیهی پیاده سازی کنید، مسلما تعداد حالات خیلی زیاد خواهد بود. ولی باید دقت کنید در این مساله وضعیت سطری به طول n حداکثر می تواند (F(n) = F(n-1) + F(n-3 حالت داشته باشد، که برای n=30، کمتر از 500000 حالت می شود که زیاد نیست. با کمی طراحی خوب، می توان در بدترین حالت در زمان کمتر از 2 ثانیه به هر ورودی جواب داد.

خوب :) دوست دارم نظرتان در باره ی سوال ها را بدانم. لطفا کامنت یا ایمیل ارسال کنید!