שאלות ופתרונות שלב ב' 2022

שאלה ראשונה - אבטיחים

לאחר שבשלב א', בעזרתכם, סבתא סמית הצליחה להוריד מהאינטרנט את התמונה של האבטיח בקצב מרשים, היא החליטה לנסות את מזלה ולגדל אבטיחים בעצמה.
היא שתלה בגינתה n אבטיחים שמסודרים בשורה, ממוספרים משמאל לימין מ-1 ל-n. אך לצערה, מגדת עתידות גילתה לה שאחד מהאבטיחים שלה פגום מבפנים, ואי אפשר לראות זאת מבחוץ!
כדי לזהות את האבטיח הפגום היא רכשה 2 מכונות מיוחדות.
כל אחת מהמכונות פועלת בצורה הבאה: מכוונים את הגלאי של המכונה לאורך מסוים ושמים אותו במקום מסוים, כך שהוא יקלוט את כל רצף האבטיחים ממקום i כלשהו (לבחירתה) עד למקום j כלשהו (לבחירתה) בשורה, ומפעילים את המכונה. כעבור שעה, כשהמכונה מסיימת לקלוט ולעבד את כל הנתונים, היא מדליקה אור אדום אם אחד מהאבטיחים בטווח של הגלאי שלה פגום, או אור ירוק אחרת. כמובן שהמכונה רב פעמית, ולאחר קבלת תוצאה עבור טווח מסוים ניתן לכוון אותה מחדש לטווח חדש ולהפעיל שוב.
2 המכונות ניתנות להפעלה במקביל ולא תלויות או מפריעות אחת לשניה.
עזרו לסבתא סמית לגלות את האבטיח הפגום מהר ככל האפשר (בכמה שפחות שעות, במקרה הגרוע), כתבו עבורה אלגוריתם שמשתמש במכונות המיוחדות לצורך כך!
האלגוריתם מקבל את מספר האבטיחים n ויכול להשתמש בפעולה use_machine(m, i, j) – שמקבלת את הטווח l1 ≤ i ≤ j ≤ n ואת מספר המכונה m (1 או 2) ומחזירה את התוצאה של המכונה - green / red כמתואר לעיל. בין כל 2 קריאות עם ערך m זהה (אותה המכונה) תעבור שעה, ניתן להניח שקריאות רצופות עם ערך m שונה יתבצעו במקביל.
הניחו כי קיים אבטיח פגום אחד בדיוק.

שימו לב שפתרון זה דורש כ-log4(n) שעות. טעות נפוצה הייתה לא לנצל את כל המידע שיכול להתקבל מהמכונות ולצמצם בכל פעם רק 2/3 מהאפשרויות, כלומר סדר גודל של log3(n) שעות, וזה לא הזמן הקצר ביותר האפשרי (אם היה מדובר בסיבוכיות של אלגוריתם אז מזניחים קבועים ולכן זו אותה סיבוכיות, אך כאן יש לנו סיפור והמשימה היא למצוא את האבטיח המקולקל בכמה שפחות שעות, אז זה חלק מנכונות הפתרון בשאלה ולא מניתוח הסיבוכיות).
הבחנות:
* בכל שעה סבתא סמית יכולה לקבל מהמכונות אחד מ-4 פלטים אפשריים שונים לכל היותר: או ש-2 המכונות מדליקות אור ירוק, או ש-2 המכונות מדליקות אור אדום, או שהמכונה הראשונה מדליקה אור ירוק והשנייה אור אדום או שהמכונה הראשונה מדליקה אור אדום והשנייה אור ירוק. אין צירופים אפשריים אחרים.
* בכל שעה נוכל לפסול את כל האבטיחים שלא מתאימים לפלט שקיבלנו מהמכונות בהתאם לאופן בו כיוונו אותן.
* כדי שסבתא סמית תוכל למצוא את האבטיח הפגום מהר ככל האפשר (במקרה הגרוע), נרצה שכל אחת מהאפשרויות תפסול לנו כמה שיותר אבטיחים / תשאיר לנו כמה שפחות. מכיוון שהאפשרויות הללו מתאימות לטווחים זרים, במקרה הגרוע בכל שעה נפסול ¾ מהאבטיחים ונשאר עם¼ (עד כדי עיגול כלפי מעלה).
רעיון האלגוריתם: בכל שלב יש לנו טווח מסוים של אבטיחים שהאבטיח הפגום נמצא ביניהם. בהתחלה כל האבטיחים יכולים להיות פגומים כי אין לנו מידע נוסף. כמו שתואר בהבחנות, בכל שעה נקבל מידע כלשהו, אחת מ-4 אפשרויות, ונרצה במקרה הגרוע לנצל מידע זה כדי להישאר עם רבע מהטווח שהיה לנו (עד כדי עיגול). כלומר, נרצה לכוון את המכונות כך שכל אחת מ-4 האפשרויות תתאים לרבע מהאבטיחים. ניתן לעשות זאת אם מחלקים את טווח האבטיחים ל-4 "רבעים" (אם המספר לא מתחלק ב-4, אז חלק מהקבוצות יהיה גדולות ב-1 מאחרות), ומכוונים את המכונה הראשונה ל-2 הרבעים הראשונים של טווח האבטיחים, ואת המכונה השנייה לרבעים השני והשלישי, כמתואר באיור הבא:

אלגוריתם:

נכונות ואופטימליות: כמתואר בהבחנות.

הצג פתרון

שאלה שניה- בבקו

בביקורה באקוואדור גאלה טעמה פרי בשם בבקו (babaco), שטעמו הוא כמו שילוב בין פפאיה, אננס ותות.

גאלה התלהבה מאוד וכשחזרה לארץ הלכה למשתלה וקנתה זרעי בבקו כדי שתוכל לגדל את הפרי בחצר ביתה בירוחם.
לצערה, היא גילתה שהאדמה אצלה לא מתאימה לגידול בבקו, ושיש להעשיר אותה בתרבית מיוחדת של חיידקים, עם מסה ששווה בדיוק n פיקוגרם.
גאלה הצליחה להשיג צלחת פטרי (צלחת שמשתמשים בה לגידול חיידקים) עם חיידק אחד בדיוק בעל מסה של 1 פיקוגרם. בכל יום, חלק מהחיידקים בצלחת של גאלה יכולים להתפצל, וגאלה יודעת לשלוט בדיוק על איזה חיידקים יתפצלו (היא יכולה עבור כל חיידק לבחור האם הוא יתפצל ביום מסוים או לא, היא גם יכולה לבחור שאף חיידק לא יתפצל). כשחיידק בעל מסה השווה ל-m מתפצל, נוצרים ממנו 2 חיידקים שמסתם שווה ל-m/2 בדיוק.
בכל לילה, אחרי שהפיצולים של היום כבר התרחשו, המסה של כל אחד מהחיידקים בצלחת של גאלה גדלה בפיקוגרם אחד.
למשל, אם ביום מסוים היו בצלחת 2 חיידקים שמסתם 3 פיקוגרם, ואחד מהם גאלה פיצלה ביום זה, אז בלילה לפני הגדילה יש 3 חיידקים בצלחת, אחד עם מסה 3 ו-2 עם מסה 1.5, והמצב משתנה ל-3 חיידקים, אחד עם מסה של 4 פיקוגרם, ו-2 עם מסה של 2.5 פיקוגרם.
גאלה רוצה בכמה שפחות ימים להגיע לצלחת שמסת החיידקים הכוללת בה שווה ל-n פיקוגרם בדיוק, על מנת שתוכל במהרה להכין את הקרקע ולגדל את פירות הבבקו האהובים עליה.
עזרו לגאלה במשימתה, וכתבו עבורה אלגוריתם, שמקבל את n (מספר שלם – המסה הכוללת בפיקוגרם של החיידקים שגלאה צריכה), ובודק האם גאלה יכולה להגיע לצלחת עם מסה של בדיוק n פיקוגרם.
אם לא – על האלגוריתם שלכם להדפיס IMPOSSIBLE. אם כן – על האלגוריתם שלכם למצוא ולהדפיס את מספר הימים הקטן ביותר שדרוש לגאלה לשם כך – נסמנו ב-d, ולאחר מכן d מספרים – מספר החיידקים שגאלה תבחר לפצל בכל אחד מהימים, לפי הסדר.
לדוגמה, אם גאלה רוצה להגיע למסה 2, היא יכולה להדפיס 1 0, כלומר יקח יום אחד להגיע למסה זו ולא צריך לפצל חיידקים כלל. אם גאלה רוצה להגיע למסה 9, היא יכולה להדפיס 3 1 0 2, כלומר יקח 3 ימים להגיע למסה זו. ביום הראשון היא תפצל את החיידק היחיד (ל-2 חיידקים במסה 0.5), ביום השני היא לא תפצל חיידקים (ויהיו לה 2 חיידקים במסה 1.5), וביום השלישי היא תפצל את 2 החיידקים (יהיו לה 4 חיידקים במסה 1.25, שיגדלו בלילה ל-2.25, סה"כ מסה של 9 פיקוגרם).

הצג פתרון

שאלה שלישית - גוג'י ברי

גברת פינק מנהלת חנות בריאות, בה היא מוכרת בין היתר פירות גוג'י בגידול עצמי. יש לה n שיחי גוג'י המסודרים בשורה, והגיע רגע הקטיף!
את הקטיף גברת פינק מבצעת באמצעות רובוט עם זרועות רבות, שתופס את השיחים, מנער אותם ואוסף את כל פירות הגוג'י בשיחים שהוא ניער. הרובוט ארוך מאוד – הוא משתרך לאורך כל שורת השיחים, המרחק בין הזרועות המנערות הוא כזה שהרובוט מנער שיחים במרחק של 2 אחד מהשני, והוא ממוקם כך שהזרוע המנערת הראשונה תופסת את השיח השמאלי ביותר (שיח מספר 1). במילים אחרות – הזרועות של הרובוט מנערות ואוספות את כל הפירות בכל השיחים שמספרם אי זוגי, ובשיחים אלו בלבד! שימו לב כי המיקום של זרועות הרובוט מקובע, ולא ניתן להזיז אותן.
מספר הפירות על כל שיח נתון לנו במערך goji (goji[i] הוא מספר הפירות על השיח ה-i, כשהשיחים ממוספרים מ-1 עד n).
כדי לאסוף יותר פירות גוג'י ולהגדיל את הרווחים, גברת פינק רכשה מכונה חד פעמית מיוחדת, שיודעת לחפור בתוך הקרקע, להוציא רצף של שיחים בשלמותו, להפוך את כל הרצף ולהחזיר לאותו המקום.
במילים אחרות, המכונה יודעת לקחת תת טווח, ממקום i למקום j לבחירתנו, ולהפוך את סדר השיחים (ואת כמות הפירות) בין המקום ה-i ל-j (ניתן גם לבחור להפוך את כל השורה).
גברת פינק יכולה לבחור טווח ולהפעיל את המכונה שהופכת את השיחים בו, או לא להפעיל אותה כלל, ואז היא מפעילה את רובוט הקטיף, שאוסף את כל הפירות בשיחים במקומות האי-זוגיים.
עזרו לגברת פינק, וכתבו עבורה אלגוריתם, שמקבל את n (מספר שלם – מספר השיחים בשורה) ואת המערך goji (מספר הפירות בכל שיח לפני פעולת המכונה ההופכת), ומדפיס את מספר הפירות הגדול ביותר שגברת פינק יכולה לאסוף (עם שימוש אחד לכל היותר במכונה ההופכת לפני הקטיף).

הבחנות:
* אין סיבה להפוך טווח באורך אי זוגי, ניקח כך את הפירות בדיוק מאותם העצים ולא נשנה כלום.
* כשהופכים טווח באורך זוגי, בטווח הזה במקום לאסוף מכל העצים במקומות האי-זוגיים הרובוט יאסוף מכל העצים במקומות הזוגיים, כי הזוגיות של המיקום תתחלף בהפיכה.
* "הרווח" שנקבל מלהפוך טווח זה סכום כל האיברים במקומות הזוגיים בתוכו, פחות סכום כל האיברים במקומות האי-זוגיים בתוכו.
* אפשר לחשוב על הפיכת טווח בגודל זוגי כחלוקה של הטווח לזוגות זרים ולהפיכת כל זוג כזה. מבחינת הרווח זה שקול, ויותר קל לבנות אלגוריתם אם מסתכלים על זה כך.
רעיון הפתרון הראשון: ניצור מערך של "הרווח" מהחלפת כל זוג סמוך (או 2 מערכים – אחד לזוגות שמתחילים במיקום זוגי והשני במיקום אי זוגי), ואז אנחנו רוצים למצוא תת-מערך רצוף שהסכום בו מקסימלי. זו בעיה ידועה, ואתם יכולים לקרוא על אלגוריתם Kadane שפותר אותה ב-O(n).
רעיון הפתרון השני: ניתן לפתור בעיה זו בתכנות דינאמי. נחשוב על 3 תתי בעיות – מה מספר הפירות הגדול ביותר שניתן לאסוף עד העץ ה-i אם לא מבצעים היפוך עם המכונה עד למקום זה, מה מספר הפירות הגדול ביותר שניתן לאסוף עד העץ ה-i אם מתחילים היפוך של טווח לפני מקום זה אבל עוד לא מסיימים אותו (כלומר הטווח שהופכים כולל את המקום ה-i), ומה מספר הפירות הגדול ביותר שניתן לאסוף עד העץ ה-i אם בוצע כבר היפוך של טווח לפני מקום זה.
ניצור 3 מערכים, אחד עבור כל בעיה, נתחיל בעץ הראשון ונפתור עבורו את 3 תתי הבעיות, ואז נעבור לעץ השני וכו', ובכל פעם נוכל להסיק את התשובה לכל תת בעיה מתתי הבעיות עבור העצים הקודמים.
רמז: בתת הבעיה השנייה, כשאנחנו כרגע בטווח שהופכים, המקומות שאוספים בהם פירות הם הזוגיים ולא האי-זוגיים, והזוגיות של המקום קובעת בכל תתי הבעיות האם הפירות על העץ הנוכחי נאספים או לא. מותר לבצע היפוך אחד לכל היותר.
נשאיר את שאר הפתרון כתרגיל 😊.

הצג פתרון

שאלה רביעית- דובדבנים

האחים רד וגולדן משחקים במשחק הדובדבנים.

במשחק יש m סלים עם מספר כלשהו של דובדבנים בכל סל.

שני השחקנים רואים כמה דובדבנים יש בכל אחד מהסלים. בכל תור השחקן שזהו תורו מבצע מהלך לפי התיאור בכל סעיף. השחקן שבהגיע תורו אין לו מהלך חוקי אפשרי, מפסיד במשחק. רד מתחיל במשחק.

בהנחה שרד וגולדן הם שחקנים שלא עושים טעויות ומשחקים תמיד את האסטרטגיה הטובה ביותר, עבור כל אחד מהסעיפים הבאים, כתבו אלגוריתם שמקבל את מספר הסלים (מספר שלם m) ואת מספר הדובדבנים בכל סל (מערך cherries בגודל m), ויקבע האם רד (השחקן שהתחיל ראשון) ינצח במשחק:

א. m=2, ונתון בנוסף מספר שלם אי-שלילי k (הוא נתון לאלגוריתם שלכם כמובן). בכל תור השחקן שזהו תורו יכול לבצע את אחד מהמהלכים הבאים:

1. לקחת כמות חיובית כלשהי (גדולה מאפס) של דובדבנים מהערימה הימנית ולאכול אותם (נעלמים מהמשחק). 2. לקחת כמות חיובית כלשהי (גדולה מאפס) של דובדבנים מהערימה השמאלית ולכל היותר k דובדבים (אפשר גם אפס) מהערימה הימנית, ולאכול את כל הדובדבנים שנלקחו.

ב. m=3. בכל תור השחקן שזהו תורו בוחר ערימת דובדבנים אחת, ולוקח ממנה כמות חיובית (גדולה מאפס) של דובדבנים. אם לקח דובדבנים מהערימה שאיננה הימנית ביותר, הוא יכול להכניס חלק מהדובדבנים שלקח אל הערימה הימנית ביותר (מותר גם לא להכניס בכלל או להכניס את כולם). אם נשארו לו דובדבנים שהוא לקח ולא העביר לערימה הימנית ביותר (או שהוא לקח מלכתחילה מהערימה הימנית ביותר) – הוא אוכל אותם והם נעלמים מהמשחק.

ג. m≥2. נסמן l=⌊m/2⌋ (m חלקי 2, מעוגל כלפי מטה). בכל תור השחקן שזהו תורו יכול לבצע את אחד מהמהלכים הבאים:

1. לקחת כמות חיובית (גדולה מאפס) כלשהי של דובדבנים מהערימה הימנית ביותר ולאכול אותם.

2. לבחור z ערימות (1≤l≥z) שאינן הימנית ביותר ולקחת מכל אחת מהן כמות חיובית כלשהי של דובדבנים. שימו לב כי חייבים לבחור לפחות ערימה אחת (כלומר לקחת לפחות דובדבן אחד בסה"כ). כעת השחקן יכול להכניס חלק מהדובדבנים שלקח אל הערימה הימנית ביותר (מותר גם לא להכניס בכלל או להכניס את כולם). אם נשארו לו דובדבנים שהוא לקח ולא העביר לערימה הימנית ביותר (או שהוא לקח מלכתחילה מהערימה הימנית ביותר) – הוא אוכל אותם והם נעלמים מהמשחק.

שאלה זו עוסקת בענף של מתמטיקה ומדעי המחשב שנקרא תורת המשחקים הקומבינטורית, שמהווה מקור להרבה חידות מעניינות. בשאלות מסוג זה מטרתנו היא לנתח את המשחקים הנתונים (בפרט, טעויות נפוצות הן לכתוב אלגוריתם שמריץ את המשחק ע"י כך שהוא קולט את המהלכים של השחקנים ומבצע אותם, או לנסות "לנחש" מהלכים טובים וכך לקבוע את תוצאת המשחק).

אנו מחלקים את המשחק למצבים. המצב "מקודד" את כל המידע שיש כרגע במשחק. במקרה שלנו, המצב הוא מספר הדובדבנים שנשארו בכל סל. את המצבים אפשר לסווג לשני סוגים: מצבים מנצחים ומצבים מפסידים. מצב מנצח הוא מצב שבו השחקן שתורו כעת יכול לכפות ניצחון ע"י משחק אופטימלי. כלומר, אם תורנו לשחק והמצב כעת הוא מפסיד, היריב ינצח אותנו אם ישחק אופטימלית, לא משנה מה נעשה. במילים אחרות, אנו רוצים להתחיל כל תור שלנו במצב מנצח ולסיים אותו במצב מפסיד (כדי שהיריב יקבל לידיו מצב מפסיד).

שימו לב: אם התחלנו במצב מנצח, אנו עדיין צריכים לשחק אופטימלית כדי להבטיח ניצחון. אם נעשה טעות היריב עשוי לנצח אותנו.

השאלה למעשה שקולה למציאת תנאי הכרחי ומספיק עבור מצבים מנצחים/מפסידים. בהינתן תנאי כזה, נוכל לבדוק את הלוח הנוכחי ולראות איזה במצב הוא. אם המצב מנצח, רד ינצח במשחק. אם הוא מפסיד, גולדן ינצח.

כיצד נמצא את המצבים המנצחים/המפסידים? ראשית, אנו יודעים כי המצב הסופי (0 דובדבנים בכל הסלים) הוא מפסיד (זה מופיע בחוקי המשחק). כעת, כל מצב שמוביל למצב מפסיד (כלומר, אפשר במהלך אחד להגיע ממנו למצב מפסיד), הוא מצב מנצח. מדוע? השחקן ישחק את המהלך שמעביר למצב מפסיד כזה, וכך ינצח. בדומה, כל מצב שמוביל רק למצבים מנצחים, הוא מפסיד. לפיכך ניתן לבחון מקרים קטנים ולנסות למצוא את התנאי.

לדוגמה, בסעיף א', משום שהמצב (0, 0) מפסיד, אנו יודעים כי כל מצב מהצורה (x, y) כאשר x ≥ 1, 0≤y≤k הוא מנצח, וכן כל מצב מהצורה (o, x) כאשר x ≥ 1 הוא מנצח (ממצבים אלו ניתן להגיע במהלך אחד ל-(0, 0). כעת, המצב x = 1, y = k+1 מפסיד, כי ניתן להגיע ממנו רק למצבים מנצחים. לפיכך גם x=1, y ≥ k+2 מנצח (ניתן להגיע ממנו למצב הקודם) וכו'. אנו עשויים לשים לב כי המצבים המפסידים היחידים הם:

(0,0);(1,k+1);(2,2(k+1));(3,3(k+1));…

זה מוביל אותנו לטענה: המצב מפסיד אם ורק אם y = (k + 1)*x. באופן שקול, מצב הוא מנצח אם ורק אם y≠(k+1)*x.

שימו לב שדרושה מעט יצירתיות כדי לנסח טענה כזו, אך ברגע שמוצאים את התנאי הנכון האלגוריתם פשוט מאוד:

חשוב להוכיח את הטענה שלכם (בראש ובראשונה כדי שתדעו שהיא בוודאות נכונה, אך גם כדי לקבל את מלוא הניקוד). כיצד מוכיחים טענה כזו? הדרך המתמטית משתמשת באינדוקציה, אך לשם פשטות נציין כי תחת תנאים מסוימים מספיק (והכרחי) להוכיח את שלושת הדברים הבאים:

כדי לוודא שהסברתם כראוי מומלץ להפריד את ההוכחה לשלושה חלקים באופן זה.

סעיף ב': התשובה היא שמצב (x, y, z) הוא מפסיד אם ורק אם z = x + y. אנו ממליצים לנסות ולהוכיח זאת במדויק באופן שתואר לעיל, זהו תרגיל טוב כדי לוודא שהבנתם את העיקרון (ההוכחה מורכבת יותר מאשר סעיף א'. בפרט וודאו כי אתם יודעים כיצד לעבור ממצב מנצח למפסיד).

סעיף ג': בשלב זה נשאיר את הפתרון כתרגיל לקוראים 😊.

רמז: נסו להכליל את הפתרון של סעיף ב'.