CodeForces Round #238 Div.1 & Div.2
سوال A. Gravity Flip
سوال می گفت یه نفر یه جعبه طراحی کرده که میشه توش جاذبه رو از بالا به پایین به چپ به راست تغییر داد .
یه نفر میاد n ستون مربع رو توی این جعبه می زاره و جاذبه رو تغییر میده .
به عنوان خروجی وضعیت نهایی مربع هارو از ما می خواست .
n < 100
سوال B. Domino Effect
سوال می گفت یه نفر n تا دومینو روی زمین می چینه . بعد میاد به یه سری از اونهارو یه ضربه می زنه تا شروع به افتادن کنن . هر ضربه ممکنه به طرف چپ باشه یا طرف راست .
تو هر ثانیه هر دومینوی در حال افتادن به سمت مورد نظر میوفته و دومینوی کناری رو تحت تاثیر خودش قرار میده .
سوال از ما تعداد دومینو هایی رو می خواد که نمی افتند .
n < 3000
سوال Div1 A & Div2 C. Unusual Product
سوال می گفت یه ماتریس n*n داریم که درایه هاش فقط می تونن 0 یا 1 باشن .
سوال یه عمل ضرب روی این ماتریس تعریف می کنه که به هر ماتریس یه عدد ( 0 یا 1 ) نسبت میده .
سوال به ما q تا query می داد .
تو هر query یکی از عمل های زیر باید انجام میشد
1. درایه های یک سطر داده شده flip بشه
2. درایه های یک ستون داده شده flip بشه
3. حاصل ضرب ماتریس تو خروجی چاپ بشه
n < 103 و q < 106
سوال Div1 B & Div2 D. Toy Sum
سوال یه بازی دونفره ( بین یه نفر و معلمش ) رو معرفی می کرد .
به این صورت که معلم از بین اعداد 1 تا 106 n تا عدد رو انتخاب می کرد .
حالا نوبت شاگرد بود تا m تا عدد از بین 1 تا 106 که تا به حال انتخاب نشدن انتخاب کنه تا تساوی زیر اتفاق بیوفته
اگر اعداد معلم Xi ها باشن و اعداد شاگرد Yi
SUM( Xi - 1 ) = SUM( 106 - Yj )
سوال Div1 C & Div2 E. Graph Cutting
سوال می گفت می خوایم یالهای یک گراف رو یه صورت جفت جفت کنار هم بزاریم به صورتی که
از همه یالها استفاده شده باشه
هر یال فقط در یک جفت اومده باشه
یالهای هر جفت تو یک سر مشترک باشند
n , m < 105
سوال Div1 D. Hill Climbing
سوال می گفت یه سری تپه داریم که روی یک خط قرار دارند و از چپ به راست شماره گذاری شده اند .
از روی قله هر تپه میشه با یه طناب به قله ی تپه ای دیگه رفت اگر
1. شماره قله بزرگتر از شماره قله فعلی باشه
2. از این نقطه بشه قله مقصد رو دید ( هیچ قله دیگه ای روی مسیر نباشه )
3. بین تمام قله هایی که می تونه بره ، همیشه قله با بزرگترین شماره رو انتخاب می کنه .
سوال به ما m تا query می داد تو هر query می گفت 2 نفر روی قله های شماره a و b هستند و می خواست ، کوچکترین شماره قله ای رو بدید که هردو نفر بتونن به اونجا برسند .
به عنوان ورودی محل قرار گیری مرکز تپه روی محور x ها و ارتفاع قله ی اون رو به ما میدن .
همچنین تو هر query دو شماره قله a , b
n , m < 105 . Xi < 107 . Yi < 1011
سوال Div1 E. Hamming Triples
سوال به ما m تا رشته از 0 , 1 میده . به این صورت که هر رشته فقط می تونه به صورت صعودی یا نزولی باشه .
همچنین Hamming Distance رو بین دو رشته ، تعداد اندیس هایی تعریف می کنیم که کاراکتر متناظر اونها با هم فرق داره .
حالا سوال از ما تعداد سه تایی هایی مثل ( a , b , c ) رو می خواد که
( H(a , b ) + H( b , c ) + H( c , a ماکزیمم باشه .
n < 109 , m < 105
حل
سوال اول
اگر خوب دقت کنید ، تعداد مربع های روی هر سطر از جعبه تغییر نمی کنن . فقط ممکنه به سمت چپ منتقل بشن .
برای همین بعد از تغییر جاذبه ، چپ ترین ستون ، بلندترین خواهد بود . به همین ترتیب بقیه ستون ها مرتب میشن .
لذا کافیه ورودی رو مرتب کنید .
سوال دوم
اولین نکته ای که باید بهش توجه داشته باشید اینه که تو هر لحظه حداقل یک دومینو میوفته .
لذا بعد از n ثانیه تمام اونایی که باید میوفتادن افتادند .
با توجه به اندازه ورودی ( 3000 ) کافیه عمل افتادن دومینو هارو شبیه سازی کنیم .
برای این کار n تا حافظه می گیرم برای نگهداری وضعیت قبلی بازی و n حافظه برای وضعیت بعدی بازی .
هر خونه از حافظه 4 مقدار ممکنه داشته باشه
0 : هنوز نیوفتاده
1 : به سمت چپ افتاده
2 : به سمت راست افتاده
3 : سمت چپ و راستش روش افتادند و خودش به تعادل رسیده .
جواب میشه تعداد 0 ها و 3 ها تو وضعیت نهایی بازی .
سوال سوم
طبق تعریفی که از ضرب داره ، کافیه یه بار مجموعی که قراره شمرده بشه رو بنویسید
A11 * A11 + A12 * A21 + .... +
A21 * A12 + A22 * A22 + .... +
....
حالا اگر این جمعوند هارو جابجا کنیم ، میشه اینجوری نوشت
A11*A11 + A22*A22+ ... + Ann * Ann + 2 * k
چون حاصلجمع رو توی دستگاه باینری Z2 می خواد ، عبارت قسمت آخر حتما 0 میشه .
پس حاصلضرب تو هر لحظه میشه حاصلضرب داخلی ( dot product ) قطر اصلی توی خودش .
حالا هر query که بیاد ، فقط یکی از درایه های قطر اصلی رو flip می کنه . پس جواب از نظر زوجیت با حالت قبلش یه فاز تغییر می کنه .
سوال چهارم
برای حل با توجه به ساختاری که تساوی داره ، میشه دید که اگر A رو معلم انتخاب کرده باشه باید S - A + 1 به سمت راست اضافه کرد تا تساوی درست باقی بمونه .
پس کافیه به ازای هر عددی مثل A که معلم برداشته ، دانش آموز S - A + 1 رو برداره .
حالت خاص این مساله زمانی بود که معلم هم A و هم S - A + 1 رو برداشته باشه .
تو این حالت به سمت چپ تساوی S اضافه شده . برای ایجاد تعادل کافیه دانش آموز یه جفت عدد که انتخاب نشدن رو برداره .
برای حل اعداد معلم رو تو یه set نگه داشتم و شروع به بررسی جفت های موجود کردم .
به ازای S/2 جفت موجود یکی از 3 حالت زیر پیش میاد
یا فقط یکیش انتخاب شده ، پس طرف دیگه به جواب اضافه میشه.
یا هردو انتخاب شدن ، پس باید یه جفت استفاده نشده به جواب اضافه کنیم .
یا هیچ کدوم استفاده نشدن ، پس می تونیم ازشون برای ایجاد تعادل استفاده کنیم .
سوال پنجم
از editorial خوندم که میشه ثابت کرد اگر تعداد یالهای یک گراف زوج باشه ، حتما میشه این کار رو کرد .
در عمل تو این سوال می خوایم یالهای یک گراف رو طوری جهتدار کنیم که مجموع درجه ورودی هر راس زوج باشه .
برای این کار یه زیردرخت پوشا ( spanning tree ) از گراف رو در نظر می گیریم .
یالهایی که روی درخت نیستند رو به سمت گره با عمق بیشتر جهتدار می کنیم .
حالا با شروع از عمیق ترین گره درخت ، یالهای درخت رو طوری جهتگذاری می کنیم که زوج بودن درجه ورودی حفظ بشه .
کافیه تو هر راس ، بدونیم چند تا یال به این سمت جهتگذاری شدند .
اگر این تعداد فرد بود ، کافیه جهت یالی که از پدر به این گره بوده رو به سمت این گره جهتدار کنیم .
اگر تعداد زوج بود ، جهت یال رو به سمت پدر قرار میدیم .
حالا می دونیم درجه ورودی زوج شده ، پس یالها رو جفت جفت به جواب اضافه می کنیم .
برای پیاده سازی از یک راس دلخواه DFS می زنیم و درخت DFS رو به عنوان زیردرخت پوشا در نظر می گیریم .
زمان اجرای DFS تو هر گره یک لیست از یالهایی که به سمت این گره جهتدار شدند می سازیم .
یالهایی که روی درخت DFS نیستند و یک سر اونها در راس فعلیه ، در لیست این گره قرار می گیرن ( چون این گره عمق بیشتری به گره های قبلی داره ) .
علاوه بر این ، اگر زیر درختی یال به پدرش ( راس فعلی ) رو به سمت پدر جهتگذاری کرده باشه باید به لیست اضافه بشه .
وقتی لیست کامل شد جهت یال به پدر رو تعیین می کنیم .
به طور خلاصه یه تابع DFS داریم که از ما شماره راس فعلی و شماره راس پدر رو می گیره و به ما میگه یال پدر -> فرزند رو به چه سمتی جهتگذاری بکنیم .
پیچیدگی زمانی : (O(E
سوال ششم
بوضوح هر کسی می تونه به قله ی بعدی خودش بره .
اول برای هر قله بدست میاریم که به کجا می تونه بره .
فرض کنید می خوایم برای قله i ام این مقدار رو بدست بیاریم .
یا به قله همجوار بریم که حتما میشه بهش رفت .
یا به قله ای با شماره بزرگتر از اون میریم . تو این حالت فرض کنید از قله i ام میشه به قله j ام رفت .
اگر دقت کنید از قله i+1 ام هم حتما میشه به قله j ام رفت و از قله i+1 ام هم بیشتر نمیشه جلو رفت .
لذا از بین i+1 و [next[i+1 باید انتخاب کنیم .
از طرفی می دونیم به ازای هر i مقدار next[i] > i .
پس کافیه از آخر به اول این مقادیر رو حساب کنیم .
بعد از این کار ، اگر خوب دقت کنید یه درخت ریشه دار ( راس آخر ریشه است ) داریم .
برای جواب دادن به هر query کافیه Lowest Common Ancestor رو گره متناظر با هر قله رو تو خروجی چاپ کنیم .
اگر با LCA آشنا نیستید این مطلب رو بخونید .
سوال هفتم
این سوال رو هنوز حل نکردم . تو اولین فرصت حل و این مطلب رو کامل می کنم .
کد های من
سوال هفتم - هنوز حلش نکردم
رضا حسینی آشتیانی
