با سلام دوباره! 🙂
امیدواریم که از این مسابقه لذت برده‌باشید. راهنمایی‌ها، راه‌حل‌ها، کد صحیح سوالات به همراه چالش‌ها، همگی در ادامه‌ی مطلب آورده شده اند. در صورتی که برای سوالات و یا چالش ها راه حل های جدیدی داشتید، می توانید در بخش دیدگاه ها مطرح کنید. 🙂
ایده‌ی سوال: محمدامین رییسی
طراحی تست‌ها: مهدی امیری – محمدامین رییسی
پیش‌نیاز: –
راهنمایی: سعی کنید تمام حالات مختلف برای چرخاندن یخ را به دست آورید.
راه‌حل اول: می‌دانیم که در کل ۶ جایگشت از طول، عرض و ارتفاع یخ وجود دارد و بنابراین می توان تمام این ۶ حالت را به دست آورد. اگر در حداقل یکی از این حالات طول یخ کوچک‌تر مساوی طول جعبه و عرض یخ کوچک‌تر مساوی عرض جعبه باشد، آن ها زنده خواهند ماند. برای کوتاه‌شدن کد می‌توانید از دستوری مانند next permutation استفاده کنید.
راه‌حل دوم: یخ را طوری می‌چرخانیم که بزرگ‌ترین ضلع یخ، ارتفاع آن شود. دو ضلع دیگر یخ را p و q در نظر بگیرید. اکنون اگر داشته باشیم که min(p,q) \leq min(a,b) و max(p,q) \leq max(a,b) ، آن ها زنده خواهند ماند.
پیچیدگی زمانی: O(1)
کد مسئله‌ی آب به زبان ++C
چالش: فرض کنید شرط قرارگیری یک جعبه‌ی مکعب مستطیلی در جعبه‌ی دیگر به همین‌صورت باشد. اکنون شما n تا جعبه‌ی درباز دارید. باید بگویید که آیا روشی وجود دارد که تمام این n را در هم‌دیگر قرار داد یا خیر؟
ایده‌ی سوال: مهدی امیری
طراحی تست‌ها: مهدی امیری
پیش‌نیاز: –
راهنمایی: راه‌حل سوال در متن سوال وجود دارد!
راه‌حل: ابتدا دنباله ی a را طوری درست کنید که a_i نشان‌دهنده‌ی تعداد تکرار‌های i امین حرف انگلیسی (بزرگ یا کوچک) در رشته‌ی ورودی باشد. اکنون با یک حلقه می‌توانید آن‌چه مسئله خواسته‌است را پیاده‌سازی کنید.
پیچیدگی زمانی: O(|S|)
کد مسئله‌ی امنیتی به زبان ++C
چالش اول: الگوریتمی طراحی کنید که با گرفتن یک رشته مانند S ، یک رشته خروجی بدهد که رمز‌شده‌ی آن، رشته‌ی S باشد.
چالش دوم: الگوریتمی طراحی کنید که با گرفتن یک رشته مانند S ، باقی‌مانده‌ی تعداد رشته‌هایی که رمز‌شده‌ی آن‌ها، رشته‌ی S است، را بر 10^{9} + 7 بگوید.
ایده‌ی سوال: محمدامین رییسی
طراحی تست‌ها: محمدامین رییسی
پیش‌نیاز: –
راهنمایی: زمانی الگوریتم چرزه پاسخ صحیح نمی‌دهد که حداقل دو عدد برابر در دنباله‌ای که باید مرتب‌سازی شود، وجود داشته باشد.
راه‌حل: فرض کنید که بخواهیم دنباله‌ی tmp را با الگوریتم چرزه مرتب‌سازی کنیم. تصور کنید که دو عدد i و j وجود داشته باشد که tmp_i = tmp_j . در این صورت می‌دانیم که هر عددی در این دنباله که از tmp_i کوچک‌تر باشد، از tmp_j نیز کوچک‌تر است و بالعکس؛ بنابراین می‌توانیم بگوییم که در این‌جا عدد t برای هر‌دو یکسان و مساوی است؛ پس ما به‌جای این‌که هر دو عدد را در دنباله‌ی نهایی داشته باشیم، فقط یکی از آن‌ها را در دنباله‌ی نهایی خواهیم‌داشت. اکنون مسئله به این‌صورت تبدیل می‌شود که باید خانه‌های پر‌نشده را طوری پر کنیم که حداقل دو عدد برابر در دنباله‌ی نهایی وجود داشته‌باشد و Mex دنباله‌ی نهایی بیشینه شود. برای این‌مساله سه حالت زیر را در نظر می‌گیریم:
- در صورتی که n = 1 ، پاسخ سوال حتما
impossible است.
- در صورتی که حالت اول برقرار نبود و تمام اعداد دنباله 1- بودند، می‌توان عبارت 1, 1, 2, 3, ... , n-1 را چاپ کرد.
- در صورتی که هیچ‌کدام از حالات بالا برقرار نبود، ابتدا تمام اعداد طبیعی در بازه‌ی \left [1, n \right] که در دنباله‌ی ورودی نیستند، را در دنباله‌ی Unfixed ذخیره می‌کنیم.اکنون از ابتدای دنباله‌ی ورودی شروع می‌کنیم و هر‌جا که -1 دیدیم، اگر اولین‌باری بود که عدد -1 را دیده‌ایم، یکی از اعدادی که قبلا در دنباله وجود داشتند، را جای‌گذاری می‌کنیم؛ در غیر این صورت کوچک‌ترین عدد دنباله‌ی Unfixed را جای‌گذاری می‌کنیم و آن را از دنباله‌ی Unfixed حذف می‌کنیم.
توجه کنید که سه حالت بالا برای زمانی بودند که هیچ دو عددی از قبل برابر نبودند و در صورتی که از ابتدا دو عدد برابر وجود داشت، از اعداد کم به زیاد پر می‌کنیم.
پیچیدگی زمانی: O(n)
کد مسئله‌ی خاص به زبان ++C
چالش: فرض کنید که به‌جای ans[t+1] = a[i]; در کد، عبارت a[t+1] = a[i]; نوشته‌شده‌‌باشد و دنباله‌ی نهایی، a باشد. در این صورت پاسخ مساله به چه صورت بود؟
ایده‌ی سوال: محمدامین رییسی
طراحی تست‌ها: مهدی امیری
پیش‌نیاز: آشنایی با نظریه اعداد، آشنایی با غربال اراتستن، آشنایی با مرتب‌سازی
راهنمایی: سعی کنید اعداد اول تجزیه کننده‌ی ورودی و توان‌های هرکدام را به دست آورید.
راه‌حل: می دانیم که هر عدد را می‌توان به صورت یک عبارت یکتا مانند p_1 ^ {a_1} * p_2 ^ {a_2} * ... * p_k ^ {a_k} نوشت که در آن تمام p_i ها اعداد اول باشند. در این سوال، ما باید با پرسیدن سوال‌هایی، به‌ازای هر عدد اول مانند p_i در بازه‌ی \left [1, n \right] ، بزرگ‌ترین عدد k را پیدا کنیم به طوری که p_i ^ {k} | x . (یعنی p_i ^ {k} ، عدد x را عاد کند.) برای این‌کار، ابتدا بزرگ‌ترین t به طوری که p_i ^ {t} \leq n را پیدا می‌کنیم و ب.م.م عدد x و p_i ^ {t} را می‌پرسیم. پس ابتدا با یک غربال اراتستن تمام اعداد اول در بازه‌ی \left [1, n \right] ، را پیدا می‌کنیم و آن را تا جایی که کوچک‌تر مساوی عدد n هست، به توان می‌سانیم. در نهایت تمام اعداد را یک بار مرتب‌سازی و آن‌ها را چاپ می‌کنیم.
پیچیدگی زمانی: O(n \sqrt{n} ) (توجه کنید که این مسئله راه‌حل O(n log n) نیز دارد!)
کد مسئله‌ی حدسی به زبان ++C
چالش: فرض کنید که چرزه بتواند حداکثر q مرتبه پشت سر هم دروغ بگوید یعنی از بین هر q+1 پاسخ پشت سر هم، حداقل یکی درست باشد. در آن صورت مسئله به چه صورت حل می شد؟
ایده‌ی سوال: مهدی امیری
طراحی تست‌ها: محمدامین رییسی
پیش‌نیاز: آشنایی با تکنیک برنامه‌نویسی پویا، آشنایی با نظریه‌بازی‌ها، آشنایی با مرتب‌سازی
راهنمایی: سعی کنید از تکنیک برنامه‌نویسی پویا استفاده کنید.
راه‌حل: آرایه‌ی دو بعدی dp را در نظر بگیرید. در این آرایه dp[x][turn] نشان‌دهنده‌ی این است که اگر x قاچ پنیر داشته‌باشیم و نفر turn شروع کند، چه کسی آخرین لقمه را بر می‌دارد. می‌توان به سادگی دید که اگر dp[n][1] برابر با 1 باشد، پاسخ مسئله charze است و در غیر این صورت پاسخ مسئله پشمک است. اما به چه‌صورت می‌توان آرایه‌ی dp را بروز‌رسانی کرد؟
برای این‌کار، ابتدا جفت دنباله‌های A و B را به صورت غیر‌نزولی مرتب‌سازی می‌کنیم. برای محاسبه‌ی dp[x][turn] نیز دو حالت را در نظر می‌گیریم:
- در صورتی که turn = 1، اگر A[0] > x (دنباله‌ها را 0 بیس در نظر بگیرید.)، داریم dp[x][turn] = 2 ؛ در غیر این صورت اگر حداقل یک i وجود داشته‌باشد، به صورتی که dp[x - A[i]][2] = 2 ، داریم dp[x][turn] = 2 . اما اگر هیچ‌کدام از حالات برقرار نبود، در این‌حالت dp[x][turn] = 1 .
- در صورتی که turn = 2، اگر B[0] > x (دنباله‌ها را 0 بیس در نظر بگیرید.)، داریم dp[x][turn] = 1 ؛ در غیر این صورت اگر حداقل یک i وجود داشته‌باشد، به صورتی که dp[x - B[i]][1] = 1 ، داریم dp[x][turn] = 1 . اما اگر هیچ‌کدام از حالات برقرار نبود، در این‌حالت dp[x][turn] = 2 .
پیچیدگی زمانی: O(n \times (|A| + |B|))
مسئله‌ی صبحانه به زبان ++C
چالش: فرض کنید که هرکدام از آن‌ها از یک تعداد قاچ ممکن حداکثر q مرتبه پشت سر هم بتوانند بردارند. در این صورت مسئله چه طور حل میشد؟ باید از آرایه‌ی چند‌بعدی استفاده شود؟
ایده‌ی سوال: محمدامین رییسی
طراحی تست‌ها: محمدامین رییسی
پیش‌نیاز: آشنایی با الگوریتم هاول حکیمی، آشنایی با تئوری‌های گراف، آشنایی با مرتب‌سازی
راهنمایی: اثبات کنید که یک دنباله خفن است اگر و تنها اگر که دنباله‌ی درجه‌ای یک گراف ساده باشد
راه‌حل: سعی می‌کنیم که دنباله‌ی ورودی را با یک گراف ساده متناظر کنیم. بدین صورت که اگر دو عدد مانند i و j وجود داشته‌باشد که gcd(i,j) = 1 ، در گراف متناظر با آن با یک یال دو راس i و j را به یک‌دیگر وصل می‌کنیم. به سادگی می‌توان دید که دنباله‌ی چراهام پل دنباله‌ی اصلی، در حقیقت همان دنباله‌ی درجه‌ای گراف متناظر با آن است. اکنون اثبات می‌کنیم که به ازای یک گراف می‌توان بی‌نهایت دنباله متناظر با آن نوشت:
روی هر یال گراف یک عدد اول می‌نویسیم به صورتی که هیچ دو عددی برابر نباشد. اکنون به ازای هر راس روی آن خانه ضرب تمام یال‌های مجاورش رو می‌نویسیم (روی راس‌های ایزوله می‌توان عدد 1 را نوشت) و بدین صورت دنباله اصلی را به دست می‌آوریم. پس از آن جایی که بی‌نهایت عدد اول وجود دارد، بی‌نهایت دنباله‌ی متناظر با یک دنباله‌ی درجه‌ای وجود دارد.
اکنون باید حداکثر تعداد دنباله‌های درجه‌ای دو به دو متفاوت و زیرینه‌ی دنباله‌ی ورودی را پیدا کرد. برای این کار ابتدا یکی از دنباله‌های درجه‌ای زیرینه‌ی ورودی که مجموع اعداد آن بیشینه است، را پیدا می‌کنیم. در این مساله اگر این دنباله‌ی دوم برابر همان ورودی بود، پاسخ تعداد یال‌های گراف متناظر با دنباله‌ی دوم است در غیر این‌صورت پاسخ تعداد یال‌های گراف متناظر با دنباله‌ی دوم + 1 می‌باشد. (تعداد یال‌های گراف متناظر با یک دنباله‌ی درجه‌ای برابر با مجموع اعداد دنباله تقسیم بر 2 می باشد.)
اما چه‌طوری باید دنباله‌ی دوم را پیدا کنیم؟
برای این‌کار، باید الگوریتمی مانند الگوریتم هاول حکیمی بنویسیم. بدین‌صورت که هر بار اعداد را به صورت نزولی مرتب‌سازی می‌کنیم و از بزرگ‌ترین عدد به اعداد دیگر یال می‌کشیم. (برای فهم بهتر کد پاسخ را مشاهده کنید.)
پیچیدگی زمانی: O(n ^ {2} lg(n) ) (برای این سوال راه O(n^{2}) نیز وجود دارد.)
مسئله‌ی مرگ و زندگی به زبان ++C
چالش: فرض کنید دو دنباله‌ی a و b متفاوت باشند اگر که یک i ایی وجود داشته باشد که a_i \neq b_i . در این‌صورت مسئله چه‌طور حل می‌شود؟
ایده‌ی سوال: محمدامین رییسی
طراحی تست‌ها: پارسا عبداللهی – محمد مهدی شکری
پیش‌نیاز: آشنایی با الگوریتم بلمن‌فورد، جست‌و‌جوی دودویی، تکنیک partial sum
راهنمایی: سعی کنید مسئله را به یک مسئله‌ی کوتاه‌ترین مسیر تبدیل کنید.
راه‌حل:
لم
در یک گراف بدون دور منفی و متشکل از n راس و یک راس مبدا (با نام src ) که به تمام راس‌های دیگر مسیر دارد، اگر dist(u,v) وزن یال از راس u به راس v باشد و d_i وزن کوتاه‌ترین مسیر از راس src به i باشد، به ازای هر جفت u و v می‌دانیم که d_v \leq d_u + dist(u,v) .
اثبات
درباره‌ی درستی الگوریتم بلمن فورد برای یافتن کوتاه‌ترین مسیر مطمئن هستیم. اکنون فرض کنید که حکم درست نباشد؛ در این صورت هنوز یال uv به اصطلاح relax نشده‌است. در حالی که ادعا می‌کنیم که d_v را پیدا کرده‌ایم. پس از آن جایی که به تناقض می‌رسیم، حکم اثبات می‌شود.
یک مسئله‌ی ساده‌تر
فرض کنید که دو عدد ثابت n و k داریم و باید یک دنباله‌ی متشکل از اعداد طبیعی به طول n مانند x_1, x_2, x_3, ..., x_n را به دست بیاوریم که q را رعایت بکند. هر شرط با دو عدد i و j بیان می‌شود و از ما می‌خواهد که x_i \leq x_j + k .
راه‌حل این مسئله
از لم بیان‌شده استفاده می‌کنیم؛ ابتدا یک گراف n + 1 راسی شامل 1 راس مبدا مانند src و n راس که هرکدام متناظر با یک عضو هستند، درست می‌کنیم. سپس d_i را به صورت کوتاه‌ترین مسیر از راس src به i تعریف می‌کنیم.
بدین‌صورت که به‌ازای هر شرط در یک گراف متناظر، یک یال از راس j به راس i با وزن k می‌کشیم. هم‌چنین از راس src به تمام راس‌ها یک یال با وزن 0 می‌کشیم. در این‌صورت اگر گراف متناظر دور منفی داشت، دستگاه معادلات پاسخی ندارد. (چرا؟) در غیر این‌صورت می‌توانیم به‌جای x_i عدد d_i را بنویسیم.
تعریف دقیق آنتروپرولارت
آنتروپرولارت دنباله‌ی a_1, a_2, a_3, ..., a_n برابر با تعداد i هایی که a_i \geq a_{i+1} به علاوه‌ی یک است. برای سادگی کار با دنباله‌ی a یک دنباله‌ی b متناظر می‌کنیم به صورتی که اگر a_i \geq a_{i+1} ، b_i = 1 در غیر این‌صورت b_i = 0 . پس به سادگی می‌توان دید که آنتروپرولارت یک زیردنباله‌ی متوالی برابر با (\sum_{n=l}^{r} b_i) + 1 است.
اکنون دنباله‌ی b را به سادگی می‌توانیم به دست آوریم. برای به دست‌آوردن این دنباله، ابتدا یک مقداری کلک می‌زنیم. بدین‌صورت که چون تمام شرط‌ها روی مجموع اعداد یک باز کاربرد دارند، از روی دنباله‌ی b یک دنباله مانند part می‌سازیم که در آن part_i = \sum_{n=1}^{i} b_i . اکنون وقتی که در یک شرط سه عدد l و r و k داده می‌شود؛ از ما می‌خواهد که part_{r} - part_{l-1} = k-1 یا به عبارت دیگر part_{r} - part_{l-1} \leq k-1 و part_{l-1} - part_r \leq -k . (هر دو عبارت باید با هم بیایند!) به سادگی در این‌جا مسئله به مسئله‌ی ابتدای کار تبدیل می‌شود. پس برای هر شرط دو یال به گراف اضافه می‌کنیم:
- یک یال از راس l به راس r با وزن k - 1 رسم می‌کنیم.
- یک یال از راس r به راس l با وزن - k - 1 رسم می‌کنیم.
هم‌چنین برای این‌که هر عضو دنباله‌ی b عدد 0 یا 1 باشد دو شرط دیگر نیز اضافه می‌کنیم: (عضو 0 ام را متناظر با راس scr در نظر بگیرید.)
- به‌ازای هر 0 \leq i \leq n-1 ، یک یال از راس i به راس i + 1 یک یال با وزن 1 داریم.
- به‌ازای هر 0 \leq i \leq n-1 ، یک یال از راس i + 1 به راس i یک یال با وزن 0 داریم.
و در صورتی که گراف دور منفی داشته‌باشد، جوابی نداریم!
مسئله‌ی سخت‌تر: کمینه‌کردن مکسیموم
برای این‌کار از جست‌و‌جوی دودویی استفاده می‌کنیم (جست‌و‌جو روی عدد بیشینه) و هر‌بار یک‌سری شروط مانند زیر اضافه می‌کنیم که هرعضو کوچک‌تر مساوی آن عدد بیشینه باشد. در صورتی که با افزودن آن شرط‌ها گراف دور منفی داشت، کمینه‌ی مکسیموم بیش‌تر از آن عدد می‌باشد. هنگامی که کمینه مکسیموم را پیدا کردیم، یک‌مرتبه‌ی دیگر شرط‌ها را اضافه می‌کنیم و دنباله‌ی نهایی part را به دست می‌آوریم. اما شرطی که اضافه می‌کنیم، این است که به‌ازای هر i \leq mid \leq n یک یال از راس i به راس i - mid با وزن 1- اضافه می‌کنیم.
چگونه با کمک دنباله‌ی part، دنباله‌ی a را پیدا کنیم؟
ابتدا از روی دنباله‌ی part ، دنباله‌ی b را بدین صورت به دست می‌آوریم:
به ازای تمام 1 \leq i \leq n ، داریم: b_i = part_i - part_{i-1}
سپس از روی دنباله‌ی b ، دنباله‌ی a را بدین صورت به دست می‌آوریم:
- a_1 = 1
- اگر i \leq 2 ، داریم که اگر b_i = 0 ، در آن زمان a_i = a_{i-1} + 1 در غیر این صورت a_i = 1 .
پیچیدگی زمانی: O(n(n+q)log(n))
مسئله‌ی q مرد خشمگین به زبان ++C
چالش: فرض کنید مسئله روی درخت بیان شود یعنی از ما خواسته‌شده‌بود که آنتروپرولارت یک سری مسیرها برابر با یک سری اعداد باشد؛ در آن صورت مسئله به چه صورت حل میشد؟
موفق و پیروز باشید! 🙂
شایان ضیایی
