CodeForces Round #236 Div.1 & Div.2

سوال Div2 A. Nuts

سوال میگه یه نفر می خواد a تا آیتم رو توی یه سری جعبه بزاره که تو هر قسمت از جعبه حداکثر v تا آیتم باشه .

در شروع کار طرف b تا divisor ( جداکننده ) داره . اگر در جعبه ای x جداکننده بزاره ، جعبه به x+1

قسمت تقسیم میشه . (تو حالت اولیه فرض میشه که جعبه 1 قسمت داره )

تو هر جعبه حداکثر میشه k تا جداکننده گذاشت .

سوال به ما مقادیر k , a , b , v رو میده و کمترین تعداد جعبه هایی که لازمه تا همه آیتم هارو توش قرار بدیم رو می خواد .

k , a , b , v < 1000

سوال Div2 B. Trees in a Row

سوال به ما یه دنباله از اعداد به طول N میده و میگه می خوایم تبدیلش کنیم به یه تصاعد حسابی با قدرنسبت K تبدیل کنیم .

تو هر لحظه می تونیم یک عدد رو به هر اندازه ای کاهش یا افزایش بدیم ( بعد از انجام عمل باید عدد مثبت باقی بمونه )

سوال از ما کمترین تعداد عمل لازم برای تبدیل دنباله به تصاعد رو می خواد .

N , K , a_i < 1000

سوال Div1 A & Div2 C. Searching for Graph

یک گراف با n راس رو p-interesting میگیم اگر

1. دقیقا p+2*n یال داشته باشه

2. گراف طوقه و یال موازی نداشته باشه

3. به ازای هر زیر گراف با k راس از گراف ، زیرگراف حاصله حداکثر p+2*k یال داشته باشه

سوال به ما عددهای n , p رو میده و از ما می خواد یه گراف با شرایط فوق تولید و چاپ کنیم .

سوال Div1 B & Div2 D. Upgrading Array

یه دنباله N عضوی داریم .

برای یه دنباله تابع f رو به این صورت تعریف می کنیم .

f( a₁ , ... , a_n ) = SUM( f( a_i ) )

f( a_i ) = تعداد عوامل اول خوب - تعداد عوامل اول بد

سوال به ما یه لیست از اعداد اول بد میده ؛ بقیه خوب فرض میشن .

علاوه براین سوال به ما یه عمل معرفی می کنه که می تونیم ازش بی نهایت بار استفاده کنیم .

تو هر بار اندیسی مثل i رو انتخاب می کنیم و i عضو اول دنباله رو به ( GCD( a₁ , ... , a_i تقسیم می کنیم .

سوال از ما بیشترین مقدار ممکن برای تابع f رو می خواد .

N < 5000

سوال Div1 C & Div2 E. Strictly Positive Matrix

سوال به ما یه ماتریس n*n به درایه های نامنفی میده و می خواد ببینه که آیا عددی مثل k وجود داره که توان k ام از ماتریس درایه هایی تماما مثبت داشته باشه ؟

n < 2000

سوال Div1 D. Beautiful Pairs of Numbers

سوال از ما تعداد دنباله های k عضوی از جفت ها رو می خواد که

1. 1 <= a₁ <= b₁ < a₂ <= b₂ < ... < a_k <= b_k <= n

2. b_i - a_i ها همگی متمایز باشند

سوال به ما t تست میده تا پردازش کنیم .

تو هر تست n , k رو میده و تعداد دنباله رو می خواد .

t < 2 * 105 و n , k < 1000

سوال Div1 E. Two Rooted Trees

هنوز حلش نکردم !

حل

سوال اول

به صورت حریصانه شروع می کنیم به قرار دادن ماکزیمم تعداد جداکننده و آیتم در هر جعبه .

به وضوح اگر x تا جداکننده بزاریم تو جعبه ، حداکثر x+1) * v) تا آیتم رو می تونیم توش بزاریم .

سوال دوم

با توجه به اندازه ورودی ها به راحتی میشه دید که اولین عضو دنباله در جواب بهینه مقداری کمتر از 1000 داره .

برای حل کافیه روی تمام مقادیر ممکن برای اولین عضو ، کمترین تعداد عمل ممکن رو بدست بیاریم .

سوال سوم

برای حل به صورت greedy عمل می کنیم .

رئوس گراف رو دور یک دایره در نظر بگیرید و از 1 تا n شماره گذاری کنید .

حالا اگر قطر های به طول 1 و 2 رو توی گراف قرار بدیم ، 2*n یال تولید کردیم .

بعد از این کار کافیه p یال باقیمونده رو بکشیم .

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

اول قطرهای به طول 3 ، اگر لازم بود قطرهای به طول 4 و ...

سوال چهارم

این سوال آسون بود و greedy حل میشد .

بوضوح حداکثر n بار میشه از عمل استفاده کرد ، بعد از اون عدد اول حتما به 1 میرسه و دیگه دنباله ثابت می مونه .

با توجه به تعریف تابع f ، برای ماکزیمم کردن تابع f باید عوامل بد رو ازش حذف کنیم . ( عامل خوب نمی تونیم تولید کنیم !! )

برای این کار عدد G_i رو تعریف می کنیم .

G_i = GCD( a₁ , ... , a_i )

برای حل تا زمانی که اندیسی مثل i وجود داره که ( f( G_i منفیه ، عمل رو برای این اندیس انجام میدیم . البته بین تمام همچنین اندیس هایی بزرگترین رو انتخاب می کنیم چون با هر بار اجرای عمل به اندازه  ( i * f( G_i از مقدار نهایی f کم میشه ، بزرگترین i رو انتخاب می کنیم تا بیشترین مقدار ممکن کم بشه .

پیچیدگی زمانی : (O(N²

سوال پنجم

اگر ماتریس مورد نظر رو ماتریس مجاورت یک گراف جهتدار ( بدون وزن ) در نظر بگیریم ، توان k ام ماتریس برابر با مسیرهای به سول k در گراف اصلی خواهد بود .

لذا اگر قرار باشه تو توانی مثل k تمام درایه ها مثبت باشند ، بعدی از هر راسی به هر راسی در گراف مسیری به طول k وجود داشته باشه .

اگر در گراف مساله بین هر دو راسی یک مسیر وجود داشته باشه ، جواب Yes و در غیر این صورت No خواهد بود .

برای تعیین کردن این مورد ، کافیه ببینیم تمام رئوس گراف تو یک مولفه قویا همبند( SCC - Strongly Conneted Component ) قرار دارند یا نه ؟

بزودی درسنامه ای در مورد SCC روی وبلاگ قرار خواهد گرفت .

سوال ششم

اول از همه باید دقت کنید که حداکثر 47 تا جفت می تونیم پشت هر قرار بدیم .

چون 1 + 2 + ... + 47 > 1000 میشه .

مساله معادلا از ما می خواد تعداد حالت هایی که میشه k تا بازه از [nو1] انتخاب کنیم که هیچ دوتایی تداخل نداشته باشند .

چون طول بازه ها قراره دو به دو متمایز باشه ، می تونیم هر بازه رو به طولش متناظر کنیم .

مساله تبدیل میشه به انتخاب k تا عدد که مجموعشون کمتر از n باشه و دو به دو متمایز هستند .

برای این کار از برنامه سازی پویا ( DP ) استفاده می کنیم .

dp[i][j][k] = 

تعداد حالت هایی که میشه عدد j رو به i قسمت تقسیم کرد درحالیکه بزرگترین قسمت حداکثر k باشه .

با دونستن این مقدار می تونیم مقادیر دیگه ای رو بسازیم .

یا عدد k رو انتخاب می کنیم یا انتخاب نمی کنیم .

پس مقادیر [dp[i][j][k+1 و [dp[i+1][j+k][k+1 رو می تونیم بسازیم .

این dp تقسیم بندی هایی رو میشماره که قسمت های استفاده شده صعودی هستند .

برای اینکه تمام حالت ها شمارده بشن ، حاصل در !i باید ضرب بشه .

تا الان مقادیر جواب رو برای حاصل جمع دقیقا j بدست آوردیم اما صورت سوال جواب رو برای مقدار n می خواد !!

برای همین فرض می کنیم n خونه داشتیم و اومدیم اون رو به k دسته تقسیم کردیم . مجموع دسته های انتخاب شده j است .

به اندازه n-j خونه باقیمونده که می تونن به هر ترتیبی بین این دسته ها قرار بگیرند .

اگر دسته هارو به صورت واحد در نظر بگیریم ، n-j+k خونه داریم که می خوایم به k دسته تقسیم بشن.

این مقدار برابر است با ( C( n-j+k , k .

لذا در جواب مساله میشه

SUM( dp[k][j][n+1] * factorial(k) * C( n-j+k , k ) )   0 <= j <= n

پیچیدگی زمانی : ( O( N²

کدهای من

سوال اول

سوال دوم

سوال سوم

سوال چهارم

سوال پنجم

سوال ششم

سوال هفتم - هنوز حلش نکردم