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

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

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

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

۷ مطلب در فروردين ۱۳۹۳ ثبت شده است

لینک سوال


مفهوم سوال

سوال میگه (d(n رو n + مجموع ارقام عدد n تعریف می کنیم .

عدد n رو یک سازنده عدد (d(n میگیم .

عددهایی که هیچ سازنده ای ندارند رو Self Number میگیم .

سوال به ما لیستی شامل k اندیس رو میده و self number متناظر با اندیس هارو از ما می خواد .

N < 107 و k < 5000


حل

۲ نظر موافقین ۲ مخالفین ۱ ۱۱ فروردين ۹۳ ، ۰۰:۱۰
رضا حسینی آشتیانی
لینک سوال

مفهوم سوال
سوال میگه یه N بهت میدم ، بگو چند تا عدد N رقمی وجود داره که اگر مربع بکنیش به 987654321 ختم میشه ؟
N < 106

حل
۱ نظر موافقین ۱ مخالفین ۰ ۱۰ فروردين ۹۳ ، ۲۳:۳۹
رضا حسینی آشتیانی
لینک سوال

مفهوم سوال
سوال به ما یه معادله به فرم a * x + b * y + c = 0 میده و از ما خواد ببینیم چند از جوابهای صیحی اون تو شرط x1 <= x <= x2 و  y1 <= y <= y2 صدق می کنند ؟

سوال به عنوان ورودی به ما a , b , c , x1 , x2 , y1 , y2 رو میده و از ما تعداد جوابهارو می خواد .
قدرمطلق همه اعداد کوچکتر از 108 است .

حل
۱ نظر موافقین ۲ مخالفین ۰ ۱۰ فروردين ۹۳ ، ۱۸:۳۷
رضا حسینی آشتیانی

لینک سوال


مفهوم سوال

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

ویترین مغازه شامل F طبقه ( سطر ) و هر طبقه شامل V گلدانه .

گلدانها به طبقه چسبیده شدند ! همچنین هر گلدان حداکثر 1 دسته گل رو می تونه تو خودش جا بده .

F تا دسته گل داریم که به ترتیب از 1 , ... , F شماره گذاری شده اند .

سوال از ما می خواد طوری گلهارو بچینیم که گل شماره i سمت سمت چپ گل شماره j باشه . ( i < j )

سوال به ما میزان زیبایی هر گلدان رو میده و ماکزیمم زیبایی ممکن و چینش نهایی رو از ما می خواد .

F , V < 100


حل

۱ نظر موافقین ۲ مخالفین ۰ ۱۰ فروردين ۹۳ ، ۱۷:۲۳
رضا حسینی آشتیانی

در یک درخت ریشه دار ، "پایین ترین جد مشترک" دو گره را دورترین راس از ریشه تعریف می کنیم که جد هردو گره باشد .


این مساله معمولا برای درخت های بزرگ مثلا 105 راسی مطرح میشود .


برای حساب کردن ( LCA( x , y به صورت زیر عمل می کنیم .

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

قبل از هر کاری باید گره x رو اونقدر به بالا منتقل کنیم تا هم ارتفاع با y بشه .

حالا اگر x = y باشه در نتیجه LCA همان x است

اگر x != y باشه ، تو این حالت از اونجاییکه فاصله x تا LCA و فاصله y تا LCA برابر است یک مقدار i دلخواه پیدا می کنیم که i امین پدر x و y با هم برابر نباشند ، از اونجایی که 

LCA( x , y ) = LCA( Parent( x , i ) , Parent( y , i ) )

می تونیم قرار بدیم ( x = Parent( x , i ) , y = Parent( y , i و مساله رو برای این زیر مساله حل کنیم .

اگر خوب دقت کنید میبینید که انتخاب i خیلی تو سرعت الگوریتم تاثیر داره .

منظور از ( Parent( x , y یعنی پدر y ام گره x .


ایده کلی ساختمان داده اینه که برای هر گره ، 20 امین پدر ، 21 امین پدر ، 22 امین پدر و ... رو نگه داریم .


حالا برای بدست آوردن k امین پدر یک گره کافیه k رو به صورت باینری نگاه کنیم .

از اونجایی که k = 2i1 + 2i2 + ... + 2in  می تونیم

اول 2i1 امین پدر k رو محاسبه کنیم سپس پدر k - 2iگره جدید رو محاسبه کنیم .

از اونجایی که یه عدد رو میشه به صورت حداکثر Log N تا جمعوند نوشت ، الگوریتم بعد از Log N محاسبه به جواب می رسه .


نحوه ساختن درخت

برای ساختن درخت کافیه برای هر گره بدونید پدرش کیه و تو چه ارتفاعی قرار داره .

برای این کار می تونید درخت از ریشه BFS یا DFS بزنید تا Dep و Parent هر گره رو معلوم کنید .

حالا با داشتن این مقادیر درخت رو می سازیم

for( int i = 0 ; i < N ; i ++ )
    for( int j = 0 ; ( 1 << j ) < N ; j ++ )
        Tree[i][j] = -1;
for( int i = 0 ; i < N ; i ++ )
    Tree[i][0] = Par[i];
for( int j = 1 ; ( 1 << j ) < N ; j ++ )
    for( int i = 0 ; i < N ; i ++ )
        Tree[i][j] = Tree[ Tree[i][j-1] ][j-1];

تو این درخت ، منظور از [Tree[i][j یعنی پدر 2j ام از گره i .

اول پدر همه رو -1 می زاریم ، یعنی اینکه هیچ پدری نداره .
بعد پدر سطح 20 ام رو مشخص می کنیم .

حالا چون به ترتیب از پایین به بالا حرکت می کنیم ، برای برست آوردن پدر 2j ام از راس i کافیه ،

پدر 2j-1 از راس i رو بدست بیاریم ( قبلا محاسبه کردیم و تو خونه [Tree[i][j-1 ذخیره کردیمش ) و بعد پدر 2j-1 ام اون گره رو بدست بیاریم ( این مقدار رو هم قبلا محاسبه کردیم )


برای بدست آوردن LCA دو گره کافیه تابع زیر رو فراخوانی کنیم

int LCA( int x , int y ) {
  if( Dep[x] < Dep[y] )
    swap( x , y );
  int log = 0;
  for( int log = 0 ; ( 1 << log ) < Dep[x] ; log ++ );
  log --;
  for( int j = log ; j >= 0 ; j -- )
    if( ( Dep[x] - Dep[y] ) & ( 1 << j ) )
      x = Tree[x][j];
  if( x == y )
    return x;
  for( int j = log ; j >= 0 ; j -- )
    if( Tree[x][j] != -1 && Tree[x][j] != Tree[y][j] )
      x = Tree[x][j], y = Tree[y][j];
  return Par[x];
}

پیچیدگی زمانی:
( O( N * Log N برای پیش محاسبات و ساختن درخت
( O( Log N برای بدست آوردن هر Query

حافظه : ( O( N * Log N 

۲ نظر موافقین ۱ مخالفین ۰ ۰۶ فروردين ۹۳ ، ۲۲:۵۱
رضا حسینی آشتیانی

سوال 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


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



حل

۱ نظر موافقین ۰ مخالفین ۰ ۰۶ فروردين ۹۳ ، ۲۰:۵۷
رضا حسینی آشتیانی

سوال 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 


۳ نظر موافقین ۰ مخالفین ۰ ۰۳ فروردين ۹۳ ، ۲۱:۲۰
رضا حسینی آشتیانی