Competing

سلام،
يک سایت مسابقات برنامه نویسی جدیدا ایجاد شده است به نام Codeforces. اگر دوست داشتید سری بزنید. به نظر من که خیلی جذاب است.
يکی از ويژگی های این سایت این است که هر کدام از اعضاء می توانند وبلاگ هم داشته باشند. این لینک وبلاگ من در آنجاست.

مسابقه ی آنلاین دوم نیز برگزار شد. سوال های A و D و G را من طرح کرده بودم.

برای دریافت صورت سوال ها به http://pykello.net/iaum-c3-6-1.tar مراجعه کنید.

سوال A، تنها یک پیاده سازی معمولی بود. برای دیدن کد من برای این سوال به http://wiki.pykello.net/doku.php?id=implementation:iaumc3_cheaters مراجعه کنید.

سوال D، یک سوال احتمالاتی بود که از سوال احتمالاتی دفعه ی پیش کمی آسان تر بود. راه حل من برای این سوال از نوع برنامه سازی پویا بود. تنها مشکلی که برخی از شرکت کننده ها داشتند این بود که بعضی جاها 0.00000- چاپ می کردند به جای 0.00000 که چون به نظرم مشکل حادی نبود، یک clarification فرستادم تا ملت این مشکل را درست کنند. برای دیدن کد من برای این سوال به http://wiki.pykello.net/doku.php?id=implementation:iaumc3_quiz مراجعه کنید.

راه حل من برای سوال G جستجوی دودوئی بود. برای اینکه بفهمم آیا با زمان x می شود به هدف رسید، ترتیب های مختلف نقاط را امتحان می کردم. مکان هندسی که هر کدام از نقاط در زمان x می توانند به آن بروند یک دایره است. اگر اشتراک تمام این دایره ها ناتهی بود، با زمان x می شود به هدف رسید، وگرنه نمی شود. برای دیدن کد من برای این سوال، به http://wiki.pykello.net/doku.php?id=implementation:iaumc3_atoms مراجعه کنید.

لطفا نظرتان را درباره ی سوال ها به صورت کامنت یا ایمیل ارسال کنید.

پ.ن. : ایده ی سوال G برگرفته از http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3159 بود، که توضیح راه حل را می توانید در http://wiki.pykello.net/doku.php?id=zju:feburary09 پیدا کنید. دلیلی که باعث شد فکر کنم تغییر من بر روی این سوال تبدیل به یک سوال جدید جالب می شود، این بود که گمان می کردم قسمت اشتراک دایره ها سخت ترین بخش سوال است، و راه حل های اولی که به ذهنم رسیده بود هم سخت بود، ولی راه حل آخرم چندان هم سخت نبود :)

در ضمن، نمی دانم چرا سوال B با اینکه سخت نبود تنها توسط یک نفر حل شد.

امروز مسابقه ی آنلاین اول 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 ثانیه به هر ورودی جواب داد.

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

عملکرد من در این مسابقه خوب نبود، ولی بد هم نبود. البته نسبت به دو مسابقه قبل خیلی بهتر بود :)

در سوال 250 امتیازی، نسبتا خوب عمل کردم و سعی کردم با دقت بنویسم و در نتیجه نسبتا کند نوشتم. سوال نسبتا آسانی بود، ولی در مقایسه با اکثر سوال های 250 امتیازی سخت تر بود و دقت بیشتری می خواست.

در سوال 500 امتیازی، سوال برنامه سازی پویای نسبتا آسان و سرراستی بود، انتظار داشتم بتوانم بیشتر از 400 امتیاز بدست بیاورم، ولی به علت اشتباهاتی نامعلوم، در ورودی های نمونه جواب درست نگرفتم، و پس از تلف کردن زمانی برای دیباگ، بخشی از کد را دوباره نوشتم و حدود 270 امتیاز گرفتم. اشتباه من در این سوال این بود که در جاهایی که می توانستم از تابع استفاده کنم از تابع استفاده نکرده بودم و کد کثیف و غیر قابل فهم شده بود.

با توجه به اینکه این دو سوال نسبتا زیاد طول کشید و زمان زیادی برای سوال سخت باقی نمانده بود، در زمان باقیمانده هر دو سوال را با مقداری ورودی دستی تست کردم و کدشان را دوباره بررسی کردم تا مطمئن شوم مشکلی ندارند.

در مرحله ی Challenge، سعی کردم محتاط باشم، ولی 2 کدی که تشخصیص دادم اشتباه است و می توانستم Challenge کنم، قبل از اینکه من اقدام کنم Challenge شدند. اشتباه من در این مرحله این بود که تعدادی تست خوب آماده نکرده بودم تا بتوانم سریع تر Challenge کنم.

رتبه ام 103 شد، امتیاز تاپکدرم از 2221 به 2242 افزایش پیدا کرد، که تغییر زیادی نبود، و تنها از اینکه نتیجه مثل دو دفعه پیش افتضاح نشده بود راضی بودم. ولی دوست دارم به دورانی برگردم که نصف مسابقات جزو 50 تای اول بودم :)

برای مشاهده ی توضیح و بررسی سوال های مسابقه ی ZOJ Monthly Contest, June 2009 به http://wiki.pykello.net/doku.php?id=zju:june09 مراجعه کنید. البته هنوز ناقص است، ولی امیدوارم کامل تر کنم :) البته از هر گونه کمکی استقبال می کنم :)

پ.ن. : توضیح سوال D کامل تر شد.

دیروز در این مسابقه آنلاین شرکت کردم. با توجه به اینکه با کمی دقت می توانستم جزو 4 تیم اول بشوم (به جای هشتم)، از عملکرد خودم کاملا راضی نبودم، ولی به هر حال بد هم نبود.

در این پست، به عملکرد خود و مقداری به سوال ها می پردازم، ولی بررسی کامل سوال ها را بعدا و هنگامی که همه سوال ها را حل کردم در پستی جداگانه خواهم نوشت :)

ابتدا شروع به خواندن سوال ها کردم، تا سوال های خیلی آسان را پیدا کنم. تا اینکه يکی از شرکت کنندگان سوال G را با سرعت حیرت انگیز در دقیقه 12 حل کرد. سوال سختی نبود، یک سوال احتمالاتی که با تشکیل دستگاه معادلات خطی و حل آن به راحتی حل می شد. ولی چون تعداد دفعاتی که سر مسابقه کد حل دستگاه معادلات خطی نوشته بودم کم بود، کد این مساله را با احتیاط و کند زدم و دقیقه 41 این مساله را حل کردم. یکی از کارهای مثبتی که کردم این بود که قبل از submit چند تست دستی دادم، و یکی از خطاهایی که مرتکب شده بودم را رفع کردم (سایز آرایه را کم در نظر گرفته بودم). عملکردم در این سوال نسبتا راضی کننده بود. تنها يک نکته ی منفی وجود داشت و آن این بود که کد این مساله را با تسلط کامل و سریع نزدم، و احتمالا باید مروری بر الگوریتم های استاندارد بکنم تا آن هایی را که کاملا مسلط نیستم را کاملا مسلط شوم.

سوال دومی که حل کردم، سوال B بود، که مساله ی شبیه سازی آسانی بود. نمی دانم کار درستی کردم یا نه، ولی چون اندازه ورودی مساله بزرگ بود، به جای استفاده از ساختار map زبان ++C، از ساختار داده ای استفاده کردم که عملیات مجموعه رشته ها را سریع تر انجام دهد، که برای همین کد این مساله هم کمی زیاد طول کشید (حدود 30 دقیقه). البته باز هم راضی بودم، خیلی زیاد طول نکشید، با اینکه می شد حدود 15 دقیقه صرفه جویی کرد.

سوال سومی که حل کردم، سوال I بود، که به صورت حریصانه، و با استفاده از BFS حل کردم. از عملکردم برای این مساله ناراضی بودم. اولین اشتباهی که کردم، دقت نکردم که برای تعداد پریدن ها محدودیت وجود دارد و الگوریتم و کد اولم مشکل داشت و باعث شد مدتی تلف شود. پس از اینکه برای ورودی نمونه جواب اشتباه کردم، متوجه خطایم شدم و الگوریتم صحیح را طراحی و پیاده سازی کردم که زیاد طول نکشید، ولی Wrong Answer گرفتم. پس از بررسی الگوریتم و اطمینان از صحت آن، و اطمینان از اینکه هیچ جای برنامه overflow رخ نمی دهد، و خواندن کد و نیافتن اشتباه، چند تست دستی به برنامه دادم تا تستی که برای آن جواب اشتباه می گرفتم را پیدا کنم و متوجه شوم که جایی از برنامه به جای r*r، نوشته بودم r. کمی باید بیشتر دقت کنم!

سوال چهارمی که حل کردم، سوال H بود، که یک شبیه سازی ساده بود. این مساله را نسبتا بدون خطا حل کردم، و شاید تنها نکته ی منفی این بود که حل این مساله آسان 40 دقیقه طول کشید. البته با فرض اینکه بررسی سوال های باقیمانده ی دیگر و خواندن صورت سوال احتمالا 15 دقیقه طول کشیده، خیلی هم بد نبود.

سوال پنجمی که حل کردم، سوال D بود، که با استفاده از مدل کردن مساله به صورت ضرب ماتریس حل می شد. یافتن ایده برای حل این مساله، نسبتا زیاد طول کشید، شاید حدود 40 دقیقه. ولی باز هم خیلی زیاد نبود. بزرگترین اشتباهم در این مساله که کد آن ساده بود این بود که در نوشتن کد عجله کردم و ماتریسی که تشکیل می دادم درست نبود و جواب نمی گرفتم. البته تست های صورت سوال را می گرفتم، ولی یکی از کارهای خوبی که کردم این بود که چند تست دستی ساده دادم تا متوجه شوم برنامه ام در برخی موارد اشتباه جواب می دهد. دیباگ کردن این مساله کلی طول کشید تا مدت زمان حل این مساله حدود 90 دقیقه باشد.

سوال ششمی که حل کردم، سوال F بود، که یک مساله خیلی ساده بود، ولی با این حال عجله کردم و دقت نکردم و دو اشتباه مضحک کردم که باعث شد 2 بار Wrong Answer بگیرم. البته در نتیجه ی مسابقه خیلی تاثیر نداشت، ولی اگر این 2 خطا را نمی کردم، به جای هشتم، هفتم می شدم.

سپس به سراغ سوال E رفتم، که پس از کمی بررسی روی کاغذ آن را با استفاده از برنامه سازی پویا حل کردم، و حدود 15 دقیقه به پایان مسابقه کد آن را شروع کردم که متاسفانه نتوانستم آن را بدون اشکال تمام کنم. اگر اشتباه های سوال های قبل را نکرده بودم، وقت خیلی بیشتری برای این سوال داشتم (حداقل 90 دقیقه به جای 40 دقیقه) و می توانستم 7 سواله شوم.

در مورد دو سوال باقیمانده: سوال C به نظر قابل حل با برنامه سازی پویا می آید، و سوال A احتمالا با استفاده از روش عقبگرد و حرس کردن حل می شود.

امیدوارم دفعات بعدی خطاهای کمتری مرتکب شوم :)

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

بررسی عملکرد من در این مسابقه:
در یک کلام، نتیجه ام اصلا خوب نبود، و خیلی بد بود. ولی، این نتیجه بد در اثر صرفا تقدیر و سرنوشت و بدشانسی نبود، و من بد عمل کردم. اشتباه هایی که کردم:

- برای سوال آسان، می توانستم با کمی بیشتر فکر کردن راه حلی آسان تر پیدا کنم، و امتیاز بیشتری بدست بیاورم. این اشتباه، خیلی بزرگ نبود و در نتیجه خیلی تاثیر نداشت.

- سوال متوسط: اشتباهی که کردم، این بود که ابتدا از کنارهای راه های الگوریتمی به سرعت گذشتم و سعی کردم راه های ریاضی و فرمولی پیدا کنم. بدیهی بود که می شد این سوال را با BFS حل کرد، ولی BFS عادی زمان زیادی لازم داشت و مناسب نبود. ولی اکثر مواقع ارزش دارد که آدم راه های درست با زمان بد را بیشتر بررسی کند، که در اکثر مواقع منجر به راه حلی خوب می شود. که این مورد هم یکی از آن موارد بود. بالاخره، پس از صرف مدت قابل توجهی بر روی راه های ریاضی و عدم موفقیت، بدون اینکه به اندازه ی کافی فکر کنم، چون زمان کمی باقی مانده بود، سعی کردم راه حل BFS ای با مقداری بهینه سازی ساده بنویسم شاید جواب دهد. ولی با اینکه بر روی خیلی از تست ها خوب جواب می داد، بر روی برخی تست های دستی بیشتر از زمان مجاز 2 ثانیه طول می کشید، و برای همین submit نکردم. یک اشتباه دیگر این بود که به شکل خاص این گراف دقت نکردم. به آسانی با کمی تامل می شد BFS را طوری طراحی کرد که در زمان خیلی خوبی اجرا شود.

- سوال سخت: با توجه به اینکه اکثر زمان را بر روی سوال متوسط صرف کردم، به این سوال تقریبا وقتی نرسید، و بنابراین برای این سوال تقریبا هیچ کار اشتباهی انجام ندادم :)

- مرحله Challenge: اصولا آدم باید طوری عمل کند که برای داشتن رتبه ی خوب و افزایش rating نیازی به امتیازهای challenge نداشته باشد، و تنها برای بیشتر شدن افزایش rating در این مرحله تلاش کند. به هر حال، چون در حل مساله ها خوب عمل نکرده بودم، به این مرحله امید داشتم که در این مرحله نیز 50 امتیاز از دست دادم و نتیجه بدتر از پیش شد. دو کد در اتاق ما بود که با توجه به ranklist احتمال زیاد اشتباه بودند (و بودند)، اشتباه اول من این بود که کد شخصی با رتبه بهتر را زودتر باز کردم (اشتباه بود، چون بقیه نیز همین کار را می کنند، و برای اینکه احتمال اینکه فرصت Challenge پیدا کنم بیشتر باشد، بهتر است کدی که توسط شخص با رتبه بدتر نوشته شده است را زودتر باز کنم، یعنی بر عکس بقیه). به هر حال، 100 امتیاز مفت را در اینجا از دست دادم، و دو challenge ناموفق هم کردم و در کل 50 امتیاز در این مرحله از دست دادم. یکی از کدهایی که با عدم موفقیت challenge کردم، به طور واضحی اشتباه بود، ولی test case من به طرز احمقانه ای آسان بود و کد طرف درست جواب داد. به هر حال، در این مرحله چند تصمیم استراتژیک بهتر دیگر می شد گرفت، ولی چون این مرحله خیلی مهم نیست، بیشتر به این مرحله نمی پردازم.

به هر حال، rating ام به اندازه 109 تا کاهش پیدا کرد، ولی کاملا امیدوارم که بتوانم در مسابقات بعدی خوب عمل کنم و دوباره به rating بالاتر دست پیدا کنم :) امیدوارم تا پایان امسال بتوانم به 2650 برسم. البته برای این کار باید 5-6 مسابقه مداوم بدون اشتباه و خوب عمل کنم.

بررسی سوال های مسابقه ی ZOJ Monthly Contest, Feburary 2009 : به http://wiki.pykello.net/doku.php?id=zju:feburary09 مراجعه کنید.

بررسی سوال های مسابقه ی POJ Founder Monthly Contest 2008.07.27 : به http://wiki.pykello.net/doku.php?id=pku:2008-07-27 مراجعه کنید.