راه‌حل‌های مسابقه‌ی دست‌گرمی کدکاپ ۳

سلام.

راه‌حل‌های مسابقه‌ی دست‌گرمی کدکاپ ۳ را در ادامه‌ی مطلب می‌بینید.

• فهرست مطالب

  Toggle

  روز آزادی بیان برره‌ای

بالابرره‌ای‌ها در مراحل فرد، فرد ناسزا می‌گویند و پایین‌برره‌ای‌ها در مراحل زوج، زوج تا. پس اگر k فرد باشد پایین‌برره‌ای‌ها خشمگین می‌شوند و اگر زوج باشد بالابرره‌ای‌ها.

کد ++C از تیم Rising Force.

کد Python از تیم Pneumonoultramicroscopicsilicovolcanoconiosis.

کد Java از تیم دلم هواتو انجام داده.

کد JavaScript از تیم Undefined Error.

کد #C از تیم Jarvis.

• تیم ملی نخودخوری در برره

به ازای هر دقیقه بشمارید چند نفر درون مغازه اند و در نرخ مربوطه ضرب کنید. جواب جمع این مقادیر است. برای شمردن این که در دقیقه‌ی  d چند نفر درون مغازه اند به ازای هر نفر بررسی کنید  d بیشتر مساوی زمان ورودش به مغازه و کمتر از زمان خروجش از مغازه باشد.

کد ++C از تیم phoenix.

کد Python از تیم Pneumonoultramicroscopicsilicovolcanoconiosis.

کد Java از تیم دلم هواتو انجام داده.

• بازی منطقی در برره

به ازای هر نخود جهت افقی و عمودی را بررسی می‌کنیم، در هر جهت اگر یک طرف یک نخود دیگر و در طرف دیگر خانه‌ی خالی بود، یکی به جواب اضافه می‌کنیم. در پایان جواب را چاپ می‌کنیم. برای پیاده‌سازی می‌توان از یک آرایه‌ی دوبعدی ۷ × ۷ استفاده کرد.

کد ++C از تیم گلابی.

کد Python از تیم Pneumonoultramicroscopicsilicovolcanoconiosis.

کد Java از تیم دلم هواتو انجام داده.

• یه قل دو قل در برره
  

بیشینه‌ی درجه‌ی الدنگی برابر تعداد عددهایی‌ست که حداقل یک بار در بین سنگ‌ها ظاهر شده اند، این اعداد را اعداد ظاهر شده می‌نامیم. بیایید از چپ به راست سنگ‌ها را پیمایش کنیم. مجموعه‌ی نامزدها را مجموعه‌ای از تعدادی بازه تعریف می‌کنیم که هر کدام مطلوب‌ند و جواب از بین اینها انتخاب می‌شود.

به ازای هر عدد ظاهر شده مثل x  ، در هنگام پیمایش، x ِ (موقعیت) آخرین سنگی که این عدد روی آن نوشته شده و تا به حال دیده شده است را نگه می‌داریم، اگر این عدد تا به حال روی هیچ سنگی دیده نشده است، منفی بی‌نهایت را نگه می‌داریم و این را last_x می‌نامیم. حال در هر مرحله می‌خواهیم کوتاه‌ترین بازه‌ی مطلوبی که انتهایش سنگ فعلی (در حال پیمایش) است را بیابیم. اگر در بین اعداد ظاهر شده، عددی مثل x وجود داشته باشد که last_x = -infinity ، هیچ بازه‌ی مطلوبی وجود ندارد که انتهایش این سنگ باشد (چون عددی وجود دارد که در این بازه نیامده است و درجه‌ی الدنگی بیشینه نیست). در غیر این صورت، کمینه‌ی  last بین تمام اعداد ظاهر شده را  L می‌نامیم، بازه‌ی  L تا سنگ فعلی درجه‌ی الدنگی‌اش بیشینه است و کوتاه‌ترین بازه‌ی مطلوبی‌ست که به سنگ فعلی ختم می‌شود، این بازه را به مجوعه‌ی نامزدها اضافه می‌کنیم. جواب مسئله کوتاه‌ترین این نامزدهاست.

کد ++C از تیم Monsters.

کد Python از تیم AIBrightness.

کد Java از تیم BUG.

• سیکل گرفتن در برره

برای هر نفر نمره‌ای که کسب می‌کند را بیابید. حال بیشترین نمره‌ی کسب شده و اسم افرادی را که بیشترین نمره را کسب کرده‌اند را چاپ کنید.

کد ++C از تیم Komite tasmim migire.

کد Python از تیم  برندگان خشمگین.

کد Java از تیم D:.

• شرکت پالایش و پخش نخود در برره

فرض کنید S مجموع تمام نخودهای خواسته شده باشد. تصور کنید که به هر خانواده به مقدار نیازش نخود داده می‌شود.
در حال حاضر باید تعدادی از نخودها را پس بگیریم و M تا را باقی بگذاریم. این یعنی ما باید S-M نخود را پس بگیریم.
از آنجا که مجموع تعداد نخودهایی که خانواده‌ها از دست می دهند، عدد ثابتی‌ست، (برابر با S-M ) و ما می‌خواهیم مجموع مربعات آن را به حداقل برسانیم، نکته‌ی کلیدی این است که اعداد باید تا جای ممکن برابر باشند.
به بیان دقیق‌تر، امکان اثبات ریاضی وجود دارد (با استفاده از نابرابری حسابی و هندسی) که مجموع مربعات تعدادی عدد مثبت، با مجموع ثابت، زمانی کمینه است که آنها برابر باشند.
فرض کنید K تعداد باقی‌مانده‌ای از نخود است که باید برداشته شود (مقدار اولیه‌ی K ، S-M است). هدف ما این است که، در صورت امکان، تعداد برابری نخود را از خانواده‌ها بگیریم، به ویژه K/N بهتر است. اگر این امکان پذیر نیست، تعداد نخود پس گرفته شده باید تا حد ممکن نزدیک به K/N باشد.
اگر خانواده‌ای که حداقل مقدار نخود را می‌خواهد حداقل K/N نخود بخواهد، ما  K/N نخود از او می‌گیریم. و مسئله به N-1 خانواده کاهش می‌یابد (با کاهش N، مقدارجدید  K را محاسبه می‌کنیم و خانواده‌ی با کمترین میزان نیاز به نخود بعدی را پیدا می‌کنیم). از سوی دیگر، اگر خانواده‌ی مذکور کمتر از K/N نخود بخواهد، همه‌ی نخودهایش را می‌گیریم و به پردازش خانواده های باقی‌مانده ادامه می‌دهیم.
در نهایت، کافی‌ست مجموع مربعات تعداد نخودهایی که گرفته شده اند را چاپ کنیم.

پیچیدگی زمانی:  \mathcal{O}(n \log n).

کد ++C از تیم کام شاد.

کد Java از تیم ما.

• بازی با اعداد در برره

با استفاده از برنامه‌نویسی پویا مسئله را حل می‌کنیم. کمترین تعداد حرکت ممکن برای تبدیل کردن  x \leq b به  b را  dp_x می‌نامیم. بدیهی‌ست  dp_b = 0 . حال از  x = b - 1 شروع می‌کنیم و تا  x = 1 حرکت می‌کنیم و در هر مرحله می‌خواهیم  dp_x را به دست آوریم.

مجموعه‌ی مقسوم‌علیه‌های x بجز ۱ و خودش را div(x) بنامید، داریم:  dp_x = min(dp_{x + y} + 1), foreach\ y \in div(x) (یعنی کوچک‌ترین مقدار dp_{x+y} + 1 به ازای هر y از مقسوم‌علیه‌های x بجز ۱ و خودش).

جواب مسئله، در صورت وجود، dp_a است.

پیچیدگی زمانی:  \mathcal{O}(b \log b) .

اثبات: جمع تعداد مقسوم‌علیه‌های اعداد ۱ تا  b برابر  \lfloor b / 1 \rfloor + \lfloor b / 2 \rfloor + \lfloor b / 2 \rfloor + \ldots + \lfloor b / b \rfloor است که از  \mathcal{O}(b \log b)  است.

کد ++C از تیم Komite tasmim migire.

کد Python از تیم برندگان خشمگین.

• شرکت‌های هرمی در برره

شماره‌گذاری معمول درخت دودویی کامل به ارتفاع  H را در نظر بگیرید (شماره‌ی ریشه را ۱ بگذارید و به ازای هر راس شماره‌ی فرزند سمت چپش را دو برابر شماره‌ی خودش وشماره‌ی فرزند سمت راستش را دو برابر شماره‌ی خودش + ۱ بگذارید). شماره‌ی یک نفر در شرکت برابر دو به توان  H منهای شماره‌اش در شماره‌گذاری معمول درخت مذکور می‌باشد. حال از ریشه شروع می‌کنیم و با پیمایش رشته‌ی داده شده شماره‌ی فرد مذکور در شماره‌گذاری درخت باینری کامل و سپس شماره‌اش در شرکت را می‌یاببم.

کد ++C از تیم قضیه کوچک ممد.

کد Python از تیم برندگان خشمگین.

کد Java از تیم Mda.

• عدالت قضایی برره

یه دو شکل می‌توان سلول‌ها را به هم متصل کرد.

حالت اول این است که یکی به دوتای دیگر متصل شود. برای به دست آوردن کمترین تعداد بلوک گلی‌ای که در این حالت باید خراب شود ابتدا سلولی که قرار است به دو سلول دیگر متصل شود را انتخاب می‌کنیم و سپس به ازای هر سلول فاصله‌ی منهتنی (فاصله‌ی منهتنی دو نقطه مجموع قدر مطلق تفاضل طول و عرض آن دو نقطه است) نزدیک‌ترین نقطه‌اش به این سلول را به دست می‌آوریم. جواب جمع این دو فاصله می‌شود.

حالت دوم این است که یکی از بلوک‌های گلی پل میان سه سلول شود (یعنی هر یک از سلول‌ها مسیری از بلوک‌های گلی را خراب کنند تا به این بلوک برسند). در این صورت نیز جواب برابر جمع فاصله‌ی منهتنی این نقطه با نزدیک‌ترین خانه‌ی هر کدام از سلول‌هاست.

جواب مسئله برابر کمینه‌ی جواب به ازای هر یک از این دو حالت است.

کد ++C از تیم قضیه کوچک ممد.

کد Java از تیم Lightning.

• بازه بازی در برره

راه‌حل اول:

در یک مجموعه‌ی برره‌پسند، اگر بازه‌ها را به ترتیب شروعشان از بیشترین به کمترین مرتب کنیم، پایانشان از کمترین به بیشترین مرتب می‌شود. در نتیجه ما به دنبال بزرگترین مجموعه‌ای هستیم که اگر به ترتیب نزولی شروعشان مرتب شوند، پایانشان به ترتیب صعودی مرتب شود.

بازه‌ها را به ترتیب نزولی شروعشان مرتب کنید، حال ما در این ترتیب به دنبال بزرگترین زیردنباله‌ای از بازه‌ها (که به ترتیب نزولی شروعشان مرتب شده اند) هستیم که پایانشان صعودی‌ست. اکنون مسئله به پیداکردن بزرگترین زیردنباله‌ی صعودی تبدیل شده است. توضیح بیشتر در مورد این مسئله و راه‌حل آن را اینجا ببینید.

کد ++C از تیم کف ایکس.

راه‌حل دوم:

اندازه‌ی بزرگترین مجموعه‌ی برره‌پسند که طولانی‌ترین بازه‌ی آن بازه‌ی i اُم باشد را dp_i بنامید. جواب مسئله بیشینه‌ی مقدار  dp به ازای تمام بازه‌هاست. حال می‌خواهیم  dp_i ها را بیابیم.

بازه‌ها را بر حسب انتهایشان از کم‌ترین انتها (بازه‌ای که انتهایش از همه چپ‌تر است) به بیش‌ترین انتها مرتب می‌کنیم. حال با این ترتیب بررسی‌شان می‌کنیم. بازه‌ی فعلی (در حال بررسی) را در نظر بگیرید.  dp این بازه برابر بیشینه‌ی  dp بازه‌هایی که تا به حال بررسی شده اند و شروعشان بزرگتر-مساوی شروع بازه‌ی فعلی‌ست به علاوه‌ی ۱ است. پس اکنون به راه‌حلی با زمان اجرای  \mathcal{O}(n^2) رسیدیم.

بیایید بیشینه‌ی  dp بازه‌هایی که تا به حال بررسی شده اند و شروعشان بزرگتر-مساوی  L است را  f(L) بنامیم، حال  dp بازه‌ی در حال بررسی را می‌توان از روی  f(L) محاسبه کرد (اگر شروع بازه‌ی فعلی را x بنامیم، dp این بازه برابر f(x) + 1 است). برای پیاده‌سازی تابع  f می‌توان از segment tree یا fenwick tree استفاده کرد. در واقع مسئله به مسئله‌ی تغییر-بیشینه (از مسائل معروف segment tree) تبدیل می‌شود.

پیچیدگی زمانی:  \mathcal{O}(n \log n).

کد ++C از تیم قضیه کوچک ممد.