Let's Learn it Together !

ِAn educational blog from FCIS'2011 students ..

Avoiding TLE in ACM Problems - General Tip + Example

Posted by Omar Mohammad Othman
Sunday, February 15, 2009
comments (3)

Dear All,

Firstly, please read Prime Numbers and Primality Test.

Great! But, what if we calculate the whole array before submitting the problem to the judge?!

This is actually a very important trick that all good ACMers must know, so please read this message with great concentration.

Firstly, thank you very much, Hafez. You've chosen a very important topic; and a glitch that happens to appear every now and then in ACM problems – which is dealing with prime numbers.

I'll now solve problem 10924.

We have the string length = 20 as a maximum. This means that the "longest" string (I mean the string with the maximum sum) is "ZZZZZZZZZZZZZZZZZZZZ", which is equal to 52 * 20 = 1040. This means that – simply – the array called "prime" can be completely computed at compile time, so that we don't consume time at the judge.

So, I solved the whole issue on 2 steps. Firstly, I'll write a complete program to generate the array isPrime.

Then I'll just take this ready-made array and put it in my easy program…

And here we come to the most important lesson… that’s actually my aim behind sending this message…

WHENEVER THE DATA CAN BE INDEPENDENT OF THE INPUT, COMPUTE IT AT COMPILE TIME.

And I think you now understand that it’s actually your task to determine what data are independent of the input. This is very important, and can easily improve the performance of your solution drastically.

This is the pdf version of this article.

Labels: ,

Prime Numbers and Primality Test

Posted by hafezhafez
Thursday, February 12, 2009
comments (8)

هانتكلم شويه عن الPRIME NUMBERS "الأعداد الأولية" وازاى اعرف ان الرقم دا PRIME ولالأ

اولا يعنى ايه PRIME NUMBER ؟؟؟؟

اه صح هى دى الاجابه فعلا .... ال PRIME NUMBER هو الرقم اللى بيقبل القسمه على نفسه وعلى 1 بس يعنى مابيقبلش القسمه على اى رقم تانى.


مثال لارقام PRIME..

2 - 3 - 5 - 7 - 11 - 13 - 17 - 19 - 23 - 29 - .......................
لو لاحظنا هنا ان كل الارقام ال PRIME ارقام فردية معدا ال 2

كدة عرفنا يعنى ايهPRIME NUMBER وخدنا امثله عليه بس المشكله الى تقابلنا واحنا بنتدرب على PROBLEM SOLVING ان احنا لو مثلا عايزين نعرف اذا كان الرقم PRIME ولا لا ممكن فكرة تيجى فى دماغنا ان احنا نمشى على كل الارقام من ال 1لحد الرقم نفسه ونشوف هو بيقبل القسمه على حاجة غير ال 1 ونفسه ولا لا .....


اوكى دى فكرة سليمه 100% بس دى للارقام الصغيرة تنفع بس لو الرقم كبير شويتين اكيد لو استخدمنا الطريقه دى هاناخد time كتير اوى


عشان كدة طلعت طريقه كدة لذيذة عشان نعرف بيها الرقم دا PRIME ولا لا ومن هنا طلع ال SIEVE ALGORITHM ومن خلال الطريقه دى ممكن نعرف الرقم بمنتهى البساطه هو PRIME ولا لا .....طب ازاى الطريقه دى بتشتغل ؟؟؟؟؟؟؟


الطريقه دى من اسمها SIEVE يعنى تقطيع يعنى ايه برضه مش فاهم ؟؟؟؟؟

طب ناخد مثال عشان نفهم

وعايزين مثلا نعرف ايه هى الأرقام ال PRIME بين ال 1 وال 16 ؟؟؟؟؟؟
قبل مانبدا لازم نكون عرفين طبعا ان ال 1 مش PRIME واى رقم اصغر من ال صفر مش prime
طب عرفنا خلاص وبعدين .....


بصو طريقه عمل ال ALGORITHM ان احنا بنقسم الارقام بتاعتنا كدة

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13 - 14 - 15 - 16
طبعا قلنا ال 1 مش PRIME هانبدا من اول 2 .... ال 2 PRIME .... لو لاحظنا كدة ان ال 4 6 8 10 12 14 16 مش PRIME طب لو ركزنا شويه كدة هانلاقى ان دول مضاعفات ال 2 يعنى نفهم من كدة ايه ؟؟؟؟

ان اى رقم PRIME مضاعفاته مش PRIME طب مين قالك ياعم ان كلامك صح ..... طب تعالو كدة نجرب رقم تانى مثلا ناخد رقم 3 ونشوف مضاعفات ال 3 هيا 6 9 12 15

طبعا الكلام ده صحيح .... لأن مضاعفات العدد هتبقى بتقبل القسمة على العدد ده يعنى مضاعفات ال 3 بتقبل القسمة على ال3 ومضاعفات ال 2 بتقبل القسمة على ال2 ومضاعفات ال 5 وال 7 وال 11 و هكذا


طيب نعرف من هنا ايه بقى نشوف كدة الارقام الى عرفناها لغايه دلوقتى من 1 ل 16 هانلاقى ان ال

2 is PRIME and (4,6,8,10,12,14,16) Aren't PRIME
3 is PRIME AND (6,9,12,15) Aren't prime


طب هانيجى عند رقم 4 وهو مش PRIME لأنه من مضاعفات ال 2

نيجى على اللى بعده عند رقم 5 PRIME يبقى نطبق عليه نفس الحكايه الى هيا مضاعفاته مش PRIME
طب مضاعفات ال 5 ايه .....هانلاقيها 10 و 15


طيب ال 10 وال 15 خدناهم قبل كدة خلاص مش مشكله

وهكذا نفس الحكايه مع ال 7 وال11وال 13


نيجى بقى لفكرة الكود بتاعنا

احنا بنستخدم BOLeEaN ARRAY يعنى اللى فيها TRUE OR FALSE وكل مكان فى فيها بيعبر عن رقم ال INDEX يعنى
ARRAY[13]بتعبر عن الرقم 13


احنا بنفرض ان كل الارقام الى عندنا PRIMEيعنى من 1 ل 16 برايم ونملى الا ARRAY كلها true


وبعدين بقى بنمشى من 2 الى هو اول رقم PRIME لحد الجذر بتاع ال LIMIT الى هو16

ليه بقى عشان وحنا فوق لاحظنا ان ان احنا محتاجين بس ان احنا نعرف مضاعفات الارقام ال PRIMEعشان نقول انها مش PRIME يعنى 2 مضاعفاتها 4 6 8 10 12 14 16 وال 3 مضاعفتها 6 9 12 15 وال 5 مضاعفتها 10 15 وال 7 مضاعفتها 14 واحنا خدناها مع مضاعفات ال 2 وال 9 مضاعفتها 18 واحنا اكبر رقم عندنا 16 وهكذا عشان كدة وقفنا لحد ال 4

,وكمان لو ضربنا 4 * 4 = 16 يعنى اكبر رقم عندنا ... لو رحنا لل 5 ... 5*5 = 25 يعنى اكبر من أكبر رقم عندنا اللى هو 16 يعنى احنا مش محتاجينه توفيرا للوقت والمجهود

الكلام ده كله احنا مش بنحتاج نعمله غير مرة واحدة بس فى أول البرنامج وبعدين طول البرنامج بنستخدم ال ARRAY بتاعتنا

كدا مش فاضل الا ان احنا نختار الرقم الى عايزين نشوف هو PRIME ولا لا



هاندخل الرقم ونعمل عليه CHECK لو الماكان بتاعه فى الا اراى ب ture يبقى PRIME لكن لو مش true يبقى للاسف مش
PRIME والعملية كده بتتم فى خطوة واحدة ومش بتاخد تايم خالص
هو التايم اللى فى الاول لما بملى الاراى وبعد كده خلاص


الكود شوفوه من هنا

دى لينكات بعض المسائل الى على ال PRIME يلا بقى الى شايف انو فهم منى يروح يجرب يحلهم :D:D:D




Labels:

GCD----> Greatest common divisor

Posted by hafezhafez
comments (7)

لما كنا صغيرين مش فاكر ابتدائى ولا اعدادى كانو بيدونا حاجة اسمها العامل المشترك الاكبر الى هو دلوقتى اسمه

(GCD) Greatest common divisor

دلوقتى لو قلنا عايزين العامل المشترك الاكبر (GCD) لرقمين يعنى المطلوب منى أدور على أكبر رقم هما الاتنين بيقبلوا القسمة عليه

ناخد مثال 6 و 16

هايطلع ان أكبر رقم الرقيمن يقبلو القسمه عليه هو 2 عشان ال 16 تقبل القسمه على ال 2 وال 6 تقبل القسمه على 2 ومفيش اى رقم تانى أكبر من ال 2 ال 16 و 6 بيقبلوا القسمة عليه معا .

دلوقتى احنا لو هنجيب العامل المشترك الاكبر لرقمين بدون Algorithm هنعمل ايه ؟؟؟

ايوة صح انت(ى) بتفكر(ى) صح

· هناخد الرقم الاصغر فيهم.

· نشوف هل بيقبل القسمة على الرقم الاكبر ولا لأ.

· لو بيقبل القسمة يبقى قشطة هو ده ال العامل المشترك الاكبر (GCD) .

· ولو مش بيقبل يبقى انقص واحد واجرب هل بيقبل القسمة على الرقمين ولا لأ لحد اما الاقى رقم بيبقى القسمة على الرقمين ويبقى هو ده العامل المشترك الاكبر (GCD).

طبعا الكلام ده سليم ولكن هياخد وقت كبير جدا جدا مع الارقام الكبيرة .... علشان كده "اقليدس" فكر وطلعلنا ب Algorithm وسماه "Euclid's algorithm"

ال Algorithm بيقول الاتى

"العامل المشترك الأكبر لعددين طبيعيين A ، B يساوي العامل المشترك الأكبر للعدد الثاني B و باقي قسمة A على B ، ونكرر العملية نفسها حتى يصبح باقي القسمة مساويا الصفر ، عندئذ يكون القاسم المشترك الأكبر هو العدد الآخر." ..... المصدر ويكيبديا

ناخد مثال علشان الموضوع يبقى أوضح

العامل المشترك الأكبر(GCD) للعددين 252 و 198 :

252 = 198 * 1 + 54

دلوقتى 54 هو باقي قسمة 252 على 198

نقوم نروح نجيب العامل المشترك الاكبر (GCD) للعددين 198 و 54

198 = 54 * 3 + 36

36 هو باقي القسمة.

نكرر العملية المرة دى مع : 54 و 36

54 = 36 * 1 + 18

ومرة ثالثة

36 = 18 * 2 + 0

هنا وصلنا للصفر فيكون العدد الثاني 18 هو العامل المشترك الأكبر.


طبعا احنا هنا فى 3 معادلات جبنا العامل المشترك الاكبر انما لو كنا مشينا زى ما قلنا فى الاول كنا هناخد وقت كبير جدا لاننا كنا هنمشى من 198 لحد 18 ونعمل عمليات طول الطريق

ودى مسألة علشان لو عايزين تحلوا على ال GCD




"Euclid's algorithm" ده

int gcd(int a, int b)
{
if (b == 0)
return a;


return gcd(b, a % b);
}




وده كود تانى لل GCD ... هو معتمد على "Euclid's algorithm" لكن معمول بطريقة ثانية.


int GCD(int a,int b)

{

while (b > 0)
{

a = a % b;

a ^= b;

b ^= a;

a ^= b;

}
return a;

}




ولو فى أى اسألة اتفضلوا اسألوا

ودى نسخة PDF للمقال

Labels:

Subscribe to: Posts (Atom)