תוכן:
- מה זו בעיית אולימפיאדה?
- איך מתכוננים לשלב א’?
- איך מתכוננים לשלב ב’ – התחרות הארצית?
- שלב ג’ והמשך האימונים
מה זו בעיית אולימפיאדה?
נסו לפתור את הבעיה הבאה:
אמיר ומיכל משחקים במשחק. על לוח המשחק מונחים 1,000 מטבעות בשורה. לכל מטבע בשורה יש ערך שהוא מספר חיובי והשחקנים יודעים בתחילת המשחק את ערכיהם של כל המטבעות.
המשחק מתנהל בתורות, לסירוגין. בכל תור, השחקן שמשחק בוחר מטבע מאחד משני קצוות השורה ולוקח אותו לקופה שלו. לאחר 1,000 תורות נגמרים המטבעות בשורה. בשלב זה, סופרים את סכום ערכי המטבעות שבקופה של כל אחד מהשחקנים. השחקן שצבר סכום גדול יותר, מנצח במשחק. במקרה של שוויון בסכומים, המשחק מוכרז כתיקו.
אמיר משחק ראשון. הוא ממש לא רוצה להפסיד. לא אכפת לו אם המשחק יסתיים בתיקו או בניצחון שלו. מצאו אסטרטגיה עבור אמיר שתבטיח שהוא לא יפסיד במשחק.
כמובן שאמיר יכול לחשב מראש את עץ המהלכים המלא של המשחק: איך מיכל יכולה להגיב לכל מהלך שלו, ואז איך הוא יגיב לכל מהלך שלה וכו’. הבעיה בפתרון כזה היא שהעץ הזה עצום: מספר המשחקים השונים שאמיר ומיכל יכולים לשחק הוא \(2^{999}\) וגם למחשב החזק ביותר בעולם, החישוב הזה ייקח טריליוני שנים.
לכן, אנו מעוניינים בפתרון יעיל לבעיה – כזה שדורש מאמיר לבצע מעט פעולות כדי לחשב לעצמו אסטרטגיה. הפתרון שנציג פה לבעיה דורש מעבר אחד בלבד על סדרת המטבעות.
הבעיה שהצגנו כאן היא דוגמה לבעיה אלגוריתמית. באולימפיאדה במדעי המחשב אנו פותרים בעיות אלגוריתמיות, ובשלבים המאוחרים אנו גם מתכנתים את הפתרונות.
מדריך זה נועד לעזור לכם להתכונן לשלבים השונים של האולימפיאדה במדעי המחשב. קראו על שלבי האולימפיאדה לפני שאתם ממשיכים.
איך מתכוננים לשלב א’?
שלב א’ של האולימפיאדה בנוי כך שניתן לגשת אליו גם ללא שום רקע במדעי המחשב או בתכנות. כדאי להתכונן אליו על ידי פתרון בעיות שלב א’ משנים קודמות. לאחר שפתרתם מספר שאלות שלב א’, המשיכו לצעדים המתוארים תחת “איך מתכוננים לשלב ב’ – התחרות הארצית?”.
טיפים לשלב א’:
- נסו להמציא אלגוריתם פתרון יעיל. בדקו את האלגוריתם שלכם היטב וודאו שהוא באמת מחזיר תמיד את התשובה הנכונה. רק לאחר שווידאתם זאת, השתמשו באלגוריתם שלכם כדי לחשב את התשובה הנכונה עבור הקלט שמופיע בשאלה.
- כדי לעבור לשלב ב’, בדרך כלל מספיק לפתור 3 שאלות (מתוך 5), ולפעמים אפילו פחות.
איך מתכוננים לשלב ב’ – התחרות הארצית?
כדאי להגיע מוכנים ככל שתוכלו לשלב ב’ של האולימפיאדה. ההתכוננות מורכבת משלושה צעדים.
צעד ראשון: עקרונות התכנות
לימדו את העקרונות הבסיסיים של תכנות:
- משתנים
- לולאות
- מערכים
- פונקציות (שיטות)
- רקורסיה
- חיפוש בינארי
- מיון
- סיבוכיות
בשלב ב’ “מתכנתים במחברת”. אין צורך במומחיות בשפת תכנות מסוימת. ישנם אתרי אינטרנט שמלמדים תכנות וניתן להיעזר בהם.
צעד שני: היכרות עם בעיות אולימפיאדה
הבעיות הבאות מדגימות רעיונות יסודיים שמופיעים בבעיות אולימפיאדה רבות. הקדישו זמן על מנת לנסות לפתור כל בעיה. לאחר מכן קראו את הפתרון. בכל בעיה, נסו למצוא אלגוריתם פתרון יעיל ככל האפשר מבחינת סיבוכיות זמן.
תנינים – שלב ב’ 2004:
יש \(N\) תנינים. לכל תנין יש שנת לידה ושנת פטירה. כתבו אלגוריתם שמקבל כקלט \(N\) זוגות של מספרים שמתארים את שנת הלידה ושנת הפטירה של כל תנין. האלגוריתם מחשב ומחזיר את השנה שבה חיו הכי הרבה תנינים בו זמנית. אם יש כמה שנים כאלה, ניתן להחזיר אחת מהן.
משחק הפחתת מספר:
שני שחקנים משחקים במשחק. בתחילת המשחק, יש בקופה \( N \) גולות. השחקנים משחקים לסירוגין. כל שחקן, בתורו, לוקח מהקופה בין \( 1 \) ל־\( 10 \) גולות, לבחירתו. המנצח הוא השחקן שלוקח את הגולה האחרונה. כתבו אלגוריתם שמשחק את המשחק בתור המחשב, נגד מתחרה אנושי. בתחילת המשחק מקבל האלגוריתם כקלט את \( N \) ומחליט אם הוא רוצה לשחק ראשון או שני. לאחר מכן, בכל תור, האלגוריתם מקבל כקלט את המהלך של המתחרה שלו ומחשב ומחזיר את המהלך שלו. האלגוריתם שלכם חייב לנצח תמיד.
טיול בעולם – שלב א’ 2013-2014:
יש בעולם \( N \) ערים הממוספרות \( 1\ldots N \). בין חלק מזוגות הערים מחברת טיסה ישירה. ערן מתכנן טיול בעולם. מסלול טיול טוב הוא מסלול שמקיים את התנאים הבאים:
- המסלול חייב להתחיל בעיר מספר \( 1 \). הוא יכול להסתיים בכל עיר.
- בכל צעד, ערן יכול לעבור בין שתי ערים רק אם קיימת ביניהן טיסה ישירה.
- בכל צעד, ערן חייב לעבור מהעיר שהוא נמצא בה לעיר שמספרה גדול יותר.
- במסלול לפחות שתי ערים שונות.
כתבו אלגוריתם שמקבל כקלט את \( N \) ולאחר מכן, מקבל רשימה של כל זוגות הערים שיש ביניהן טיסה ישירה. על האלגוריתם לחשב ולהחזיר כפלט את מספר מסלולי הטיול הטובים השונים האפשריים עבור ערן.
ספירת תת מערכים – שלב א’ 2014-2015:
נתון מערך \(A[1\ldots N]\) של \(N\) מספרים שלמים. כתבו אלגוריתם שמחשב כמה תת־מערכים רצופים \(A[i]\ldots A[j]\) קיימים כך שסכומם \(A[i]+\ldots+A[j]\) מתחלק ב־\(3\).
מסלול זול ביותר – שלב ב’ 2012:
נתון מערך \(A\) של \(N\) מספרים שלמים חיוביים המציינים תעריפי ביקור בתחנות לאורך מסלול קווי. ג’רי נמצא בתחנה הראשונה ומעוניין להגיע לתחנה האחרונה, במסלול כמה שיותר זול. כשג’רי נמצא בתחנה \(i\) יש לו שתי אפשרויות: לעבור לתחנה \(i+1\) או לדלג עליה ישירות אל התחנה \(i+2\). אם \(i=N-1\) אז ג’רי חייב לעבור אל תחנה \(N\) ולא יכול לדלג.
ג’רי צריך לשלם תעריף ביקור בכל תחנה שהוא מבקר בה. כתבו אלגוריתם שמקבל את תעריפי התחנות ומחשב מהו התשלום הכולל המינימלי שג’רי יכול לשלם כדי להגיע מהתחנה הראשונה לאחרונה.
משחק כדורסל – שלב א’ 2012-2013:
משחק כדורסל בין שתי קבוצות התחיל בתוצאה \(0:0\) והסתיים בתוצאה \(N:M\) נקודות. כתבו אלגוריתם שמקבל את שני המספרים \(N,M\) ומחזיר בכמה דרכים אפשר להגיע לתוצאה \(N:M\). קבוצה יכולה לקלוע בקליעה בודדת (סל בודד) נקודה אחת, או שתי נקודות או שלוש נקודות.
לדוגמה, יש \(4\) דרכים להגיע לתוצאה \(0:3\) – לקלוע סל של \(3\), או סל של \(1\) ואז סל של \(2\), או סל של \(2\) ואז סל של \(1\), או שלושה סלים של \(1\).
צעד שלישי: בעיות נוספות
לאחר שקראתם והבנתם את הפתרונות בצעד השני, היכנסו לעמוד של שלב ב’ כדי לראות את השאלות מהתחרויות הארציות של השנים הקודמות. נסו לפתור בעצמכם, ובכל מקרה קראו את הפתרונות. כדאי לנסות גם לתכנת חלק מהפתרונות.
טיפים לשלב ב’
- כדי לעבור לשלב ג’ (האימון המתקדם), בדרך כלל מספיק לפתור 2.5 שאלות (מתוך 4), ולפעמים אפילו פחות.
- השקיעו זמן בניסוח רעיון האלגוריתם. עליכם להסביר, בקצרה אך בבהירות, מדוע האלגוריתם שלכם באמת עושה את מה שהוא נדרש לעשות.
- לפני שאתם כותבים את אלגוריתם הפתרון ודאו שהוא באמת עובד, כלומר שהוא מחזיר תשובה נכונה עבור כל קלט אפשרי לבעיה. אלגוריתמים שטועים על חלק מהקלטים לא יזכו בנקודות.
- בכתיבת תוכנית הפתרון שלכם, ניתן לקצר כשמתארים מימוש של פעולות סטנדרטיות, כמו קריאת קלט או מציאת מינימום במערך. יש להקפיד שהגרעין של האלגוריתם יהיה ברור.
שלב ג’ והמשך האימונים
שלב ג’ (האימון המתקדם) הוא סדרה של מפגשי תחרות ולימוד. ההתכוננות אליו מורכבת משני צעדים נוספים, מעבר לצעדי ההתכוננות לשלב ב’.
צעד רביעי: תחרויות ואתגרים באינטרנט
ישנם מספר אתרי אינטרנט שמאפשרים לפתור בעיות אולימפיאדה ברמות שונות, לתכנת את הפתרון ולקבל עליו משוב מידי ממערכת בדיקה אוטומטית שנמצאת על האתר. מומלץ להשתמש באתרים כאלה כדי לתרגל פתרון בעיות, הן בהיבט האלגוריתמי והן בהיבט התכנותי. שני אתרים מומלצים במיוחד הם Codeforces ו־CodeChef. אתרים אלה גם עורכים תחרויות אונליין בהן תוכלו להשתתף.
בנוסף, בעמוד החדשות באתר זה מופיעים לעתים עדכונים בנוגע לתחרויות באינטרנט. מומלץ לעקוב.
צעד חמישי: למידה
במקביל לתרגול פתרון בעיות, ישנם מספר נושאים תאורטיים באלגוריתמים ובמתמטיקה שכדאי ללמוד (ראו מקורות מידע). הנה שלושה נושאים חשובים שכדאי להתחיל מהם:
- תכנות דינמי
- מושגים בסיסיים בתורת הגרפים
- אלגוריתמים בסיסיים בגרפים – DFS, BFS ואלגוריתמי מסלולים קצרים
ומה עכשיו?
המשיכו להתאמן, ואולי תגיעו לאולימפיאדה הבינלאומית. גם אם לא תגיעו לשם, אין ספק שתיהנו ותלמדו המון בדרך. בהצלחה!
