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

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

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

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

تعاریف و مفروضات:

فرض می کنیم یه رشته داریم مثل S و می خوایم ببینیم چند بار رشته ای مثل T تکرار شده.

به رشته اصلی اصطلاحا text و به رشته ای دنبالش می گردیم، pattern می گیم.

طول text رو n فرض می کنیم و طول pattern رو m.

مثلا تو رشته aaaa رشته aa 3 بار تکرار شده.

i امین prefix رشته ای مثل S رو [S[0..i تعریف می کنیم.

i امین suffix رشته ای مثل S رو [S[i..n-1 تعریف می کنیم.


بدیهی ترین راه حل اینه که بیایم از هر نقطه شروع چک کنیم که آیا زیر رشته فعلی دقیقا برابر با pattern هست یا نه.

یعنی کاری شبیه این می کنیم:

int counter = 0;
for( int i = 0 ; i + pattern.size() <= text.size() ; i ++ )
{
  bool mismatch = false;
  for( int j = 0 ; j < pattern.size() ; j ++ )
    if( text[i+j] != pattern[j] )
    {
      mismatch = true;
      break;
    }
  if( mismatch == false )
    counter ++;
}

اگه دقت کنید این پیاده سازی (O(n*m زمان نیاز داره.

سه دانشمند به نام های Knuth, Morris, Pratt الگوریتمی ابداع کردند که تو زمان (O(n+m این کار رو انجام میده. الگوریتمی که طراحی کردند به اسم سازندگانش معروف شده.( KMP )

نحوه کار الگوریتم به این شکله:

فرض کنید تو پیاده سازی بالا برای اندیسی مثل i ما تونسته باشیم k تا کاراکتر اول pattern رو match کرده باشیم و تو اندیس k+1 از pattern به mismatch رسیده باشیم.

الگوریتم بالا میاد تمام k تا match ای که داشت رو پاک می کنه و دوباره از اول برای اندیس i+1 از text کار رو تکرار می کنه.

چیزی که تو KMP اتفاق میوفته اینه که الگوریتم بر اساس یه پیش پردازشی که انجام داده، میاد یه تعداد از k تا match ای که داشت رو پاک می کنه و ادامه میده.

چطور؟

کافیه برای هر اندیس از pattern ، "طول بلندترین suffix رو بدست میارم که prefix هم باشه".

یعنی می خوایم تو i امین prefix از pattern، عددی مثل k رو پیدا کنیم که 

pattern[0..k-1] == pattern[ i-k+1..i]

به عبارت دیگه، k کاراکتر اول از pattern دقیقا برابر k کاراکتر آخر از i امین prefix از pattern باشه.


مثلا برای رشته ای مثل abaab داریم:

برای اندیس 0:

0 امین prefix میشه : a

این رشته هیچ prefix ای نداره پس مقدار k0 = -1 فرض می کنیم.(قرارداد می کنیم که -1 یعنی هیچ)

برای اندیس 1:

1 امین prefix میشه : ab

این رشته یه prefix داره و یه suffix. اینجا هم باز چون برابر هم نیستند k1 = -1 میشه.

برای اندیس 2:

2 امین prefix میشه : aba

این رشته یه prefix به طول 1 داره که دقیقا برابر suffix به طول 1 ـه. پس k2 = 1 میشه.

برای اندیس 3:

3 امین prefix میشه : abaa

این رشته هم مثل حالت قبلی میشه. پس k3 = 1 میشه.

برای اندیس 4:

4 امین prefix میشه : abaab

این رشته یه prefix به طول 2 داره که برابر suffix به طول 2 ـه. پس k4 = 2 میشه.


این اطلاعات به چه درد می خوره؟

زمانی که تو اندیسی مثلا 3 از pattern یه mismatch رخ میده، می تونیم به جای اینکه کل match هایی که داشتیم رو پاک کنیم، می تونیم، 3 - K3  از match هارو پاک کنیم، ادامه بدیم.

برای اینکه واضح تر بشه روی یه مثال میگم

text = ababaabd

pattern = abaab

الگوریتم این طور کار می کنه:

3 کاراکتر اول از pattern رو match می کنه و به 4 امین کاراکتر می رسه.

چون [pattern[3] != text[3 پس یه mismatch اتفاق افتاده.

الگوریتم اول میاد تمام 3 تا match ای که داشت رو می ریزه دور و شروع می کنه از دومین کاراکتر text ادامه دادن.

اما KMP میاد میگه چون K3 = 1 بوده، پس می تونیم 1 دونه از match هایی که داشتیم رو نگه داریم و دنبال 2 امین match بگردیم.

اتفاقی که میوفته عملا اینجوریه:

شروع می کنیم به match کردن از اندیس 0 ام.

ababaabd

abaab

    ^

تو این اندیس mismatch داریم، الگوریتم میگه به جای اینکه برگردیم به این حالت:

ababaabd

 abaab

 ^

از مقداری که پیش محاسبه کردیم استفاده کنیم و بریم به این حالت:

ababaabd

  abaab

   ^

و ادامه بدیم به match کردن. چون match شده میریم جلو تا رشته رو پیدا کنیم یا دوباره mismatch ببینیم.

هر جا mismatch دیدیم، از مقادیری که محاسبه کردیم استفاده می کنیم.


چجوری این مقادیر رو حساب کنیم؟

خود نویسندگان یه الگوریتم برای پیدا کردن Ki ها ارائه دادن که اینجوریه:

int *fail[m+1];
int j = fail[0] = -1;
for( int i = 1 ; i <= m ; i ++ )
{
	while( j >= 0 && pattern[j] != pattern[i-1] )
		j = fail[j];
	fail[i] = ++ j;
}
آرایه fail ای که تولید شده همون K ای که بالا توضیح دادمه.
اینجوری اسمش بهتره.

کد الگوریتم چجوریه؟
کد الگوریتم خیلی شبیه قسمت بالاست.
فقط باید pattern رو روی text سرچ کنیم. یعنی:

int count = 0, k = 0;
for( int i = 0 ; i < n ; i ++ )
{
	while( k >= 0 && pattern[k] != text[i] )
		k = next[k];
	if( ++ k >= m )
	{
		k = next[k];
		count ++;//match at t[i-m+1 .. i]
	}
}
تحلیل زمانی:
برای قسمت اول:
اگه دقت کنید می تونید ببینید که برای هر j داریم: [j >= fail[j
پس عبارت [j = fail[j فقط می تونه مقدار j رو کم کنه، همچنین شرطی داریم که نمی زاره j کمتر از 0 بشه.
پس اون while داخل for حداکثر به اندازه j می تونه کار کنه.
تنها جایی که j داره زیاد میشه اون عبارت ++ j ـه که دقیقا m بار داره انجام میشه.
پس در مجموع قسمت اول الگوریتم (O(m بار اجرا میشه.

برای قسمت دوم:
تحلیل زمانی الگوریتم دقیقا مثل قسمت قبل میشه پس (O(n بار انجام میشه.

لذا در مجموع این الگوریتم به (O(n+m زمان احتیاج داره.

اگه احساس می کنید بد توضیح دادم، بگید تا اصلاح کنم.

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

لینک سوال


مفهوم سوال

سوال میگه m امین روز از ماه n ام از سال 2001 چند شنبه است؟


حل

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

لینک سوال


مفهوم سوال

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

شهرها همه روی یک خط مستقیم واقع شدند. مختصات هر شهر و جمعیت شون رو داریم.

میزان نارضایتی مردم شهر i رو حاصلضرب جمعیت شهر در فاصله شهر تا مرکز تلویزیون تعریف می کنیم.

میزان نارضایتی کل، مجموع نارضایتی همه شهرهاست.

سوال از ما می خواد که یه نقطه رو برای مرکز تلویزیون انتخاب کنیم که میزان نارضایتی مینیمم باشه.

N < 15000


حل

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

لینک سوال


مفهوم سوال

عدد X رو Nearly prime number میگیم هرگاه بشه عدد X رو به صورت P1 * P2 نوشت.

سوال به ما N عدد میده و می خواد بررسی کنیم که کدومشون nearly prime هستش.

X < 109


حل

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

لینک سوال


مفهوم سوال

سوال به ما مقدارهای a,b رو میده و از ما مقدار ab - ba رو از ما می خواد.


حل

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

لینک سوال


مفهوم سوال

سوال میگه یه عدد X بهتون میدیم و شما باید عددی صحیحی رو پیدا کنید که مربعش از X بزرگتر نباشه.

به عبارت دیگه سوال جزء صحیح (sqrt(X رو از ما می خواد.

X < 101000


حل

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

لینک سوال


مفهوم سوال

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

یه صفحه N*N داریم و انگشت نفر اول روی خونه (1,1) این جدول قرار داره.

تو هر دور نفر دوم یه عدد مثل K اعلام می کنه و نفر اول باید دقیقا K بار انگشت خودش رو حرکت بده. تو هر حرکت فقط می تونه به یکی از 4 خونه همسایه که هنوز حذف نشدند بره.

بعد از انجام حرکت توسط نفر اول، نفر دوم باید حداقل 1 خونه از جدول رو حذف کنه، به شرطی که انگشت نفر اول اونجا نباشه.


سوال به ما N رو میده و می خواد به عنوان نفر دوم یه استراتژی ارائه کنیم که در آخر فقط 1 خونه باقی مونده باشه.

N < 100 و N <= K < 300


حل

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

لینک سوال


مفهوم سوال

سوال میگه (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 است .

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