سلام 🙂
در این مطلب راه حل‌های آزمون دوم دوره تابستان المپیاد کامپیوتر ۹۵ را قرار داده‌ایم.
همچنین در پایان هر راه حل، برای کمک به درک بهتر الگوریتم‌ها، پیاده‌سازی آن‌ها به زبان C++ موجود است.
امیدواریم برای کسانی که موفّق به حلِ کامل سوال‌ها نشده‌اند، مفید واقع شود!
موفق باشید 🙂
برای شروع می‌توان دید که اگر بزرگترین عدد در آرایه‌ی h برابر maxh باشد، تا انتهای عملیات قد هیچ کسی از maxh بیشتر نخواهد شد.
حال فرض کنید ارتفاع یک نفر x باشد، بلندترین قد در سمت چپ او maxl و بلندترین قد در سمت راست او maxr باشد. واضح است اگر او به چپ نگاه کند، تنها در صورتی قدش افزایش می‌یابد که maxl > x و اگر به راست نگاه کند قدش تنها در صورتی افزایش می‌یابد که maxr > x.
اگر هر دو مقدار maxl و maxr در ابتدا از x کوچکتر باشند، قد x تا انتهای عملیّات تغییری نخواهد کرد. امّا اگر دقیقن یکی از این دو از x بزرگتر یا مساوی باشند، مثلن maxl(maxr) قد x تا زمانی افزایش پیدا خواهد کرد که به چپ(راست) نگاه کند و قدش همچنان از maxl(maxr) کوچکتر باشد. قد نهایی چنین افرادی به راحتی تنها با استفاده از نگه داشتن تعداد کل Lها و Rها به دست خواهد آمد. چنین افرادی را «خوب‌ها» می‌نامیم!
برای سرگرمی(و البته پیدا کردن شهود!) می‌توانید بررسی کنید که به ازای هر فردی، قدبلندترین افراد سمت چپ و راستش، در لیست خوب‌ها هستند.
در غیر این صورت، هر دو مقدار maxl و maxr از x بزرگتر هستند. maxl و maxr پیش از شروع عملیات سه حالت دارند.
در این حالت واضح است که maxr عنصر ماکزیمم آرایه است و تا پایان عملیّات ثابت می‌ماند. حال تا زمانی که x < maxl باشد، آن شخص به هر طرفی که نگاه کند، قدش یک واحد اضافه می‌شود. اما maxl تنها زمانی زیاد می‌شود که افراد به راست نگاه کنند. یعنی تا زمانی maxl - x حرف L در مجموعه حرکات ظاهر نشده است، x < maxl خواهد ماند. تا آن زمان، x با نگاه به «هر» سمتی افزایش می‌یافت؛ امّا از آن مرحله به بعد، تا زمانی که x کمتر از maxr باشد، فقط نگاههای به سمت راست است که x را افزایش می‌دهد.
یعنی روند افزایش x به طور کلّی سه فاز دارد! فاز اوّل آن است که با نگاه به هر سمت قدش افزایش می‌یابد. فاز دوم آن است که فقط با نگاه به راست افزایش می‌یابد و فاز سوم آن است که قدش به maxh رسیده باشد و دیگر نتواند افزایش پیدا کند. زمان شروع و اتمام هر یک از این فاز‌ها را می‌توان با نگه داشتن دو آرایه‌ی Partial Sum که یکی تعداد Lها و دیگری تعداد Rها را در هر بازه‌ی دلخواه از عملیات به ما می‌دهد و سپس باینری سرچ روی آن‌ها پیدا کرد!
در این حالت، واضح است که maxl و maxr عناصر ماکزیمم آرایه هستند و تا اتمام روند تغییر قدها ثابت می‌مانند. در این صورت تا زمانی که x به maxl برسد، مستقل از این که به چپ نگاه می‌کند یا به راست، در هر مرحله قدش یک واحد افزایش می‌یابد و اگر به maxl برسد، تا پایان عملیّات دیگر قدش تغییر نخواهد کرد.
این حالت مانند حالت اوّل است. پس توضیح جدیدی برای آن نداریم!
پس ما سوال را با تعداد عملیاتی از O(n.log(m)) حل کردیم.
حال می‌خواهیم روش سریع‌تر و آسان‌تری برای حل سوال ارائه دهیم!
اگر تعداد کل Lها در درنباله‌ی جهت نگاه‌ها برابر cntl و تعداد کل Rها در آن دنباله برابر cntr باشد، واضح است که فردی با قد x خارج از مجموعه‌ی «خوب‌ها» می‌تواند با نگاههای به سمت چپ، به اندازه‌ی lplus = min\left\{cntl, maxl - x\right\} قدش را افزایش دهد. همچنین به اندازه‌ی rplus = min\left\{cntr, maxr - x\right\} نیز قدش را با نگاههای به سمت راست افزایش می‌دهد! یعنی قد آن فرد در انتها حداکثر برابر x + rplus + lplus خواهد بود.
در این بین، تعدادی از افزایش قدها وجود دارند که ما آن‌ها را اضافه شمرده‌ایم. یعنی آن‌هایی که پس از رسیدن قد آن فرد به ماکزیمم قد ممکن رخ می‌دهند. برای کم کردن آن‌ها، کافی است که مقدار x + rplus + lplus را، با maxh مینیموم بگیریم!
چون maxl و maxr و maxh را می‌توانیم از O(n) به دست بیاوریم، بنابراین الگوریتمی ارائه دادیم که تعداد عملیاتش از O(n) است!
کد این سوال از این جا قابل مشاهده است.
مسئله را به یک گراف مدل کنید! یک درخت T داده شده که تعدادی از راس‌های آن سیاه هستند (راس‌های دارای PokeStop). مسئله تعدادی شرط به ما می‌دهد که در هر شرط به ازای یک راس فاصله‌ی دورترین راس سیاه از آن داده شده است.
اگر هر یک از این شروط شامل راس v و فاصله d را درنظر بگیریم، مشخص می‌کند که تمامی راس‌های سیاه داخل زیردرختی هستند که از راس v به فاصله‌ی حداکثر d است و حداقل یکی از راس‌های سیاه دقیقا در فاصله‌ی d از راس v قرار دارد.
اگر به ازای هر شرط زیر درخت آن شرط را در نظر بگیریم و اشتراک این درخت‌ها را T' بنامیم، تمامی راس‌های سیاه در T' قرار دارند.
اگر یک جواب برای مسئله را در نظر بگیریم که در تمامی شرط‌ها صدق می‌کند و مجموعه‌ی S شامل راس‌های سیاه آن باشد. می‌دانیم S\subseteq V(T'). در این صورت اگر V(T') را هم به عنوان راس‌های سیاه انتخاب کنیم همچنان این درخت در تمامی شرط‌ها صدق می‌کند. به ازای هر کوئری راس v و فاصله‌ی d چون S همچنان سیاه است پس دورترین به راس v حداقل d است و چون تمامی راس‌های T' در فاصله‌ی حداکثر d از راس v هستند، فاصله‌ی دورترین به v دقیقا d خواهد بود.
اکنون می‌دانیم اگر پاسخی وجود داشته باشد، سیاه کردن تمام راس‌های T' نیر پاسخ است. عکس نقیض این حکم مشخص می‌کند اگر سیاه کردن راس‌های T' پاسخی برای مسئله نباشد، پاسخی برای مسئله وجود ندارد.
اکنون کافی است تمامی راس‌های T' را پیدا و سیاه کرده و به ازای هر راس دورترین سیاه را بیابیم. و اگر به ازای راس‌های شرط‌دار دورترین سیاه در آن شرط صدق می‌کرد پاسخ است در غیر این صورت با لم قبلی ثابت می‌شود پاسخی وجود ندارد.
حال چگونه باید T' را پیدا کرد؟
راس جدیدی به درخت اضافه می‌کنیم و اسم آن را st میگذاریم. به ازای هر کوئری مثل (d, v)، از راس st یالی به وزن -d به راس v وصل می‌کنیم. وزن سایر یال‌های گراف را نیز برابر +1 قرار می‌دهیم. حال طول بلندترین مسیر(بدون راس تکراری!) از هر راس به st را می‌خواهیم پیدا کنیم. ادّعا می‌کنیم اگر به ازای راسی، این طول مثبت باشد، آن راس در T' نخواهد بود و در غیر این صورت خواهد بود! چون اگر آن طول مثبت باشد، به این معنی است یکی از کوئری‌ها مثل (d, v) وجود دارد که تعداد یال‌های مسیر این راس به v بیشتر از d است.
درخت را از راس 1 ریشه‌دار می‌کنیم. dpDown_v برابر است با طول طولانی‌ترین مسیر از v به st که دومین راسِ آن st یا یکی از بچّه‌های v باشد. (اگر چنین مسیری وجود نداشت، مقدار آن برابر -INF خواهد بود!)
به همین منوال، dpUp_v برابر خواهد بود با طولِ طولانی‌ترین مسیر از v به st که دومین راس آن پدر v باشد. (چنین مقداری برای ریشه‌ی درخت و سایر راس‌هایی که چنین مسیری از آن‌ها شروع نمی‌شود برابر خواهد بود با -INF)
می‌توان گفت:
dpDown_v = \max(\max_{(d, v) \in Queries} d, 1 + \max_{u \in Children(v)} dpDown_u)
و همچنین
dpUp_v = \max(1 + dpUp_{par_v}, 2 + \max_{u \in brothers(v)} dpDown_u)
ابتدا با یک dfs از ریشه به راحتی dpDown_v را به ازای هر راس به دست می‌آوریم؛ همچنین به ازای هر پریفیکس و سافیکس از لیست بچّه‌های هر راس، ماکسیمم dpDown آن بچّه‌ها را نگه می‌داریم.
سپس یک dfs دیگر از ریشه می‌زنیم و به هر راس رسیدیم، dpUp آن را از روی dpUp پدرش و از روی دو آرایه‌ای که به ازای پدرش نگه داشته‌ایم به دست می‌آوریم. (چون با استفاده از آن آرایه‌ها می‌توانیم ماکزیمم مقدار dpDown برادر‌هایش را به دست آوریم)
حال دورترین فاصله از st به ازای هر راس v دقیقن برابر است با max\left\{dpDown_v, dpUp_v\right\} و می‌توانیم T' را بیابیم! با یافتن T' می‌خواستیم تمام راس‌های آن را سیاه کنیم و فاصله‌ی دورترین راس سیاه از هر راس را بیابیم. این کار را با تکرار الگوریتمی مشابه می‌توانیم به راحتی انجام دهیم 🙂
تعداد عملیات‌های الگوریتم نیز به وضوح از O(n) خواهد بود.
کد این الگوریتم رو می‌تونید از این جا ببینید 🙂
یک کد دیگر این سوال هم از این جا قابل مشاهده است.
یک کد دیگر هم برای ساب‌تسک ۳۰ نمره‌ایِ این سوال موجود هست، که می‌تونید از این جا ببینید!
فرض کنید P(X) میزان تحمّل مشتری X است.
دو نفر مثل X و Y از یک صف را در نظر بگیرید که X جلوی Y است(لزومن مجاور نیستند) و Y در بین تمام افرادی که پشت X هستند، کمترین تحمّل را دارد. در صورتی که P(X) > P(Y)، اگر در حالتی مشتری Y نان دریافت کند، واضح هست که در آن حالت به مشتری X هم نان رسیده است و اگر زمانی برسد که X قصد آتش زدن نانوایی را داشته باشد، در زمانی زودتر و یا مساوی آن زمان، Y هم همین تصمیم را می‌گیرد. پس می‌توانیم فرض کنیم P(X) = P(Y).
پس می‌توانیم به ازای هر فرد X، P(X) را برابر با کمینه مقدار اوّلیّه‌ی P(X) و مقدار P(Y) (به ازای کم تحمّل‌ترین Y که صفش با X مشترک است و بعد از X نوبتش خواهد شد) قرار دهیم.
حال فرض کنید تمام افراد را بر حسب مقدار P از کوچک به بزرگ مرتّب کرده‌ایم و ترتیب آن‌ها را در آرایه‌ای به اسم A داریم. (اگر مقدار P دو نفر از یک صفِ مشترک برابر بود، آن کسی کوچکتر است که نوبتش زودتر فرارسد و اگر مقدار P به ازای دو نفر از دو صف مختلف برابر بود، کسی کوچکتر است که اندیس صفش کوچکتر باشد)
به راحتی می‌توان نشان داد اگر حالتی وجود داشته باشد که پیش از آتش گرفتن نانوایی، w نفر نان بگیرند، حالتی هم وجود دارد که آن‌ها w مشتری ابتدای آرایه‌ی A باشند و دقیقن به ترتیب از کوچک به بزرگ نان دریافت کنند. (برای اثبات می‌توانید از اکسترمال استفاده کنید و حالتی را در نظر بگیرید که بیشترین تعداد افراد از بازه‌ای متوالی از ابتدای آرایه نان گرفته‌اند، اگر تعداد این افراد از w کمتر باشد، می‌توانید بررسی کنید که به جای بزرگترین مشتری که نان دریافت کرده است، می‌توانستیم به اوّلین مشتری از آرایه‌ی A که نان نگرفته است، نان بدهیم)
با توجّه به لمی که در پاراگراف قبل گفتیم، اگر فردی که اندیسش در A برابر i است نان بگیرد، آن نان iاُمین نانی است که پخته شده است. پس یعنی اوّلین کسی که نمی‌توانیم به او نان بدهیم، در واقع کوچک‌ترین اندیس i است که P(A_i) < i باشد! (عناصر A را با شروع از 1 شماره‌گذاری کرده‌ایم)
پس کافی‌است که روی عناصر آرایه‌ی A حرکت کنیم و مکان مذکور را به دست آوریم 🙂
اگر S = \sum{l_i}، زمان اجرای الگوریتم به علّت مرتّب‌سازی عناصر A از O(S.lg(S)) خواهد بود.
برای درک بهتر الگوریتم، می‌توانید کدِ آن را به زبان C++ در این جا و یا حتّی این جا مشاهده کنید.
