نصائح البرمجة التنافسية

7 نصائح يقدمها كتاب Competitive  Programming لنتائج أفضل في المسابقات البرمجية :

تعرفنا في المقال السابق عن البرمجة التنافسية  

نتابع في هذا المقال سلسلة البرمجة التنافسية وقبل البدء بشرح بنى المعطيات والخوارزميات وجدنا أنه من المفيد نقدم نصائح عملية لتحقيق أفضل النتائج في المسابقات البرمجية ولتوضيح أهم النقاط التي يجب التركيز عليها خلال فترة التدريب والتي ستقوم السلسلة بتغطيتها في المقالات القادمة.

يقدم Steven Halim  في كتابه Competitive Programming النصائح التالية والتي تعتبر نصائح ذهبية في المسابقات البرمجية:

النصيحة الأولى: تعلم كتابة الأكواد بسرعة.

تعتبر هذه النصيحة القاعدة الذهبية ومن أهم النصائح العملية في المسابقات البرمجية، فكثيراً مانرى أن الفارق في ترتيب الفريق i والفريق i+1 هو بضعة دقائق قليلة، كما أن زيادة سرعتك في كتابة الكود يوفر لك المزيد من الوقت للتفكير في بقية المسائل واختبارها.

يوفر الموقع

http://www.typingtest.com

اختبار لسرعة الكتابة على لوحة المفاتيح كما يوفر دروس تفاعلية يمكنك الاستفادة منها في زيادة سرعتك في الكتابة.

النصيحة الثانية: حدد نوع المسألة بسرعة.

يجب عليك كمبرمج أن تكون قادراً على تحديد نوع المسألة بسرعة ويجب أن تمتلك معرفة خوارزمية جيدة تمكنك من ذلك، بالإضافة إلى انه عليك الانتباه إلى أن بعض المسائل يمكن أن تصنف ضمن أكثر من نوع مثل خوارزمية Floyd warshall والتي هي حل لمسألة البيان Graph (All pairs shortest paths) بالإضافة إلى أنها أيضاً خوارزمية برمجة ديناميكية Dynamic Programming

خوارزمية Kruskal تعتبر خوارزمية لحل مسألة البيان (MST Minimum spanning trees) بالإضافة إلى أنها خوارزمية طماعة Greedy وبالتدريب المتواصل يمكنك التعرف على أنواع المسائل بسرعة وتحديد الخوارزميات المثلى التي لحل لهذه المسائل.

النصيحة الثالثة: قم بتحليل الخوارزميات.

في المسابقات البرمجية وعندما تصمم خوارزمية لحل مسألة معينة في المسابقات البرمجية يجب عليك أن تسأل نفسك هذا السؤال بإعطاء الدخل الأعظمي ( والذي يكون مشروحا بشكل واضح في نص المسألة) هل ستقوم هذه الخوارزمية بإعطاء الخرج الصحيح ضمن قيود الزمن والحجم المحددين؟

في بعض الأحيان يوجد العديد من الطرق التي يمكن بواسطتها محاولة حل المسألة، بعض الطرق قد تكون غير صحيحة وبعضها الآخر لا يكون سريع بشكل كافٍ، وهكذا.

الإستراتيجية المناسبة هي عصف الذهن وحصر الخوارزميات الممكنة واختيار "أبسط حل يعمل" ( يعمل ضمن قيود الزمن والمساحة ويعطي الحل الصحيح).

النصيحة الرابعة: احترف لغات البرمجة.

يوجد عدة لغات برمجة مدعومة في المسابقات البرمجية ومن اللغات المدعومة في المسابقة البرمجية العالمية ACM ICPC لغات C\C++ & JAVA فأي لغة منهم أحتاج أن أحترف؟

أغلب المحترفين يفضلون لغة C++ بما توفره مكتبة القوالب القياسية المضمنة بها Standard Template Language ولكننا أيضا بحاجة إلى إحتراف ال JAVA، فعلى الرغم من بطئها فإنها تمتلك مكتبات و API فعالة مضمنة بها مثل BigInteger و BigDecimal وغيرها العديد، كما تعبر برامج الجافا سهلة التنقيح بما توفره الآلة الإفتراضية للجافا  JAVA Virtual Machine من معلومات للأخطاء ضمن Stack trace.

في بعض الأحيان قد تعتبر اللغة البرمجية الحل الأمثل لحل مسألة ما، فمثلا لو طلب منا حساب 25! فإن هذه القيمة مساوية ل :

15,511,210,043,330,985,984,000,000

وهذه القيمة تتجاوز بشكل كبير مجال أكبر نمط معطيات صحيح أولي معرف ضمن اللغة والذي يساوي في الغالب (unsigned long long = 2⁶⁴-1)  وفي هذه الحالة لابد من استخدام لغة الجافا وبمكتبتها BigInteger  والتي تمكننا من حسابه بكل بساطة كما يلي:

import java.util.Scanner;

import java.math.BigInteger;

class Main { // standard Java class name in UVa OJ

public static void main(String[] args) {

BigInteger fac = BigInteger.ONE;

for (int i = 2; i <= 25; i++)

fac = fac.multiply(BigInteger.valueOf(i)); // it is in the library!

System.out.println(fac);

.النصيحة الخامسة: إحترف فن إختبار الكود

عندما تدرس مسألة معينة، وتحدد نوعها وتصمم الخوارزمية المناسبة لها، بحيث تكون هذه الخوارزمية قادرة على إعطاء الحل الصحيح ضمن قيود الحجم والزمن وترسل الكود لكنك لا تحصل على AC .

في هذه الحالة يجب عليك أن تقوم بتصميم حالات اختبار شاملة ومخادعة تغطي كافة حدود المسألة وتنفيذها على جهازك في محاولة منك لكشف مكامن الخطأ في كودك بدلا من القيام بإرسالات خاطئة والتي قد تسبب عقوبات زمنية في ال ICPC .

وهذه بعض التقنيات النموذجية التي تساعد في إختبار الكود:

1.    من أجل المسائل التي تحوي أكثر من حالة إختبار خلال تنفيذ البرنامج مرة واحدة قم بتضمين حالتي إختبار متشابهتين وقارن الخرج، وعند إختلاف خرج هاتين الحالتين فإن هذا يعني وجود متغير أو أكثر لم يتم تهيئتهم بقيم افتراضية عند بداية كل حالة إختبار.
2.    حالات الإختبار التي تقوم بتجريبها لاختبار الكود يجب أن تحتوي حالات مخادعة. فكر كأنك كاتب المسألة وحاول أن تعطي أسوأ حالة دخل قد تكون مختفية ومضمنة ضمن نص المسألة، حالات الإختبار هذه تكون مضمنة ضمن الحالات السرية للحكام وغير ظاهرة في مثال الدخل/الخرج البسيط المرفق ضمن المسألة، حالات الإختبار هذه تكون بشكل نموذجي عند N=0, N=1 أو القيم السالبة أو القيم الكبيرة والتي تقع خارج مجال متغير من 32-Bit.
3.  .  يجب على حالات الإختبار هذه أن تختبر المجال الأعظمي من القيم المحدد ضمن نص المسألة، واختبار هل يحدث TLE عند القيم الكبيرة أو يوجد أخطاء ضمن مجال المتغيرات وغيرها من الأخطاء.

النصيحة السادسة: تمرن أكثر وأكثر.

البرمجة التنافسية مثل الألعاب الرياضية يجب عليك التمرن بانتظام لتحقق نتائج أفضل، يوجد العديد من المواقع التي توفر عدد كبير من المسائل وأغلبها يقوم بفرزها حسب مستويات صعوبتها ويعطي تسميات توضيحية عن نوع المسألة.

النصيحة السابعة:العمل الجماعي كفريق.

وهذه النصيحة ليست شيئاً من السهل تعلمه ولكن يوجد بعض النقاط من الممكن أن تفيدك خلال المسابقة البرمجية:

   1- تمرن على كتابة الكود على ورقة (هذا مفيد عندما يكون زميلك بالفريق  يقوم بكتابة حله على جهاز الحاسوب وعندما ينتهي تقوم فقط بكتابة كودك على الحاسوب بأسرع وقت ممكن من دون التفكير في حل المسألة ).

2- إعتمد استراتيجية أرسل واطبع الكود في حال كان الحل صحيحاً تجاهل الورقة المطبوعة وفي حال لم يقبل الحل قم بتنقيح الكود على الورقة وإترك زميلك بالفريق يستخدم الكمبيوتر لحل المسائل (ملاحظة التنقيح من دون استخدام الكمبيوتر عملية ليست بالسهلة ).

3- إذا كان زميلك بالفريق يكتب كود خوارزمية حل مسألة ما، جهز تحدي لكوده عن طريق وضع حالات إختبار حدية لهذه الخوارزمية.

4- العامل X: كن صديقاً مع أعضاء فريقك خارج أوقات التدريب والمسابقات.

المراجع:

Steven Halim, Felix Halim, Competitve Programming 3 Copyright © 2013 by lulu.

إعداد: ربيع دغو