سلام!
راهحلهای مسابقه‌ی شماره ۲۲ را می‌توانید در ادامه‌ی مطلب ببینید.
می‌خواهم از آرمین فلاح برای کمک در نهایی‌سازی مسابقه نیز تشکر کنم.
این هم راهحل سوالات مسابقه:
می‌توان در این مساله همان کاری که صورت می‌خواهد را انجام دهیم.
کد C++
می‌توان دو حالت زوج و فدر بودن را جدا‌گانه بدست آورد که اگر فرد بود جواب برابر \frac{n-1}{4} می‌شود و برای زوج جواب برابر \frac{n^2}{(n+1) \times 4} می‌شود.
کد C++
بابت مشکلات بوجود آمده در این سوال عذرخواهی می‌کنیم.
می‌توان همان کاری که صورت سوال خواسته را انجام داد. علاوه بر این، سوال راه‌حلی با پیچیدگی زمانی O(n\ k^2 \ log n + m \ log n) نیز وجود دارد.
کد C++
کد C++ با پیچیدگی زمانی O(n\ k^2 \ log n + m \ log n)
پس از مقداری برسسی می‌توان به این نتیجه رسید که سوال تعداد زیر رشته‌های ۱۱۰۰ و ۱۱۱۰ را باید بشماریم، که این کار را می‌توان با نگه داشتن تعداد ۱۱۰ ها و ۱ ها بدست آورد. برای درک بهتر راهحل کد زیر را مطالعه کنید.
کد C++
می‌توان به این نتیجه رسید که حتما عضوی از دنباله وجود دارد که تغییر نمی‌کند. و ما با تبدیل مساله به مساله‌ای که می‌خواهیم تمام اعداد دنباله را برابر کنیم می‌توانیم این مساله را به راحتی با مشخص کردن عددی که می‌خواهیم تمام اعداد را برابر آن کنیم حل کنیم. برای درک بهتر راهحل کد زیر را مطالعه کنید. علاوه بر این یک راهحل با جستجوی ترنری نیز وجود دارد.
کد C++
کد C++ با جستجوی ترنری
اگر تعداد حرکات کمتر از 4000 بود می‌توانستیم از DFS معمولی استفاده کنیم که مولفه‌ها را بدست بیاوریم، ولی با این تعداد حرکات می‌توان به‌جای آن که راس ها را خانه‌های گراف در نظر گرفت، خانه‌های هر سطر (یا همان هر y) را به بازه‌ها‌یی از خانه‌های سفید افراز می‌کنیم. سپس در بین دو بازه‌ی متوالی یال می‌گذاریم اگر حداقل یک خانه‌های با x برابر داشته‌باشند. این یال ها را می‌توان با استفاده از جستجوی دودویی قرار دهیم. سپس روی گراف حاصل می‌توانیم الگوریتم DFS را اجرا کنیم. تعداد راس‌های این گراف از O(n) است زیرا هر حرکت یک بازه را به دو قسمت تقسیم می‌کند. و تعداد یال ها هم از O(n) است زیرا هر بازه به اندازه‌ی حداکثر دو برابر طولش یال به بقیه‌ی راس‌ها دارد. پیچیدگی زمان راهحل از O(n \ log n) می‌شود. برای درک بهتر راهحل می‌توانید کد زیر را مطالعه کنید.
می‌توان به این نتیجه رسید که قدرت‌محض یک دنباله فقط به مجموع اعدادش بستگی دارد، قدرت محض یک دنباله برابر
\sum_{i=1}^{n} \binom{n-1}{i-1} \times B_{n-j} \times p_i
ضرب در مجموع آن بخش از دنباله می‌شود که B_i عدد i ام بل است که می‌توان با پیچیدگی زمانی O(n^2) بدست آورد. حال با نگه‌داشتن هر یک از آن ضرایب و استفاده از یک داده‌ساختار برای تغییر اعداد یک بازه و بدست آوردن مجموع آن می‌توان مساله را حل کرد.
یک ناحیه از جدول این‌گونه تعریف می‌شود که یک بخش همبند از جدول است که اطراف آن از # تشکیل شده‌باشد که می‌تواند به هر شکلی باشد. بعد از گرفتن ورودی دور جدول یک نوار . و سپس یک نوار # و سپس یک نوار . دور جدول قرار می‌دهیم. صاحب یک ناحیه، جزیره‌ای است که دور آن ناحیه است. حال ما برای بدست آوردن جواب از dp استفاده می‌کنیم که برای هر ناحیه از جدول، ۳ dp تعریف می‌کنیم:
- dp_{walk} : جواب برای این ناحیه به این شکل که یک مسیر باشد که از صاحب این ناحیه شروع شود و به خودش پایان یابد.
- dp_{open} : جواب برای این ناحیه به این شکل که یک مسیر باشد که از صاحب این ناحیه شروع شود.
- dp_{close} : کمترین تعداد مسیر مورد نیاز برای دیدن کل این ناحیه.
حال صاحب این ناحیه نقاط این ناحیه را به چند بخش تقسیم می‌کند. برای هر کدام از آن بخش های dp را بدست می‌آوریم. سپس برای بدست آوردن dp هر کدام از بخش های افراض شده شده، از dp هر کدام از ناحیه‌های آن جواب را بدست می‌آوریم که به این شکل اند:
cnt_{walk} = number \ of \ (dp_{walk}=dp_{close})
cnt_{open} = number \ of \ (dp_{open}=dp_{close})
cnt_{sum} = sum \ of \ all \ dp_{close}
dp_{walk} = cnt_{sum} - \frac{cnt_{open}}{2} - max(0,cnt_{walk} - max(0,1-cnt_{open}))
dp_{open} = cnt_{sum} - \frac{cnt_{open}+1}{2} - max(0,cnt_{walk})+1
dp_{close} = dp_{walk}
البته dp_{close} را باید در صورتی که cnt_{open} = cnt_{walk} باشد یک واحد افزایش دهیم.
حال برای بدست آوردن dp این ناحیه باید روی مسیری که از صاحب این ناحیه عبور می‌کند حالت‌بندی کنیم (برای dp_{walk} این بدیهی‌ست، برای dp_{open} و dp_{close} نیز به سادگی با حالت‌بندی جواب به دست می‌آید) و سپس حداقل جواب ممکن را برای این ناحیه در نظر می‌گیریم.
حال جواب مساله برابر dp_{walk} -1 برای ناحیه‌ی بیرونی می‌شود.
شایان ضیایی
