ای سی ام کار تازه وارد

در این وبلاگ مطالبی در مورد برخی الگوریتم ها و راهنمایی برای حل سوالات ارائه می گردد

ای سی ام کار تازه وارد

در این وبلاگ مطالبی در مورد برخی الگوریتم ها و راهنمایی برای حل سوالات ارائه می گردد

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 , ai < 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( a1 , ... , an ) = SUM( f( ai ) )

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

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


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

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

سوال از ما بیشترین مقدار ممکن برای تابع 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 <= a1 <= b1 < a2 <= b2 < ... < ak <= bk <= n

2. bi - ai ها همگی متمایز باشند

سوال به ما 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 باید عوامل بد رو ازش حذف کنیم . ( عامل خوب نمی تونیم تولید کنیم !! )

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

Gi = GCD( a1 , ... , ai )

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


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


سوال پنجم

اگر ماتریس مورد نظر رو ماتریس مجاورت یک گراف جهتدار ( بدون وزن ) در نظر بگیریم ، توان 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( N2


کدهای من

سوال اول

سوال دوم

سوال سوم

سوال چهارم

سوال پنجم

سوال ششم

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

موافقین ۰ مخالفین ۰ ۹۳/۰۱/۰۶
رضا حسینی آشتیانی round 236 codeforces.com

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی