Topcoder SRM 443

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