שאלות ופתרונות שלב ב' 2023-2024

שאלה ראשונה - אפרסקים שטוחים

גברת פינק אוהבת אפרסקים שטוחים.

אפרסק שטוח, הקרוי גם אפרסק פיתה, הוא זן של אפרסק בעל צורה פחוסה.

אפרסק שטוח ניתן להניח על שולחן ב-2 אופנים:

עם הצד שהיה מחובר לעץ כלפי מעלה.
עם הצד שלא היה מחובר לעץ כלפי מעלה.

גברת פינק סידרה בשורה n אפרסקים שטוחים, והאופן שבו היא סידרה אותם נתון לנו במערך A, שהאיבר ה-i בו הוא 1 אם האפרסק ה-i מונח באופן הראשון, או 2 אם הוא מונח באופן השני.

גברת פינק יכולה בפעולה אחת להפוך את כל האפרסקים בטווח רציף לבחירתה. במילים אחרות, בכל פעולה היא בוחרת 2 ערכים, s ו-e, המקיימים s ≤ e, ולכל s ≤ i ≤ e היא הופכת את האפרסק ה-i (כלומר מבצעת A[i] = 3 - A[i]).

גברת פינק רוצה שכל האפרסקים יהיו מונחים באופן הראשון – עם החלק שחיבר אותם לעץ כלפי מעלה (כלומר שכל הערכים ב-A יהפכו להיות 1).

היא רוצה להשתמש בכמה שפחות פעולות לצורך כך.

למשל, היא יכולה עבור השורה הבאה להשתמש ב-2 פעולות:

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

ב. בסעיף זה, גברת פינק יכולה להפוך רק אפרסק בודד, או רישה של השורה – כלומר טווח רציף שכולל גם את האפרסק הראשון (באינדקס 0). במילים אחרות, הטווחים המותרים לפעולות מקיימים או s = e, או s = 0. עזרו לגברת פינק וכתבו עבורה אלגוריתם, שמקבל את n ואת A, ומדפיס את מספר הפעולות (החוקיות בסעיף זה) הקטן ביותר שגברת פינק זקוקה לו על מנת שכל האפרסקים יהיו מונחים עם הצד שהיה מחובר לעץ כלפי מעלה.

הערה: בשאלה זו יינתן בונוס של 10% עבור סיבוכיות זיכרון אופטימלית.

הצג פתרון

פתרון לסעיף א':

תובנות:

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

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

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

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

אלגוריתם:

סיבוכיות האלגוריתם היא O(n) זמן ו-O(1) זכרון.

פתרון לסעיף ב':

לסעיף זה קיימים מספר פתרונות אפשריים.

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

תובנות:

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

מתובנה 3 נובע פתרון בתכנות דינאמי: נשמור לכל רישה את מספר הפעולות הקטן ביותר הדרוש על מנת להפוך את כל הרישה ל-1, ועל מנת להפוך את כל הרישה ל-2, ובכל פעם נעדכן את 2 המשתנים האלו.

אם האפרסק הנוכחי הוא 1, נסתכל על 3 הפעולות האפשריות מתובנה 3:

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

(המקרה שבו האפרסק הנוכחי הוא 2 מקביל, כמו שניתן לראות באלגוריתם)

אלגוריתם:

סיבוכיות האלגוריתם גם כאן היא O(n) זמן ו-O(1) זכרון.

פתרונות אלטרנטיביים (וטעות נפוצה):

ניתן להוכיח שאם סורקים את האפרסקים לפי הסדר, בכל פעם כשנתקלים באפרסק בודד ששונה מהאפרסק הקודם וזה שאחריו, כדאי להפוך אותו, ואם האפרסק זהה לזה שלפניו אבל שונה מזה שאחריו, כדאי להפוך את הרישה שמסתיימת בו. גם זה נובע מעניין החילופים / זוגות סמוכים שונים שציינו בסעיף א', אבל ההוכחה כאן תהיה מורכבת יותר. טעות נפוצה מאוד הייתה לחשוב שמספיק רק להפוך אפרסקים בודדים הפוכים (2) שמוקפים באפרסקים שמונחים נכון (1) ואז להפוך את הרישות. זהו פתרון שגוי - למשל עבור המערך A = {2, 2, 1, 2, 2} פתרון זה יניב 3 היפוכי רישות, אך אופטימלי להפוך קודם את האפרסק הנכון שבאמצע, ואז את כל האפרסקים בפעולה אחת (הרישה שהיא כל המערך), וזה יהיה 2 פעולות בלבד.

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

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

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

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

פרי הבקורי הוא הפרי האהוב על רד. הוא כל כך אוהב את הפרי, עד שהוא טס עד לאמזונס במיוחד כדי להביא אותו.

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

במשחק 2 סלסלות, ששני השחקנים רואים בדיוק מה יש בהן בכל זמן נתון.

בסלסלה הראשונה שמונחת ליד רד יש n ערמות לא ריקות של בקורי.

מספר הפירות בכל אחת מהערמות בסלסלה זו נתון במערך B_red (שבאורך n), כאשר B_red[i] הוא מספר הפירות בערמה ה-i בסלסלה שמונחת ליד רד בתחילת המשחק.

בסלסלה השנייה שמונחת ליד גולדן יש m ערמות לא ריקות של בקורי.

מספר הפירות בכל אחת מהערמות בסלסלה זו נתון במערך B_golden (שבאורך m), כאשר [j]B_golden הוא מספר הפירות בערמה ה-j בסלסלה שמונחת ליד גולדן בתחילת המשחק.

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

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

השחקן שבתורו לא יכול לעשות מהלך חוקי מפסיד במשחק.

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

לפני כל תור של רד (כולל התור הראשון), רד יכול לבחור להחליף בין הסלסלה שלידו לבין הסלסלה שליד גולדן. הוא יכול לפני כל תור שלו באופן בלתי תלוי בתורות האחרים להחליט האם להחליף בין הסלסלות או לא.

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

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

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

הצג פתרון

תובנות:

אם סך הפירות באחת הסלסלות שונה מסך הפירות בסלסלה השנייה – רד ינצח. אסטרטגיית הניצחון שלו תהיה בתור הראשון לדאוג שהסלסלה שלידו תהיו עם יותר פירות בסך הכל (אם כך התחיל – מצוין, אחרת הוא יחליף בין הסלסלות), ובכל תור לאכול בדיוק בקורי 1. מכיוון שגם גולדן בכל תור חייב לאכול לפחות בקורי 1, לגולדן יסתיימו הבקורי קודם לכן ולכן הוא הראשון שבתורו לא יהיה לו מהלך חוקי.
אם הסלסלות זהות לחלוטין מבחינת כמות הפירות והפיזור שלהן לערימות – גולדן ינצח. אסטרטגיית הניצחון שלו תהיה בכל תור לעשות בדיוק את מה שרד עשה כמו תוכי, כלומר לקחת מהערימה המקבילה של רד את אותה כמות הבקורי שרד לקח. כל עוד רד עשה מהלך חוקי, גם לגולדן יש כזה (המהלך המקביל), ויכולת החלפת הסלסלות של רד לא עוזרת לו – כי תמיד לפני תורו של רד 2 הסלסלות יהיו זהות לחלוטין. כך שהשחקן הראשון שלא יהיה לו מהלך חוקי יהיה רד.
בשאר המקרים – כלומר אם לרד ולגולדן יש את אותה כמות הפירות הכוללת – אבל הפיזור בין הסלסלות שונה, רד ינצח. האסטרטגיה שלו תהיה אם מסתכלים על כל סלסלה כרשימה של מספרי הפירות בכל ערימה בה (כמו המערכים הנתונים) וממיינים בסדר יורד – לקחת בתור הראשון את הסלסלה הגדולה יותר לקסיקוגרפית (שבה הערימה הכי גדולה שלא קיימת לה ערימה מתאימה בסלסלה השניה גדולה יותר), ובכל תור לקחת את הערימה הכי גדולה שנשארה בסלסלה שלו במלואה, כל עוד גולדן לקח את אותה הערימה. בשלב כלשהו, מכיוון שהסלסלות לא זהות לחלוטין, גולדן לא יוכל לחקות את המהלך של רד. בפרט – גולדן יאלץ לאכול בתור זה פחות בקורי – כי מהגדרת האסטרטגיה של רד בשלב זה לגולדן כל הערימות יהיו קטנות מהערימה שרד אכל. לכן לאחר המהלך של גולדן מספר הפירות ב-2 הסלסלות לא יהיה שווה, ויהיה תורו של רד, והוא יעבור לשחק לפי האסטרטגיה של המקרה הראשון. לדוגמה, אם B_red = {1, 4, 6, 6, 7, 9, 14} ו-B_golden = {1, 4, 5, 7, 7, 9, 14} (כמות פירות זהה), רד יחליף את הסלסלות (כי של גודלן גדולה לקסיקוגרפית), ויקח את כל הבקורי בערימה של ה-14. אם גולדן יעשה מהלך אחר – כמות הפירות לא תהיה זהה ונעבור למקרה 1. אחרת, רד יקח את הערימה של 9. שוב, אם גולדן עושה מהלך זהה נעבור למקרה 1, אחרת רד יקח את הערימה עם ה-7. כעת שוב אם גולדן יעשה מהלך אחר נעבור למקרה 1, אחרת רד יקח את הערימה השניה של ה-7 וגולדן לא יוכל להשוות את כמות הפירות, שכן נשארו לו הערימות 1, 4, 6, 6, ולאחר תורו בוודאות נעבור למקרה 1.

האלגוריתם במקרה זה יהיה מאוד פשוט.

אלגוריתם:

אם n ≠ m, הדפס "רד" וסיים את הריצה

מיין את המערכים B_red, B_golden
לכל i מ-0 עד n-1:
- אם B_red[i] ≠ B_golden[i] הדפס "רד" וסיים את הריצה
הדפס "גולדן"

סיבוכיות זמן: O(n log n) (אפשר גם ב-O(n) עם hash table למי שמכיר)

אלטרנטיבות:

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

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

למשל אם B_red = {1, 2, 3, 4, 6} ו-B_golden = {1, 4, 5, 6}, רד יכול לקחת לפי האסטרטגיה השגויה את הערימה של ה-2, ואז גולדן יקח 2 בקורי מהערימה של ה-5, יגיע לסלסלה זהה וינצח על ידי חיקוי המהלכים של רד מכאן ואילך.

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

שאלה שלישית - גפן הבר

סבתא סמית מנסה לפתח זנים שונים של גפן הבר,

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

ושיחים נקביים נפרדים בכל זן, כשהשיח הנקבי מניב פרי, והשיח הזכרי

מפרה את השיח הנקבי באמצעות הרוח שמגיעה מכיוון הים.

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

סבתא סמית שתלה בשורה אחת בניצב לקו החוף n שיחי גפן מ-m צבעים,

במיקומים שונים.

האופן בו היא שתלה את השיחים נתון לכם ב-3 מערכים:

המערך C_loc מכיל את מיקומי כל השיחים,
כאשר C_loc[i] הוא המרחק של השיח ה-i מהים,
כשהשיחים ממויינים בסדר עולה (כלומר השיח ה-i + 1 במרחק
גדול או שווה למרחק של השיח ה-i מהים).
המערך C_color מכיל את צבעי השיחים,
כאשר C_color[i] מכיל את צבע הזן של השיח ה-i.
המערך C_sex מכיל את המין של כל שיח, כאשר C_sex[i] = 1 אם השיח ה-i הוא שיח זכרי, ו-2 אם הוא שיח נקבי.

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

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

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

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

לדוגמה, אם C_loc={1,2,3,4,6,9,10,12,13,14},C_color={1,2,1,3,1,1,3,1,2,1} ו-C_sex={1,1,1,1,1,2,2,2,2,2}, נחבר את 2 השיחים היחידים מזן 3 (ממיקום 4 עד 10 – כלומר מסדרון באורך 6, כתום בהיר באיור), את השיח מזן 1 במיקום 3 לשיח במיקום 9 (מסדרון באורך 6 גם כן, כחול באיור), את 2 השיחים היחידים מזן 2 (אורך 11 – ממיקום 2 עד 13, ירוק כהה באיור), את השיח מזן 1 במיקום 1 לשיח במיקום 12 (אורך 11 גם כן), ואת 2 השיחים האחרונים מזן 1 (מיקומים 6 ו-14 – מרחק 8), ונקבל את אורכי המסדרונות 6, 6, 8, 11, 11 – כלומר ההפרש בין המסדרון הקצר ביותר (6) למסדרון הארוך ביותר (11) הוא 5, שזה גם ההפרש הכי קטן שאפשר לקבל בדוגמה זו.

הצג פתרון

תובנות:

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

הוכחה:

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

תחילה המסדרונות היו באורכים x2 ו-x1 + x2 + x3, וכעת הם באורכים x1 + x2 ו-x2 + x3. נסמן את אורך המסדרון הקצר ביותר מבין כל המסדרונות בפתרון האופטימלי ב-min ואת אורך המסדרון הארוך ביותר מבין כל המסדרונות בפתרון האופטימלי ב-max.
לפי ההגדרה מתקיים x2 ≥ min, ולכן כמובן גם x1 + x2 ≥ min וגם x2 + x3 ≥ min.
לפי ההגדרה מתקיים x1 + x2 + x3 ≤ max , ולכן גם x1 + x2 ≤ max וגם x2 + x3 ≤ max.
לכן גם לאחר ההצלבה בהכרח לא הגדלנו את max ולא הקטנו את min, ולכן גם לא הגדלנו את max-min.
ראשית, האלגוריתם לא מוביל לתרחיש ב-1, כי התרחיש הוא שקיימים שיחים במיקומים a < b < c < d כך שהמיקום a (זכר) מזווג למיקום d (נקבה) והמיקום b (זכר) למיקום c (נקבה), וזה אומר שבעת הזיווג של b (ולכן גם בעת הזיווג של a קודם לכן) השיח הנקבי מאותו הזן ב-c היה פנוי, וש-a מזווג לשיח נקבי רחוק יותר (d) ולא לקרוב ביותר הפנוי כמו באלגוריתם.
שנית, אם אלגוריתם אחר מקבל החלטה שאינה שקולה, זה אומר שיש עץ זכרי a שזווג לעץ נקבי d שאינו הקרוב ביותר אליו הפנוי מאותו הזן, כלומר קיים גם עץ נקבי c קרוב יותר שיזווג לעץ זכרי רחוק יותר מ-a מאוחר יותר (אם העץ באותו המקום זו החלטה שקולה), מה שיצור מסדרון שמוכל במסדרון אחר. לכן הזיווג שאנו מוצאים הוא גם היחיד שתרחיש זה לא מתקיים בו.
אם קיים זיווג כלשהו גם הזיווג שהאלגוריתם שלנו ימצא הוא תקין, וכל זכר יזווג לנקבה משמאלו (אחרת קיימת רישה עם יותר שיחים נקביים מאשר זכריים, ולא קיים זיווג חוקי כלל במצב זה).

אלגוריתם:

סיבוכיות זמן O(n+m)

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

לאדון חרמון יש n דובדבנים בגדלים שונים.
הקוטר של כל דובדבן במיקרומטרים הוא מספר שלם, בין 10,000 לבין 30,000, והוא נתון במערך D, כאשר D[i] הוא הקוטר במיקרומטרים של הדובדבן ה-i.
אדון חרמון רוצה לסדר את הדובדבנים שלו במעגל בסדר כלשהו, כך שלכל 2 דובדבנים שכנים, הערך המוחלט של ההפרש בין הקטרים יהיה בדיוק מיקרומטר אחד (כלומר ההפרש בין הקטרים יהיה 1 או 1-), אך הוא לא בטוח שזה אפשרי.
עזרו לאדון חרמון, וכתבו עבורו אלגוריתם, שבהינתן n (מספר הדובדבנים), והמערך D (גדלי הדובדבנים), יקבע האם אדון חרמון יכול לסדר את כל הדובדבנים שלו במעגל כך שהערך המוחלט של ההפרש בין כל 2 דובדבנים שכנים יהיה 1 בדיוק.

דוגמה, אם D={22022,22022,22023,22023,22023,22024} התשובה תהיה חיובית:

אך אם D={22022,22022,22023,22023,22023,22025}, התשובה תהיה שלילית.

הצג פתרון

תובנות:

נניח שהתשובה חיובית. אז מתקיים:

נסתכל על כל הזוגות הסמוכים. כל זוג (לא סדור) חייב להופיע מספר זוגי של פעמים (כי על כל פעם שעברנו מ-x ל-x+1, נצטרך מתישהו לחזור ל-x מ-x+1, ולכן (x, x+1) יופיע מספר זוגי של פעמים).
נסמן את המספר הקטן ביותר ב-A ואת המספר הגדול ביותר ב-B. לכל A ≤ x < B, הזוג (x, x+1) יופיע מספר חיובי של פעמים (כי חייבת להיות דרך להגיע מ-A ל-B באמצעות מספרים עוקבים).
נסמן ב-H[x] את מספר המופעים של x במערך D. נסמן ב-E[x] את מספר המופעים של הזוג (x, x+1) בסידור. מתקיים בהכרח
E[x] = 2H[x] – E[x – 1] לכל A ≤ x ≤ B (כש-E[A-1]=0 כמובן), משום שכל דובדבן מופיע ב-2 זוגות (יש לו 2 שכנים), וכמובן כל אחד מהזוגות האלו עבור x הוא או (x, x+1) או (x, x-1), לכן מתקיים E[x]+E[x-1]=2H[x].

שילוב של 3 התובנות הראשונות:
נגדיר E[A-1] = 0, E[A ≤ x ≤ B] = 2H[x] – E[x – 1]. קיים סידור חוקי אם ורק אם לכל A ≤ x < B הערך E[x] זוגי וחיובי, וגם E[B]=0.

נכונות:

כבר הסברנו למה אם קיים סידור חוקי בהכרח התנאי הזה יתקיים.

נותר להסביר למה קיום התנאי מבטיח שקיימת בניה חוקית.
נבנה את המערך E.

נשים תחילה דובדבן בגודל A ומ-2 צדדיו דובדבנים בגודל A+1. משום ש-E[A] חיובי וגדול שווה ל-2, זה בהכרח אפשרי. נחסיר 2 מ-E[A]. כל עוד E[A] ≠ 0, נוסיף באחד הצדדים A ואחריו A+1, ונוריד 2 מ-E[A] (כי השתמשנו פעמיים בזוג סדור זה). לאחר מכן, נשים A+2 ב-2 הצדדים, נוריד 2 מ-E[A+1], ואז כל עוד E[A + 1] ≠ 0, נוסיף באחד הצדדים A+1 ואחריו A+2, ונוריד 2 מ-E[A+1]. נשים A+3 ב-2 הצדדים, נוריד 2 מ- E[A + 2], וכו'... עד שנגיע ל-B. במקום להוסיף את B מ-2 הצדדים, נוסיף אותו בצד אחד ונחסיר 1 מ-E[B-1]. כל עוד E[B - 1] ≠ 1, נוסיף לידו B ואז B-1. בסוף המעגל ייסגר (ולכן כאן לא מאפסים את E[B – 1] – כי החיבור האחרון הוא הסגירה של המעגל 😊).
הערה: חלק זה היה חסר במספר פתרונות, שרק הסבירו מדוע אם קיים סידור חוקי האלגוריתם מחזיר תשובה נכונה, אבל לא הסבירו מדוע אם האלגוריתם מחזיר תשובה חיובית אכן קיים סידור חוקי, שזה כמובן חלק חשוב בהסבר הנכונות (גם אלגוריתם שתמיד מדפיס "כן" מקיים את החלק הראשון, אך כמובן שאינו נכון)

אלגוריתם:

A → האיבר הקטן ביותר במערך D
B → האיבר הגדול ביותר במערך D
H → מערך בגודל B – A + 1, כשנשים ב-H[i] את מספר המופעים של A+i במערך D
2H[0] → E // ישמור את מספר הזוגות הסמוכים (i - 1, i) בכל איטרציה
עבור כל i מ-1 עד B – A:
- 2H[i] - E → E
- אם E ≤ 0 או E אי-זוגי:
  - הדפס תשובה שלילית וסיים את ריצת התוכנית
אם E ≠ 0:
- הדפס תשובה שלילית
אחרת:
- הדפס תשובה חיובית

סיבוכיות זמן O(n)

טעות נפוצה:

את המבנה הכללי של ההיסטוגרמה ניתן היה להבין בעוד דרך – ניתן איטרטיבית בכל פעם להוריד את האיבר הקטן ביותר בסידור חוקי עם השכן שלו, ולסגור את החור שנשאר במעגל. הבעיה היא שרבים לא לקחו בחשבון שבסוף אנחנו חייבים להשאר עם B ועם B-1 ולא סתם עם זוג איברים סמוכים, ובמבנה ההסטוגרמה רק בדקו שאם מחשבים את E בדומה לאלגוריתם שלנו, הוא לא נהיה שלילי באמצע. אבל זה לא מספיק – הוא חייב להיות חיובי (כלומר שונה מאפס), אחרת לא ניתן להגיע מ-A ל-B ולחזור בחזרה. לבדוק שההיסטוגרמה רציפה זה לא מספיק, למשל אם נתון D={22022, 22023, 22024, 22025}, התשובה צריכה להיות שלילית.