4. Week 4

الهدف من الأسبوع الرابع:

1- مراجعة على Bitwise Operations.

2- التعرف على بعض المفاهيم المتعلقة بـ Bits مثل Masks و Submasks وكيفية استعمالهم لحل العديد من المسائل.

3- التعرف على إحدى طرق حل المشاكل وهو Complete Search وسنركز على واحد من أهم الـ Techniques المستخدمة في Complete Search عن طريق Bitmasks.

4- التعرف على Class مهم في C++ STL وهو Bitset.

ملاحظات هامة :

• "Complete search exploits the brute force, straight-forward, try-them-all method of finding the answer"

- هنتعرف الأسبوع دا على Complete Search وهو إحدى طرق الحل اللي بنجرب فيها جميع الاحتمالات الممكنة للوصول لحل المشكلة، وفي أسماء تانية مشهور للـ Complete Search مثل Brute-force وExhaustive Search.

- لما نبدأ التفكير في أي مسألة في المسابقات، أول حل لازم نفكر فيه هو Brute-force solution، لإن في أحيان كتيرة بيكون الحل دا سهل كتابته ومناسب للـ Time limit، وفي الحالة دي هنوفر وقت كبير من التفكير كان ممكن نضيعه لمسائل تانية في المسابقة، وأحيانا بيكون Brute-force solution صعب جدا كتابته وفي حل تاني أفضل وأسهل، ومن الحاجات المهمة جدا إننا نتأكد إن الـ Brute-force solution بيغطي الـ Corner cases.

- في مفهوم اتعرفنا عليه قبل كدا وهو Search Space: ومعناه فضاء البحث (أو مساحة البحث) ودا بكل بساطة هو الفضاء اللي فيه كل الإجابات الممكنة وبنبحث فيه عن الإجابة المناسبة لحل مشكلتنا بإستخدام خوارزمية من خوارزميات البحث.

- الإحتمالات المختلفة في Search Space نقدر نسميها States، ولما يكون عدد الـ States الممكنة في المشكلة بتاعتنا متناسب مع Time limits، والـ Complexity مش هتكون أكبر من عدد الـ States يبقى ممكن نفكر في Complete Search (مثلا: لو عدد states بيساوي مليون وtime limit بيساوي ثانية، والحل بتاعنا آخره O(number of states) يبقى ممكن نفكر في Brute-force solution).

- مهم جدا إنك تعرف تحسب الـ Complexity للـ Brute-force solution بسرعة من غير ما تكتبه بعد قراءة المسألة.

- في طريقتين لكتابة Complete Search إما Iterative عن طريق Loops أو Recursive عن طريق Recursive functions، حلول الـ Complete Search مش بتخرج عن الأشكال التالية واتعرضنا لبعضها قبل كدا تحت مسمى Brute-force، وهنتعرض للباقيين خلال الأسابيع القادمة:

- Loops or Nested Loops

- Permutations

- Bitmasks (Subsets)

- Recursion

- Backtracking

- من المفاهيم المهمة جدا المتعلقة بالـ Search Problems هو مفهوم Pruning ومعناه بالعربي القطع، والمفهوم دا بيقول إن أحيانا أثناء البحث بنكون عارفين إن بعض الطرق لو مشينا فيها مستحيل توصلنا للحل، فممكن ناخد قرار إننا منكملش في الطرق دي من بدري عشان الحل بتاعنا يبقى أسرع وبالطريقة دي احنا قدرنا نقلل Search Space، وهنتعرض للمفهوم دا أكتر في الأسابيع القادمة.

- في الأسبوع دا إن شاء الله هنتعرف أكتر على Bitmasks وازاي هتفيدنا في كتابة Complete Search Solution، وفي بعض المفاهيم الهامة اللي لازم نتعرف عليها الأول:

1. مفهوم Subset: لو احنا عندنا مجموعة A مكونة من n عنصر، وقررنا نختار بعض العناصر الموجودة في A ونعمل منهم مجموعة تانية B بشرط إن ترتيب العناصر اللي اخترناها بالنسبة لبعض في B يكون نفس ترتيبهم بالنسبة لبعض في A، يبقى المجموعة B تعتبر Subset من المجموعة A، مثال:

A = {a, b, c}

B = {a, c} // B is a subset of A

Number of subsets = 2^3 = 8

2. مفهوم Empty Subset: لو احنا قررنا منختارش أي عنصر في A، في الحالة دي مجموعة B هتكون فاضية، وبنطلق عليها Empty Subset.

3. مفهوم Power Set: الـ Power set هي عبارة عن مجموعة فيها كل الـ Subsets الممكنة، اللي نقدر نكونها من عناصر المجموعة A حتى Empty Subset، مثال:

A = {a, b, c}

Number of elements = 3

The subsets of the set A are: {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}

The power set P(A) = { { } , { a }, { b }, { c }, { a, b }, { b, c }, { c, a }, { a, b, c } }

The Power Set has 2^3 elements

- الـ Bitmask هو مجرد رقم، ولكن احنا مهتمين بالـ Binary Representation بتاعه لإنها بتمثل معنى معين عندنا لما نتعامل معاه.

على سبيل المثال لو احنا معانا نفس المجموعة A وقررنا نختار منها Subset معينة مكونة من العنصر الأول والثالث:

A = {a, b, c}

B = {a, c}

نقدر نعبر عن اختيارنا بـ Bitmask مكون من 3 bits، حيث أول bit بتمثل هل هنختار أول عنصر ولالا، وثاني bit بتمثل هل هنختار ثاني عنصر ولالا، وثالث bit بتمثل هل هنختار ثالث عنصر ولا لا، كالتالي:

Bitmask = 101

ودا معناه إننا قررنا نختار أول عنصر، ونتجاهل ثاني عنصر، ونختار ثالث عنصر، وهو دا معنى الـ Binary Representation للرقم 5.

لو احنا عايزين نعبر عن كل الـ Subsets الممكنة للمجموعة A باستخدام Bitmasks، هنلاقي إن الأرقام المكونة من 3 bits من 0 إلى 7 (أو من 0 إلى 2^3 - 1)، بتمثل كل الـ Subsets الممكنة:

Bitmask in Decimal |Bitmask in Binary | Subset

0 | 000 | {}

1 | 001 | {a}

2 | 010 | {b}

3 | 011 | {a, b}

4 | 100 | {c}

5 | 101 | {a, c}

6 | 110 | {b, c}

7 | 111 | {a, b, c}

- احنا كدا فهمنا يعني ايه Mask، طيب يعني ايه Submask؟ لو احنا معانا مجموعة واخترنا منها Subset عبرنا عنها بـ Mask بيمثل الـ Subset دي، وعايزين نشوف كل الـ Subsets الممكنة من الـ Subset اللي احنا اخترناها، في الحالة دي أي اختيار ممكن نقدر نعبر عنه بـ Submask من الـ Mask الأصلي.

مثال:

Mask = 1010

All possible submasks are: {0000, 0010, 1000, 1010}

- الـ Submask مستحيل يحتوى على bit قيمتها 1 كانت في الأصل قيمتها 0 في الـ Mask الأصلي، ولكن العكس ممكن.

- مسألة: لنفترض إن معانا Array فيها n رقم، والمطلوب إننا نطبع كل الـ Subsets اللي مجموع عناصرها بيساوي X.

الحل: الحل المباشر للمسألة دي هو إنك تجرب كل الـ Subsets الممكنة، ولما تختار Subset معينة، تشوف مجموع العناصر فيها كام، ولو بيحقق الشرط هتضيفها للإجابة، وعشان نقدر نعدي على كل Subsets الممكنة هنستخدم Bitmasks.

- زي ما قولنا كل Subset نقدر نعبر عنها بـ Bitmask مكونة من n bits، الـ bit الأولى معناها هل هنختار الرقم الأول في الarray معانا في الـ Subset ولالأ، وهكذا لحد n-th bit.

- عدد الـ Subsets الممكنة (متضمنة Empty Subset) بيساوي 2^n

- كل رقم من 0 إلى 1 - (2^n) بيعبر عن Subset مختلفة.

- دلوقتي عشان ننفذ الحل بتاعنا:

1. هنمشي على الأرقام باستخدام Loop من أول 0 لحد 1 - (2^n).

2. وبعدين كل مرة هنشوف أول n bits في الرقم.

3. ولو لقينا قيمة أي bit بواحد، يبقى معنى كدا إننا هنختار العنصر المقابل للـ bit من الـ Array وهنضيفه للـ Subset.

4. بما إننا مهتمين بالـ Sum، فاحنا هنعمل متغير نخزن فيه مجموع الأرقام الموجودة في Subset.

5. وفي النهاية هنقرر إذا كان Subset Sum بيساوي X ولالأ عشان نعد الـ Subset في الإجابة.

حل المسألة:

https://ideone.com/fTUiev

- آخر حاجة هنتعرف عليها الأسبوع دا هي Bitset وهي مفيدة في الـ Optimizations أكتر، وأحيانا في تبسيط الكود.

- Bitset is a container which can be represented as an array of bool (e.g : 10001,111001) but each Boolean value is not stored separately instead bitset optimizes the space such that each bool takes 1 bit space only.

الخطوة القادمة بعد مشاهدة الفيديوهات:

1- الدخول إلى Training Group والانضمام له من خلال الضغط على كلمة Apply Join في حالة عدم الانضمام.

2- بدء حل مسائل Week #4 بالترتيب.

ملاحظات هامة:

1- المسائل كثيرة العدد إلى حد ما وتحتاج إلى بعض التفكير.

2- ينتهي الأسبوع يوم الجمعة الساعة 12 مساء.

3- ستبدأ المسابقة الأسبوعية يوم الجمعة الساعة 10 مساء ومدتها ثلاث ساعات.

4- لا تنسى تحديث بيانات تقدمك في Training Sheet بشكل دوري.

5- لا تتردد في السؤال على FB Community Training Group إذا واجهتك مشكلة ما أو لم تستطع فهم سؤال ما أو أردت طلب مصادر إضافية.