'שלב ב
חושבים שאתם מסוגלים?
שלב ב’, אליו ניגשים מאות עוברי שלב א', נערך כחודש - חודשיים לאחר שלב א' במוקדים שונים ברחבי הארץ. בשלב זה משתמשים בדף ועט ולא במחשב. השאלות בשלב זה הן אלגוריתמיות, אך בניגוד לשלב א’ שבו המתחרים מקבלים קלט ספציפי וצריכים לתת את הפלט עבורו, בשלב זה על המתחרים לכתוב אלגוריתם כללי ויעיל ככל האפשר שפותר את הבעיה. בכל שאלה, יש לתאר את האלגוריתם באמצעות פסאודו קוד או שפת תכנות לבחירת המתחרה, ולהסביר את הרעיון מאחוריו, את נכונותו ואת ההבחנות שהביאו אליו. הדגש הוא על אלגוריתמים יעילים הפועלים בסיבוכיות זמן נמוכה ככל האפשר. גם בשלב זה אין צורך בידע תכנותי, ומספיק לתאר אלגוריתמים במילים.
כדי להתכונן לשלב זה, כדאי ללמוד על אלגוריתמים, לראות שאלות לדוגמה (ואחרי שהצלחתם לפתור גם את הפתרונות כדי להבין כיצד לנסח אותם), וללמוד נושאים בסיסיים במדעי המחשב - כגון חיפוש בינארי, תכנות דינאמי, סיבוכיות של אלגוריתמים ואלגוריתמי מיון.
בהמשך נעלה לכאן מדריכי הכנה מפורטים יותר עם מקורות לימוד :)
עד אז, המקור המומלץ על ידינו לבעלי רקע קודם בתחום והיכרות עם C++ הוא הספר https://cses.fi/book/book.pdf (באנגלית), פרקים 1-4 ו-6-7.
מצורפים גם חומרים בעברית על אלגוריתמים, סיבוכיות וחיפוש בינארי שניתן לעבור עליהם. למי שמעדיף הרצאות, יש לנו הרצאות מוקלטות בנושאי סיבוכיות, מיונים וחיפוש בינארי, ותכנות דינמי.
דוגמה לשאלת שלב ב'
בוגרת הנבחרת, עדי ריבקין, מציגה שאלה משלב ב' 2020
דוגמה למבנה שאלת שלב ב'
ניקח את השאלה שניתנה כדוגמה לשאלת שלב א' כאן.
בשלב ב' יכולה להופיע השאלה בצורה הכללית שלה, למשל כך:
לסבתא סמית יש n תפוחים במשקלים שונים. משקלי התפוחים נתונים במערך apple.
יש לה גם משקל חשמלי, שהיא יכולה לשים עליו תפוחים (המשקל מספיק גדול גם כדי לשים את כל התפוחים עליו), והמשקל מראה לה על הצג את המשקל הכולל של התפוחים שעליו, בגרמים.
סבתא סמית רוצה לדעת מה המספר החיובי השלם הקטן ביותר שהיא לא יכולה לגרום למשקל להציג (או במילים אחרות – שלא יכול להווצר על ידי חיבור של משקלים של תפוחים שיש לה).
עזרו לסבתא סמית, וכתבו עבורה אלגוריתם (יעיל) שיפתור את הבעיה.
שימו לב להבדלים בין השלבים. בשלב א' נתנו לנו אוסף של משקלים וביקשו למצוא את המשקל הקטן ביותר שאי אפשר להציג (תשובה מספרית). לצורך כך היינו צריכים למצוא אלגוריתם לעצמנו ו"להריץ" אותו על דף לקבלת התשובה הסופית.
בשלב ב', אנחנו צריכים לכתוב את האלגוריתם עצמו שפותר את הבעיה הכללית. בנוסף, יש להסביר איך הגענו אליו ואת נכונותו ויעילותו.
למשל, פתרון לשאלה זו יכול להכתב כך:
הבחנות:
1. נניח שלקחנו אוסף כלשהו של תפוחים מבין התפוחים של סבתא סמית, ושניתן ליצור איתם את כל המשקלים מ-1 עד משקל W מסוים, ויש תפוח נוסף מחוץ לאוסף שלקחנו שמשקלו Y. ביחד אתו אפשר ליצור את כל המשקלים מ-1 עד W+Y.
2. נניח שלקחנו אוסף כלשהו של תפוחים מבין התפוחים של סבתא סמית, ושהמשקל הכולל שלהם הוא W. אם כל שאר התפוחים שלא באוסף שבחרנו שוקלים יותר מ-W+1 (כלומר W+2 ומעלה), אי אפשר ליצור את המשקל W+1 על הצג.
הסבר: אי אפשר רק עם התפוחים באוסף שבחרנו ליצור משקל יותר גדול מהמשקל הכולל שלהם, כי כל המשקלים חיוביים (אז אם נשים רק חלק מהתפוחים האלו נקבל רק משקל נמוך יותר), וכל תפוח מחוץ לאוסף שוקל יותר מ-W+1 ויקפיץ את המשקל מעבר למשקל זה.
רעיון הפתרון: נמיין את התפוחים ונעבור עליהם לפי הסדר, בכל שלב נשמור את סכום התפוחים עד כה (נסמנו ב-sum). אם התפוח הבא גדול מ-sum+1 (או אם לא נשארו יותר תפוחים), לפי ההבחנה השנייה אי אפשר לייצג את sum+1 על הצג. אם נעבור על התפוחים לפי הסדר – בפעם הראשונה שבה זה יקרה נקבל את המשקל הנמוך ביותר שאי אפשר להציג.
נכונות: באינדוקציה מהבחנה 1, אם עד מקום מסוים ניתן להרכיב את כל המשקלים עד sum והתפוח הבא שוקל x, עכשיו סכום התפוחים sum+x ואפשר להרכיב את כל המשקלים עד אליו.
אלגוריתם:
- מיין את המערך apple בסדר עולה
- 0 → sum
- עבור כל i מ-1 עד n:
אם sum + 1 < apple[i]:
הדפס sum+1 וסיים
אחרת:
sum + apple[i] → sum
- הדפס sum+1 וסיים // המקרה שבו ניתן להרכיב כל משקל מ-1 עד סכום המשקלים
סיבוכיות זמן: המיון לוקח O(n log n), שאר הסריקה O(n), סה"כ O(n log n).