ZOJ Monthly Contest, June 2009

دیروز در این مسابقه آنلاین شرکت کردم. با توجه به اینکه با کمی دقت می توانستم جزو 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 احتمالا با استفاده از روش عقبگرد و حرس کردن حل می شود.

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