یه کم دیر شد ولی امید وارم از راه‌حل‌ها لذت ببرید (مث سوالا که لذت بردید ?).
راه حل ها در ادامه‌ی مطلب موجود است. هم‌چنین برای همه‌ی سوال‌ها جز سوال آخر، کد اولین کسی که این سوال را حل کرده قابل مشاهده است.
نامه‌ی بد
طول هر کلمه رو حساب کنید ببینید آیا همه زوج هستن یا نه. O(n^2) یا O(n)
یا
چک کنید که هر حرفی که در جایگاه زوج (دومین حرف، چهارمین حرف، ششمین حرف، …) آمده‌اند با حرف قبلی برابر باشند. O(n)
کد ++c از مهدی جعفری، راه حل اول گفته شده.
جفای یار
دقیقن مثل دستور کار دستگاه عمل کنید؛ روند اعمال دستگاه را با دقت پیاده‌سازی کنید.
برای پیاده‌سازی ساده‌تر:
برای هر وضعیت قانون‌هایی که وضعیت ابتدایی آن‌ها آن وضعیت است را نگه دارید و سپس مثل دستور کار دستگاه عمل کنید.
کد ++C از امید آزادی
فرار یار
برای هر اتاق مدت زمانی که طول می‌کشد تا بعد از این که از اتاق قبلی وارد آن اتاق شدیم از در خروجی اتاق خارج شویم عددی ثابت است و با داشتن عدد روی در خروجی آن‌ها و مقدار k قابل محاسبه است. و جواب هر اتاق برابر مجموع جواب اتاق بعدی و مقدار زمانیست که طول می‌کشد تا از این اتاق خارج شویم.
کد ++C از محمد نعمت‌اللهی
یار و چرخ‌دنده‌ها
مسئله را با گراف مدل کنید. اگر راس متناظر چرخ‌دنده‌ای در یک موله همبندی غیر دو بخشی باشد، آن چرخ‌دنده هیچ وقت نمی‌تواند بچرخد. اگر دو راس متناظر دو چرخ‌دنده در دو مولفه‌ی مختلف باشند چرخیدن یکی از آن‌ها، بر دیگری اثری نمی‌گذارد. اگر هر دو در مولفه‌ای دو بخشی باشند با توجه به این که در یک بخش قرار دارند یا نه جهت حرکت آن‌ها نسبت به هم مشخص میشود. پس ما یک می‌توانیم مولفه‌ها و دوبخشی بودن یا نبودن آن‌ها را مشخض کنیم و مسئله حل میشود.
کد ++C از محمد نعمت‌اللهی
شیرین عسلی که پیگیر نبود
مقدار dp_{state, rem} را تعریف می‌کنیم: جواب مسئله اگر از وضعیت state شروع کنیم و rem حرف آخر نامه را به عنوان خروجی بخواهیم.
یک گراف با یال‌های جهت‌دار و بی‌وزن در نظر بگیرید که راس‌های آن ها جفت‌های (state, rem) هستند و یال‌های آن به این صورت تعریف میشوند.
به ازای هر مقدار 1 \le rem \le |s| و کاراکتر c:
- اگر قانونی بصورت state\ state2\ c وجود داشت، آن‌گاه یک یال از راس متناظر (state, rem) به راس متناظر (state2, rem) می‌گذاریم.
- اگر c = s_{|s| - rem} و قانونی مثل state\ state2\ c وجود نداشته باشد، یک یال از راس متناظر (state, rem) به راس متناظر (state, rem - 1) می‌گذاریم.
حالا اگر از راس (1, |s|)، bfs بزنیم می‌توانیم مقدار همه‌ی خانه‌های را حساب کنیم و در آخر جواب برابر کوچک‌ترین مقدار dp_{state, 0} برای stateهای مختلف است.
کد ++C از حمیدرضا کامکاری که برای بروز کردن هر لایه از مقادیر dp، از bfs استفاده کرده است.
کد ++C از محمد صانعیان که راه گفته‌شده را پیاده‌سازی کرده است.
شیرین عسل و علوم تجربی
فرض کنید یک Heap داریم که در آن برای هر موش اولین روی که زنده نیست را در آن نگه می‌داریم و یک Segment\ tree و یا Fenwick\ tree که تعداد موش‌های زنده‌ی هر بازه را به ما می‌دهد و می‌توانیم وضعیت زنده شدن و یا مردن هر موش را در آن تغییر دهیم. به این ترتیب در اول هر روز می‌توانیم با استفاده از هیپ تمام موش‌هایی که دیشب مرده‌اند را پیدا کنیم و در فنویک ثبت کنیم و برای هر درخواست سوالی با استفاده از فنویک پاسخ را به دست بیاوریم و برای هر درخواست انتقاق ویروس مقادیر اولین روز زنده نبود را در Heap آپدیت می‌کنیم.
کد ++C از محمد نعمت‌اللهی
شیرین عسل و علوم خفن
تعاریف:
Cildren(v) مجموعه‌ی بچه های راس v است و grandChildren(v) مجموعه‌ی رئوس داخل زیردرخت v.
لم۱:
\sum_{A \subseteq grandChildren(v)}^{A\neq \varnothing}(\prod_{u \in A}^{}f(u))
= \prod_{u\in grandChildren(v)}^{}(f(u) + 1) - 1
= \prod_{u \in Children(v)}^{} (f(u) + 1)^{2} - 1
پس
\log_{2}{f(v) + 1} = \sum_{u \in Children(v)}^{}2\log_{2}{(f(u) + 1)}
پس می‌توانیم تعریف کنیم dp_v برابر \log_{2}{f(v) + 1}. به این ترتیب، کمترین مقدار g روی رئوس درخت هستیم و می‌توانیم تعریف کنیم:
g(v) = \sum_{u \in Children(v)}^{}2g(u)
اما مقدار g روی رئوس درخت بسیار بزرگ است؛ بیش از دو به توان ارتفاع درخت!
لم ۲: اگر هر یال را از راسی که اگر از اون ریشه دار کنیم جواب بدتر میشود به سر دیگر یال جهت دار کنیم، هر راس به جز راس جواب یک یال خروجی خواهند داشت و همه ی مسیرای جهت دار ماکسیمال به راسِ جواب ختم میشوند. پس کافیست به ازای هر یال بفهمیم مقدار g روی کدام سرش کمتر است.
لم ۳: اگر از یک راس ریشه دار کرده باشیم، هر راس اگر یال خروجیش به پدرش نباشد قطعن به بچه‌ایست که ماکسیمم عدد بین بچه‌ها را دارد. (اگر هم دوتا بچه ماکسیمم عدد را داشته باشند، قطعن یال خروجی یا به پدر این راس است و یا این بهترین راس است.)
لم ۴: فرض کنید درخت را ریشه دار کرده باشیم و g_1(v) را تعریف کنیم مقدار g(v) برای زیردرخت v و Leaves(v) مجموعه‌ی برگ‌های زیردرخت v است. هم‌چنین dist(u, v) برابر فاصله‌ی راس u و v در درخت است. داریم:
g1(v) = \sum_{u \in Leaves(v)} 2^{dist(u, v)}
در ادامه بوسیله‌ی dfs می‌توان جهت هر یال بصورت گفته‌شده را در درخت بدست آورد؛ به این صورت که اگر قرار باشد آن راس یال خروجی به یکی از بچه‌هایش داشته باشد، به کدامیک از آن‌ها خواهد داشت. برای نگهداشتن مقدار g1 برای هر راس نیز در یک set به ازای هر راس بیت‌های یک مقدار g1(v) را نگهداری می‌کنیم و برای جمع کردن دو مقدار از مجموعه‌ی کوچکتر مقادیر را به مجموعه‌ی بزرگتر انتقال می‌دهیم. می‌توان جوری با دقت این بخش را پیاده‌سازی کرد که زمان اجرای این بخش از الگوریتم O(n\log^2(n)) شود و در نهایت برای راس ریشه مقدار g محاسبه شود.
سپس مسیر جهت دار بدست آمده از ریشه‌ی درخت تا یکی از برگ‌ها را در نظر می‌گیریم؛ راس جواب حتمن روی این مسیر قرار دارد. سپس با باینری سرچ روی این مسیر، راسی که در نهایت یال‌ها به سمت او خواهند بود را پیدا کرد و با محاسبه‌ی مقدار f روی این راس بوسیله‌ی روش گفته شده در لم ۱، پاسخ نهایی را پیدا کرد.
کد ++C
موفق باشید! 🙂
