CodeForces Round #234 Div.2
سوال A. Inna and Choose Options
سوال می گفت یه نفر میاد 12 تا کاراکتر از {X , O} انتخاب می کنه و می خواد این کاراکترهارو به ترتیب توی یه ماتریس به سایز a*b بچینه ؛ تمام سطر های ماتریس باید کامل باشند .
سوال تمام زوج مرتب هایی مثل (a,b) رو می خواد که اگر کاراکترهارو توی ماتریسی به اندازه a*b بچینیم ، یه ستون کاملا شامل X داشته باشه .
سوال B. Inna and New Matrix of Candies
سوال یه بازی رو معرفی می کنه .
این بازی روی یک صفحه مستطیل به ابعاد n و m انجام میشه .
روی هر سطر دقیقا یک کوتوله و یک آبنبات قرار گرفته .
تو هر دور از بازی یه تعداد ( شاید همه ) از سطر هارو انتخاب می کنیم .
تمام کوتوله های روی سطر های انتخاب شده شروع به حرکت به سمت راست می کنن .
تو هر لحظه یک خونه به سمت راست میرن .
اولین زمانیکه یکی از کوتوله ها به یه خونه شامل آبنبات برسه یا اینکه یکی به انتهای سطر خودش برسه ، همه حرکت خودشون رو متوقف می کنن و این دور از بازی تموم میشه .
سوال از ما می خواد کمترین تعداد دور های بازی رو بدست بیاریم یا اینکه بگیم این کار غیر ممکنه .
سوال به عنوان ورودی وضعیت صفحه بازی رو به ما میده . خونه های شامل کوتوله با حرف G و خونه های شامل آبنبات با حرف S و بقیه خونه ها با * مشخص میشن .
n,m < 1000
سوال C. Inna and Huge Candy Matrix
این سوال می گفت یه نفر یه ماتریس بزرگ داشته که روی p سلول از اون آبنبات داره .
یه نفر دیگه میاد این ماتریس رو x بار 90 درجه در جهت عقربه های ساعت دوران میده و بعد از اون y مرتبه اون رو نسبت به محور تقارن عمودی بازتاب می کنه و در آخر اون رو z مرتبه 90 درجه خلاف جهت عقربه های ساعت دوران میده .
ما محل قرارگیری قبل از دوران هارو داریم و محل جدید اونها رو می خوایم .
به عنوان ورودی سایز ماتریس رو داریم n , m < 10^9
همچنین مختصات اولیه p نقطه .
سوال D. Dima and Bacteria
سوال میگه n تا باکتری داریم که از k نوع مختلف هستند .
n < 10^5 , k < 500
باکتری هارو با شماره های 1 تا n شماره گذاری کردیم .
باکتری های مشابه شماره های متوالی دارند .
سوال میگه ما یه دستگاه خاص داریم که می تونه انرژی رو از یه باکتری به دیگری منتقل کنه .
در کل سوال به ما m نوع انتقال رو معرفی می کنه به این صورت که از باکتری با شماره u میشه انرژی رو به باکتری شماره v منتقل کرد با هزینه x .
یه توزیع از باکتری رو خوب میگیم اگر بشه انرژی رو بین باکتری های مشابه با هزینه صفر منتقل کرد .
به عنوان خروجی سوال از ما کمترین هزینه برای انتقال انرژی بین باکتری با انواع مختلف رو می خواد ، در صورتی که توزیع انرژی خوب باشه و در غیر این صورت No .
سوال E. Inna and Binary Logic
این سوال میگه از یه لیست شامل n عضو ، n لیست جدید می سازیم که عناطر لیست k ام معادل با انجام عمل AND روی k عضو متوالی از آرایه اولیه است .
یعنی :
A[k][i] = AND( a[i] , a[i+1] , ... , a[i+k-1] )
منظور از AND عمل منطقی ِAND است .
سوال حاصل جمع همه عناصر موجود در همه لیست هارو از ما می خواد .
ُسوال به ما m تا query میده که تو هر کدوم مقدار یکی از اعداد آرایه اصلی تغییر می کنه .
برای هر query باید حاصل جمع جدید رو محاسبه و چاپ کنیم .
n, m , a[i] < 10^5
حل سوالات
سوال اول
برای حل کافیه به ازای تمام مقادیر a و b کاراکتر هارو بچینید و چک کنید که یه ستون از X داره یا نه .
سوال دوم
برای حل اول محل قرار گیری G ها و S هارو معلوم می کنیم .
حالا فقط کافیه مراحل بازی رو شبیه سازی کنیم .
تو هر دور از بازی ، سطر هایی که هنوز کوتوله ی اونها به خونه آبنبات نرسیده رو انتخاب می کنیم و شروع می کنیم به یکی یکی جلو بردن کوتوله ها تا اینکه دور تموم بشه .
سوال سوم
اگر خوب دقت کنید میبینید که هر 4 بار که 90 درجه دوران بدیم به محل اولیه برمی گردیم .
پس کافیه باقیمانده به 4 هر کدوم از آرگومان هارو در نظر بگیریم .
البته تو بازتاب هر دو بار این خاصیت رو داره ، پس باقیمانده به 2 می گیریم .
برای حل کافیه یه تابع بنویسیم که مختصات یه سری نقطه رو بگیره و 90 درجه ( ساعتگرد ) اون رو دوران بده .
برای دوران پادساعتگرد کافیه 3 بار دوران بدیم .
برای بازتاب هم فقط کافیه هر نقطه (x,y) رو به (y,x) تبدیل کنیم .
سوال چهارم
اگر خوب دقت کنید یه گراف وزندار داریم و دنبال کوتاهترین مسیر بین هر دو راس از اون می گردیم .
اگر n خیلی بزرگ نبود ( n < 500 ) می تونستیم برای کل گراف از الگوریتم Floyd استفاده کنیم ولی تو این سوال n < 10^5 فرض شده ، پس باید دنبال الگوریتم های دیگه ای باشیم .
برای حل اول باید تعیین کنیم که توزیع خوب بوده یا نه .
چیزی که تو نگاه اول به نظر میرسه اینه که میشه یالهای بین باکتری های با نوع مشابه رو ایزوله درنظر گرفت و چک کرد که با عبور از یالهای با وزن صفر میشه کل این مولفه همبندی رو پیمایش کرد یا نه .
اما نکته ای که این سوال داره اینه که میشه انرژی رو به نوع دیگه ای منتقل کرد و بعد دوباره به نوع فعلی برگردوند . مثلا اگر 3 تا باکتری از 2 نوع داشته باشیم .
شماره 1و 2 = نوع 1
شماره 3 = نوع 2
و یالها به صورت 1 - 3 و 2 - 3 باشه ( وزن همه یالها صفر )
این توزیع خوب فرض میشه چون میشه بدون هزینه انرژی رو از 1 به 2 منتقل کرد .
برای اینکه این مورد رو هم در نظر گرفته باشیم ، زیرگرافی از گراف اصلی رو در نظر می گیریم که همه یالهای اون وزن صفر داشته باشند .
حالا فقط کافیه ببینیم برای هر نوع باکتری میشه همه ی هم نوعانش رو پیمایش کرد یا نه .
این کار رو با یه DFS میشه بدست آورد .
حالا اگر توزیع خوب بود باید کوتاه ترین مسیر هارو بدست بیاریم .
برای این کار یه گراف جدید از گراف اصلی می سازیم که هر نوع از باکتری متناظر با یکی از راس های اونه و یالهای گراف ، یال با کمترین وزن بین دو نوع باکتری مختلفه .
از اونجایی که این گراف جدید k راسی است می تونیم از Floyd استفاده کنیم و کوتاه ترین مسیر هارو بدست بیاریم .
پیچیدگی زمانی :
یک بار روی گراف DFS می زنیم پس (|O(|E زمان لازم داریم .
برای جواب دادن یکبار Floyd می زنیم پس (O(K^3 زمان لازم داریم .
در مجموع : (O(|ٍE| + K^3
سوال پنجم
اگر کمی دقت کنید میبینید که بیت های مختلف از اعداد نسبت به هم مستقل هستند .
لذا کافیه مساله رو برای هر بیت از اون حل کنیم .
اگر یه بیت دلخواه ( مثلا بیت k ام ) رو در نظر بگیریم دنباله تبدیل به یه سری 0 و 1 میشه .
حالا کافیه بشماریم که چند تا زیر دنباله وجود داره که همه ی عناصرش 1 باشند .
برای حل به ازای هر بیت یه Fenwick Tree درنظر می گیریم .
تو هر query ( مثلا p v ) ، چند حالت ممکنه پیش بیاد .
1. توی بیت k ام از عنصر p ام دنباله اولیه و عدد فعلی ( v ) هردو 0 یا هردو 1 هستند . تو این حالت تغییری در جواب حاصل نمیشه .
2. توی بیت k ام از عنصر p ام دنباله 1 و توی v صفر داشته باشیم . توی این حالت باید جواب رو update کنیم .
برای update کردن تو این حالت باید اولین اندیس کوچکتر از p رو بدست بیاریم که همه عناصر از اونجا تا p همگی 1 باشند ( مثلا L ) و همین طور اولین اندیس بزرگتر از p که از p تا اون اندیس همگی 1 هستند رو بدست میاریم ( مثلا R )
قبل از تغییر در آرایه ، به ازای هر دو اندیس از بازه [L,R] عنصر متناظر در لیست کلی 1 میشه .
پس اگر طول بازه رو N در نظر بگیریم ، باید به اندازه N* ( N+1 ) / 2 تا 2k از جواب کم کنیم .
بعد بازه به دو قسمت [L,p-1] و [p+1,R] تقسیم میشه . حالا باید به اندازه تعداد حالت های انتخاب 2 عضو از این بازه ها 2k به جواب اضافه کنیم .
3. توی بیت k ام از عنصر p ام دنباله 0 و توی v یک داشته باشیم . توی این حالت هم باید update کنیم .
برای update کردن جواب توی این حالت کافیه بیت k ام از عضو p رو 1 کنیم و مثل حالت قبلی LوR رو پیدا کنیم .
حالا از اونجایی که می دونستیم بیت k ام 0 بوده ، به اندازه بازه های [L,p-1] و [p+1,R] از جواب کم می کنیم و به اندازه بازه [L,R] به جواب اضافه می کنیم .
برای بدست آوردن مقادیر L یا R می تونیم از BinarySearch استفاده کنیم .
مثلا برای بدست آوردن L و اندیس p دنبال اندیسی هستیم که مجموع عناصر p تا p-L دقیقا L+1 باشه .
پیچیدگی زمانی : هر query رو در زمان (O(LogN ^ 3 انجام میدیم .
پس در کل میشه ، M * LogN ^ 3
کدهای من برای سوالات
موفق باشید
