שאלות ופתרונות שלב ב' 2025-2026
שאלה ראשונה - אגסים
האחים רד וגולדן קנו המון אגסים אדומים וירוקים, והחליטו לשחק במשחק!
הם סידרו בשורה n מתוך האגסים, אותם נמספר מימין לשמאל מ-0 עד n - 1. צבעי האגסים נתונים במערך A (A[i]=0 אם הצבע של האגס i הוא ירוק, או 1 אם הוא אדום. למשל, A[0] הוא צבע האגס הימני ביותר, A[1] צבע האגס השני מימין, וכו'). את שאר האגסים הם השאירו בערמה בצד, שמאפשרת במהלך המשחק להחליף צבעים של אגסים בשורה (להחליף את האגס הרלוונטי בשורה עם אגס מהצבע הנגדי מהערמה). נתון שבערמה יש לפחות n אגסים ירוקים ולפחות n אגסים אדומים, כך שתמיד יהיה אגס מתאים להחלפות הצבע. החלפות צבעים מותרות רק כחלק מהמהלכים המתוארים בהמשך במסגרת התור.
רד וגולדן משחקים במשחק לסירוגין, כאשר רד מתחיל (רד משחק, ואז גולדן, ואז רד, וכו').
בכל תור, על השחקן שזהו תורו לבחור אגס אדום כלשהו בשורה, ואז לבצע את 2 הפעולות הבאות:
-
להחליף את האגס הנבחר עם אגס ירוק מהערמה.
-
להחליף את הצבע של כל האגסים שמימין לאגס הנבחר (אם יש כאלו).
לאחר החלפת צבע האגס הנבחר וכל האגסים שמימינו, התור נגמר ומגיע תורו של השחקן השני.
במילים אחרות, לאחר התור של כל שחקן, האגס שהשחקן בחר יהפוך להיות ירוק, וכל האגסים שמימינו ישנו את צבעם. האגסים משמאל לאגס הנבחר יישארו באותם הצבעים שהיו בהם לפני התור.
שחקן שבתורו אין לו מהלך חוקי, כלומר שאין אגס אדום שיוכל לבחור, יפסיד במשחק.
ידוע שרד וגולדן מאוד חכמים ואף פעם לא עושים טעויות, כלומר אם לאחד מהם יש אסטרטגיה מנצחת, מובטח שהוא יפעל בצורה נכונה ולא יעשה טעויות שעלולות לאפשר לשחקן השני לנצח.
כתבו אלגוריתם שמקבל את n (מספר האגסים בשורה), ואת המערך A (צבעי האגסים לפי המיקום שלהם בשורה), ויקבע האם המשחק בהכרח יסתיים, ואם כן, האם רד (שמתחיל) או גולדן (השחקן השני) ינצחו במשחק.
הסבירו את נכונות הפתרון שלכם (למשל על ידי תיאור אסטרטגיית הניצחון של רד ושל גולדן, או תיאור מהלך אינסופי של המשחק).
הצג פתרון
תובנות:
-
ניתן להסתכל על המערך כמספר, כש-A[0] זו הספרה הכי פחות משמעותית ו- A[n-1] הספרה הכי משמעותית. הערך של המספר קטן בכל מהלך, משום שבמהלך אנחנו בוחרים 1 כלשהו, הופכים אותו ל-0, וכל שאר השינויים הם רק מימין ל-1 שאיפסנו = בספרות פחות משמעותיות. לכן המשחק תמיד סופי – בכל תור ערך המספר קטן ב-1 לפחות, בסוף הוא חייב להגיע ל-0.
-
בכל תור צבע האגס הימני ביותר (A[0]) משתנה (משתנים צבע האגס הנבחר וכל האגסים שמימינו, ותמיד האגס הימני ביותר כלול בקבוצת האגסים הזו).
אלגוריתם:
-
אם A[0]=1 קבע שרד ינצח, אחרת קבע שגולדן ינצח.
הסבר נכונות:
בחלק של ההבחנות כבר הוכחנו שהמשחק תמיד סופי, ולכן בסופו של דבר נגיע למצב היחיד שבו אין מהלך חוקי - שבו אין אגס אדום לבחור, כלומר שכל האגסים ירוקים. במצב זה בפרט האגס הימני ביותר ירוק (0).
ראינו שצבע האגס הימני ביותר משתנה בהכרח בכל מהלך, לכן אם רד התחיל במצב שבו אגס זה אדום, לאחר תורו הוא תמיד יהיה ירוק, ולכן לאחר תורו של גולדן, שתמיד יקבל מצב בו האגס הימני ביותר ירוק, האגס הימני ביותר יהפוך לאדום (אם לגולדן יש מהלך חוקי). מכיוון שבמצב שבו אין מהלך חוקי האגס הימני ביותר ירוק, בהכרח גולדן יקבל מצב זה, לא משנה כיצד 2 השחקנים ישחקו.
בדומה, אם בתחילת המשחק האגס הימני ביותר ירוק, תמיד רד יקבל מצב כזה, וגולדן תמיד יקבל מצב בו האגס הימני ביותר אדום, ולכן גולדן בהכרח ינצח, לא משנה איזה מהלכים חוקיים כל שחקן יבצע.
סיבוכיות זמן: O(1)
הערה:
ישנן דרכים נוספות להוכיח שהמשחק סופי / למצוא את המנצח.
למשל, כדי לראות שהמשחק סופי, אפשר גם לשים לב שאי אפשר להפוך אגס ירוק לאדום (0 ל-1) מבלי שיהיה לפחות אגס אדום אחד מימינו. לכן, המיקום של האגס האדום השמאלי ביותר לא יכול לזוז שמאלה, אלא רק ימינה.
זה מאפשר להוכיח באינדוקציה שהמשחק סופי, לפי המיקום של האגס האדום השמאלי ביותר (מיקום 1 - יש רק מהלך אחד חוקי ואז אי אפשר להמשיך, ואם נניח שעד מיקום n המשחק סופי, אז עבור מצב שבו האגס האדום השמאלי ביותר במיקום n+1 מהנחת האינדוקציה יש מספר סופי של מהלכים אפשריי מבלי לבחור אותו, ומאז שבוחרים אותו שוב יש מספר סופי של מהלכים).
שאלה שניה - בננות
יונתן החליט להביא למטע הבננות שלו את קוף המחמד שלו – בננובו. במטע הבננות של יונתן יש n עצי בננה בשורה, הממוספרים משמאל לימין מ-0 עד n-1. העץ i בגובה B[i].
יונתן מעוניין לבנות מתקן משחקים לבננובו.
לצורך כך, עליו לבחור 2 עצים כלשהם, ולתלות ביניהם חבל אופקי (מקביל לקרקע) בגובה לבחירתו. כמובן שגובה החבל חייב להיות קטן שווה מגובה כל אחד מ-2 העצים (אחרת לא יוכל לחבר אותו אליהם), וכן אסור שיהיה עץ גבוה יותר מהחבל באמצע (החבל לא יכול לעבור דרך עצים, אך מותר שיהיה עץ שנוגע בו, כלומר בגובה זהה).
לאחר שיתקין את החבל האופקי, יונתן יחבר מעל אחד מהעצים שהחבל עובר מעליהם חבל טיפוס אנכי (מאונך לקרקע), שאורכו הוא בדיוק המרחק מצמרת העץ לחבל האופקי. כך, בננובו יוכל להגיע דרך החבל האופקי לנקודה שבה נמצא החבל האנכי, ואז לצנוח לצמרת העץ שמתחתיו, לקטוף בננה, ולטפס חזרה מעלה.
בננובו אוהב לצנוח מרחק גדול ככל האפשר, לכן יונתן רוצה לבנות מתקן שבו החבל האנכי יהיה ארוך ככל האפשר. במילים אחרות, הוא רוצה שהמרחק בין החבל האופקי לבין צמרת העץ הרחוק ביותר ממנו שנמצא מתחתיו יהיה גדול ככל האפשר.
עזרו ליונתן וכתבו עבורו אלגוריתם, שמקבל את n (מספר העצים בשדה) ואת המערך B (גבהי העצים), יחשב עבורו את אורך החבל האנכי הארוך ביותר האפשרי.
בשאלה זו הניקוד המלא יינתן על סיבוכיות זיכרון אופטימלית (כשהמערך B הוא לקריאה בלבד ולא לעריכה, ולא נחשב לצורך חישוב סיבוכיות הזיכרון), כמובן לא על חשבון סיבוכיות הזמן.
הצג פתרון
תובנות:
-
אם החבל האופקי תלוי בין 2 עצים x,y, הוא יהיה בגובה min(B[x],B[y]) (אחרת תמיד אפשר "להרים" אותו וזה רק יאריך את החבל האנכי מתחתיו).
-
אם החבל האופקי תלוי בין 2 עצים x,y, גובה החבל האנכי (שאנו מעוניינים למקסם), יהיה min(B[x],B[y])-min(B[y],B[y+1],…,B[x]), כלומר הוא יהיה תלוי מעל העץ הנמוך ביותר ביניהם (אחרת, הזזה לעץ נמוך יותר תאריך את החבל האנכי)
-
נניח שאנחנו יודעים מהו העץ שמהווה את הקצה הימני של החבל האופקי. נסמן אותו ב-x. יש 2 אפשרויות – קיים עץ גבוה יותר מ-x משמאלו, או שלא קיים כזה עץ. נניח שמדובר במקרה הראשון, ונסמן את העץ הראשון שגבוה מ-x ונמצא משמאלו (הראשון = הקרוב אליו ביותר, כלומר הימני ביותר משמאלו) ב-y. אופטימלי ש-y יהיה הקצה השמאלי של החבל, והחבל יהיה בגובה B[x].
(נכונות: ניתן למתוח חבל בין x לבין y שכן כל העצים ביניהם נמוכים משניהם, ולא ניתן למתוח חבל שקצה אחד שלו ב-x, כלומר גובהו המירבי הוא B[x], דרך y, שכן B[y]>B[x] ואסור למתוח חבלים "דרך" עצים).
-
נניח שמדובר עכשיו במקרה השני - גובה הקצה הימני של החבל (x) גדול שווה מגובה כל העצים משמאלו.
-
נסמן את העץ הגבוה ביותר משמאל ל-x ב-y (אם יש כמה כאלו – את השמאלי ביותר). אז y הוא קצה שמאלי אופטימלי לחבל האופקי (שכן תמיד ניתן למתוח ביניהם – אין עצים גבוהים יותר באמצע, וגם כאן אי אפשר להעביר "מעבר" ל-y, הפעם כי כל נקודות הקצה ל-y מגבילות את גובה העץ לגובה נמוך יותר). נסמן את גובה העץ הגבוה ביותר משמאל ל-x ב-y. קיים חבל אנכי שגובהו min(B[x],B[y])-min(B[y],B[y+1],…,B[x]), ולא קיים חבל אנכי גבוה יותר עבור פתרון שבו הקצה הימני של החבל האופקי הוא x. החלק השני (לא קיים חבל כזה גבוה יותר) נובע מהבחנות 3 ו-4. החלק שהבחנות 3 ו-4 לא מכסות הוא שבמקרה 3, ייתכן שהעץ הגבוה ביותר משמאל ל-x הוא לא העץ הראשון שגבוה מ-x, אלא עץ גבוה יותר. במקרה זה, אי אפשר לתלות חבל אנכי בין x לבין y, כי הוא יעבור דרך עץ אחר. אבל, אפשר לדמיין שמעבירים חבל בגובה B[x] מ-x ל-y, דרך עצים אחרים, להסתכל על העץ הנמוך ביותר ביניהם שמעליו תלוי החבל האנכי, ואז "לגזור" את החבל האופקי בעץ הראשון משמאל ומימין שהוא עובר דרכם, למשל (החיצים מסמנים את הקצוות החוקיים של החבל האופקי):
וכך ליצור פתרון חוקי בגובה הנ"ל.
אלגוריתם:
-
B[0]→ highest // גובה העץ הגבוה ביותר שראינו עד כה
-
B[0]→ highest // גובה העץ הנמוך ביותר שראינו מאז הכי גבוה
-
O → ans // גובה החבל האנכי הכי ארוך שמצאנו עד כה
-
עבור i מ-1 עד n-1: // נעבור על כל העצים משמאל לימין
-
min(lowest ,B[i]) → lowest
-
אם B[i] ≥ highest:
-
max(ans ,highest - lowest ) → ans // חבל מהעץ הגבוה ביותר עד כה לנוכחי
-
B[i] → lowest
-
B[i] → highest
-
-
אחרת:
-
max(ans ,B[i] - lowest) → ans // חבל בגובה B[i] לפי תובנה 5
-
-
נכונות:
מתובנה 5, בכל איטרציה של הלולאה אנחנו מוצאים אורך חוקי של חבל אנכי, שהוא גם חסם עליון לחבל האנכי הארוך ביותר שאפשר ליצור אם תולים את החבל האופקי כשהעץ i הקצה הימני שלו. מכיוון שעץ כלשהו הוא הקצה הימני של החבל האופקי בפתרון האופטימלי, נמצא בהכרח את גובה החבל האנכי הגבוה ביותר.
סיבוכיות: O(n) זמן, O(1) זכרון נוסף
שאלה שלישית - גודגדנים
סבתא סמית פותחת דוכן גודגדנים חדש בעיר – ומהצלחות העבר שלה התושבים צופים שהגודגדנים בדוכן יהיו המתוקים ביותר בכל המדינה!
n תושבים כבר נעמדו בתור לקראת הפתיחה החגיגית. בדוכן של סבתא סמית משלמים בגרעינים. מספר הגרעינים (מספר שלם אי-שלילי) שכל אחד מהעומדים בתור מחזיק בו נתון לנו במערך C לפי סדר עמידתם בתור (C[0] הוא מספר הגרעינים של הראשון בתור, C[1] של השני בתור, וכו').
ידוע שכל אחד מהעומדים בתור (אם הוא לא הראשון בתור), יכול לשלם למי שעומד ישירות לפניו בתור גרעין אחד כדי לעקוף אותו, וזה שלפניו תמיד יסכים לכך. למשל, אם ללקוח ה-i+1 יש 10 גרעינים, וללקוח ה-i יש 7 גרעינים, אם הלקוח ה-i+1 ירצה לעקוף, הוא ישלם גרעין אחד וישאר עם 9 גרעינים (וכעת הוא יהיה הלקוח במקום ה-i), והלקוח שעקף – שכעת במקום ה-i+1, יישאר עם 8 גרעינים (שכן קיבל גרעין נוסף בתור תשלום על העקיפה).
ידוע גם שלא יתבצעו עקיפות בתור מעבר לכך, כלומר אף אחד לא ייתן לעקוף אותו מבלי שיקבל מהעוקף גרעין אחד בתמורה, וכן שאף אחד לא ישלם יותר מגרעין אחד לזה שלפניו על עקיפה, או יאבד גרעינים.
כמובן שאי אפשר להגיע ל"מספר שלילי" של גרעינים, כלומר לקוח יכול לעקוף רק אם יש ברשותו לפחות גרעין אחד.
כתבו אלגוריתם, שבהינתן n (מספר התושבים בתור) והמערך C (מספר הגרעינים שכל תושב מחזיק בו לפי סדר העמידה הנוכחי שלהם), יקבע האם ניתן באמצעות עקיפות להגיע למצב שבו אף אחד לא מחזיק ביותר גרעינים ממי שעומד ישירות לפניו בתור.
הצג פתרון
תובנות:
-
אם הלקוח i יגיע בסדר החלפות כלשהו למקום j, יהיו לו C[i]-i+j גרעינים, כי בכל החלפה שבה הוא זז קדימה הוא חייב לעקוף = לשלם גרעין אחד, ובכל החלפה שבה הוא זז אחורה עוקפים אותו = הוא מרוויח גרעין אחד.
-
ניצור מערך C2[i]=C[i]-i לכל i. ההבחנה הקודמת אומרת שאם לקוח x מסיים במקום y יהיו לו C2[x]+y גרעינים. השאלה היא האם אפשר להגיע למצב שבו המערך C2[p[0]]+0,C2[p[1]]+1,….,C2[p[n-1]]+n-1 יהיה ממוין, כש-p[x] הוא המקום המקורי של מי שמסיים במקום x. זה אפשרי אם ורק אם אחרי מיון בסדר יורד של המערך C2 זה אפשרי – כלומר לאחר המיון לכל 0≤i<n-1 מתקיים C2[i]+i≥C2[i+1]+i+1⇒C2[i]≥C2[i+1]+1⟹C2[i]>C2[i+1]. כלומר – אמ"ם אין 2 איברים זהים במערך C2.
-
אם אין 2 איברים זהים במערך C2, קיים פתרון דמוי "מיון בועות" שבו בכל העקיפות ללקוח העוקף יש יותר גרעינים מאשר ללקוח שעוקפים. פתרון זה גם מבטיח לנו שאם כולם התחילו עם מספר אי-שלילי של גרעינים, אף אחד לא יגיע למצב שהוא מבצע עקיפה כשאין לו גרעין לשלם, לכן מספיק לבדוק רק האם קיימים 2 איברים זהים במערך C2 על מנת לקבוע האם קיים פתרון.
אלגוריתם:
-
צור מערך C2 באורך n
-
לכל i מ-0 עד n-1:
-
C[i]-i→C2[i]
-
-
מיין את C2 בסדר עולה // לאחר המיון, אם יש 2 ערכים זהים הם יהיו סמוכים
-
לכל i מ-0 עד n-2:
-
אם C2[i]=C2[i+1]:
-
קבע שלא ניתן להגיע למצב הרצוי, וסיים את ריצת התוכנית
-
-
-
קבע שניתן להגיע למצב הרצוי // נגיע לכאן רק אם אין זוג ערכים זהים ב-C2
הסבר נכונות:
-
אם קיימים 2 לקוחות i,j עבורם C[i]-i=C[j]-j, ללקוח שעומד מאחורה יותר בתור יהיו יותר גרעינים מאשר ללקוח השני, לא משנה באיזה מיקומים הם יהיו, לכן במקרה זה אין פתרון (אינטואיטיבית, אם הם יעמדו זה אחר זה, ללקוח מאחור יהיה גרעין אחד יותר מהלקוח שלפניו, ועקיפה תשמר מצב זה, ולכן ניתקע).
-
אם לא קיימים 2 לקוחות כאלו, הפתרון יהיה ליצור את המערך C2[i], ואז בכל פעם להגיע לאיבר הגדול ביותר שלא נמצא במקומו אם נמיין בסדר יורד, ושהוא יבצע עקיפות עד שהוא מגיע למקומו, בסגנון "מיון בועות". בכל עקיפה, מכיוון שבכל פעם אנחנו מביאים את האיבר המקסימלי שלא במקומו למקום שלו, ואין 2 איברים זהים, לעוקף יהיו לפחות 2 גרעינים יותר מלנעקף, והעקיפה יכולה להתבצע. זה גם מבטיח לנו שאף אחד לא יגיע למצב שאין לו גרעינים לשלם (נניח בשלילה שכן. נסתכל על העקיפה הראשונה שבה מישהו צריך לעקוף ולא יכול. לעוקף יש 0 גרעינים, ולנעקף יש פחות ממינוס 2, בסתירה לכך שכולם התחילו עם מספר אי-שלילי של גרעינים וזו העקיפה הלא חוקית הראשונה).
סיבוכיות זמן O(n log n)
שאלה רביעית - דובדבנים
לאור ההצלחה של סבתא סמית, אדון חרמון החליט גם הוא לפתוח דוכן חדש בעיר. הוא הבין שלא יוכל להתחרות במתיקות הגודגדנים של סבתא סמית, אז הוא בחר בשוק מעט שונה – שוק הדובדבנים החמוצים!
בחלון הראווה אדון חרמון סידר בשורה n דובדבנים, הממוספרים משמאל לימין מ-0 עד n-1. הדובדבן ה-i שוקל Dw[i] גרם, והוא ברמת יופי ייחודית של Dp[i].
אדון חרמון ביצע מחקר מעמיק, וגילה שהדרך הטובה ביותר למשוך לקוחות לחנות היא לסדר את הדובדבנים בחלון הראווה לפי רמות היופי שלהם, משמאל לימין (כשהדובדבן השמאלי ביותר הוא עם רמת היופי הנמוכה ביותר, והדובדבן הימני ביותר הוא עם רמת היופי הגבוהה ביותר).
לצורך סידור הדובדבנים אדון חרמון משתמש בכלי פלסטיק מיוחד בעל אורך מתכוונן, שמאפשר לו להחליף בכל פעם בין זוג דובדבנים לבחירתו. כשאדון חרמון בוחר זוג דובדבנים להחלפה, הוא:
-
מכוונן את אורך המכשיר לפי המרחק ביניהם.
-
מכניס את הכף באחד הצדדים של המכשיר מתחת לאחד מהדובדבנים בזוג.
-
מרים את הדובדבן השני בזוג ומניח אותו על הכף בצד השני של המכשיר.
-
מפעיל את המכשיר שמסתובב ב-180 מעלות סביב האמצע שלו, מה שמחליף בין הדובדבנים – הדובדבן הראשון בזוג מגיע למקום שהיה בו הדובדבן השני לפני ההחלפה, ולהפך (כל שאר הדובדבנים לא זזים).
רמת המאמץ הדרושה לאדון חרמון כדי להחליף בין זוג דובדבנים, היא המינימום בין 2 המשקלים של הדובדבנים שהוא מחליף ביניהם (שכן הוא ירים את הדובדבן הקל יותר לצורך ההחלפה).
אדון חרמון לא יזיז אף דובדבן לא במסגרת הפעלות של המכשיר.
כתבו אלגוריתם, שבהינתן n (מספר הדובדבנים בחלון), משקל כל דובדבן (המערך Dw שבאורך n) ורמת היופי של כל דובדבן (המערך Dp שבאורך n), יחשב את רמת המאמץ הכוללת המינימלית הדרושה לאדון חרמון על מנת לסדר את הדובדבנים לפי רמות היופי שלהם. רמת המאמץ הכוללת היא סכום רמות המאמץ בכל ההחלפות שהוא יבצע, כלומר הסכום של המשקל המינימלי בכל זוג שיחליף לאורך הדרך.
הצג פתרון
תובנות:
נשים לב שכיוון שערכי היופי Dp[i] של כל הדובדבנים ייחודיים, לכל דובדבן אנו יודעים לקבוע את האינדקס (מיקום) הסופי בו הוא צריך להיות. נסמן ב-T[i] את האינדקס הסופי של הדובדבן שנמצא תחילה באינדקס i.
כל ה-T[i]ים שונים כיוון שכל דובדבן רוצה להגיע בסוף למקום אחר. נשים לב שאנו יכולים לפצל ככה את הרשימה לאוסף מעגלים, כשכל מעגל יהיה סדרת אינדקסים (i_1,…,i_k ) שתקיים שכל אינדקס רוצה להיות בסוף במיקום של זה שאחריו.
כלומר i_1 רוצה להיות ב-i_2=T[i_1 ], i_2 רוצה להיות ב-i_3=T[i_2 ], וממשיך ככה עד שזה נסגר כש-i_k רוצה להיות ב-i_1=T[i_k ].
ננסה להבין איך מסדרים מעגלים ביעילות.
נשים לב ל-2 הדרכים הבאות שניתן לסדר מעגלים:
-
נגיד ומדובר במעגל (i_1,…,i_k ) (k אורך המעגל). נסמן ב-d את הדובדבן שכרגע במיקום i_k. נוכל להחליף את הדובדבן d עם האחד שב-i_(k-1) וכך האחד שהיה ב-i_(k-1) יגיע למקומו. לאחר מכן להחליף את d שנמצא ב-i_(k-1) עם האחד ב-i_(k-2) וכך האחד ב-i_(k-2) יגיע למקומו ונמשיך כך האלה עד i_1.
במילים אחרות, בכל שלב נחליף את דובדבן d עם האחד שמאחוריו במעגל, עד ש-d מגיע ל-i_1, ובעצם במהלך הדרך הבאנו את כל הדובדבנים במעגל למקומם. סך הכל בוצעו k-1 החלפות כדי למיין את כולם, וכולם השתמשו בדובדבן d. נשים לב שהבחירה ב-i_k כסוף המעגל היא שרירותית כי הרשימה מעגלית, ובעצם אין סיבה שלא נבצע תהליך זה מהדובדבן בעל המשקל המינימלי ביותר מהמעגל, וככה אותו דובדבן מינימלי יהיה המינימלי בכל החלפה.
כך שנוכל למיין מעגל בעלות של (k-1)*w כאשר w זה המשקל המינימלי של דובדבן במעגל. -
נגיד ומדובר במעגל (i_1,…,i_k ) (k אורך המעגל), נוכל להביא דובדבן חיצוני d ולהחליף אותו עם i_k. את הדובדבן שהוצאנו מהמעגל הנתון נסמן ב-e (פעולה 1).
לאחר מכן כמו קודם, נחליף את הדובדבן אחורה במעגל עד i_1 (סך הכל k-1 פעולות), ובכך כל הדובדבנים שהיו במיקומים i_1,…,i_(k-1) הגיעו למיקומם הרצוי. לאחר מכן נחליף את דובדבן d שנמצא במיקום i_1 עם e. e היה בהתחלה במיקום i_k, כלומר רצה להגיע ל-i_1, ולכן הגיע כעת למיקומו הנוכחי. בנוסף e היה במיקום שבו דובדבן d היה לפני שהתחלנו לסדר את המעגל, כך ש-d חזר לאיפה שהתחיל (פעולה 1). בצורה זו מיינו את המעגל ב-k+1 פעולות בשימוש ב-d. אין לנו סיבה לא לבחור ש-d יהיה הדובדבן בעל המשקל המינימלי ביותר מכל רשימת הדובדבנים.
כך שנוכל למיין מעגל בעלות של (k+1)*gw כאשר gw זה המשקל המינימלי של דובדבן ברשימת הדובדבנים.
אלגוריתם:
עבור כל מעגל בחלוקה שלנו, נבחר את הדרך שבעלות נמוכה יותר מבין דרכים (1) או (2).
שימו לב שהראנו 2 דרכים לסדר את המערך, אך עלולות להיות דרכים נוספות יותר זולות, צריך להוכיח שהאלגוריתם שהצענו בעל עלות מזערית, נעשה זאת בסוף.
-
צור מערך זוגות A באורך n
-
לכל i מ-0 עד n-1:
-
pair(Dp[i], i)→A[i]
-
-
מיין את A בסדר עולה לפי הערך הראשון בזוג (ערכי היופי Dp)
// כעת האיבר השני ב-A[i], שנסמנו A[i].second, הוא המיקום ההתחלתי של הדובדבן שצריך להגיע למקום i -
צור מערך T באורך n
-
לכל i מ-0 עד n-1:
-
i→T[A[i].second]
-
-
שמור את הערך הקטן ביותר במערך Dw במשתנה gw
-
אתחל מערך בוליאני visited באורך n המאותחל ב-false
-
0→ans
-
לכל i מ-0 עד n-1:
-
אם visited[i]=false:
-
1→k
-
Dw[i]→w
-
T[i]→j
-
כל עוד j≠i:
-
true→visited[j]
-
min(w, Dw[j])→w
-
T[j]→j
-
k+1→k
-
-
ans+min((k-1)*w,(k+1)*gw)→ans
-
-
-
הדפס את ans
סיבוכיות זמן O(n log n) (עקב המיון, לאחריו - O(n), כי לא מבקרים באיברים אחרי שכבר ביקרנו בהם וסימנו זאת ב-visited).
הוכחת נכונות:
את התובנה הראשונה (אם לא מכניסים למעגל כלשהו איברים מבחוץ, אין דרך זולה יותר לסדר את הדובדבנים במעגל במקומם) קל להוכיח באינדוקציה על אורך המעגל.
כשמותר להעביר איברים בין מעגלים, ההוכחה שעדיין אופטימלי לכל מעגל לבצע k+1 החלפות מורכבת משמעותית, ונשתמש בה במושג "גרף".
נסמן ב-c_1,…,c_m את החלוקה למעגלים ההתחלתית לפי המצב הראשוני במערך הדובדבנים.
סמן ב-gw את משקל הדובדבן המינימלי בכל מערך הדובדבנים.
תהי סדרת מהלכים S כלשהי שמסדרת את המערך. נגדיר גרף על המעגלים, בו יש קשתות בין זוגות מעגלים עבורם ביצענו ב-S החלפה בין אינדקסים שלהם.
ננתח את העלות של כל רכיב קשירות בנפרד, כיוון שאין תלות בין רכיבים קשירים שונים, ונראה שהעלות שלנו לסדר את כל המעגלים ברכיב הינה לא יותר זולה מלסדר כל מעגל באמצעות דרכים (1) ו-(2).
יהי רכיב קשיר מסוים שנניח שמורכב מהמעגלים c_1,…,c_k כש-k זה כמות המעגלים. נסמן ב-l_i את אורך המעגל c_i. סך כל כמות הדובדבנים שברכיב היא: l=l_1+⋯+l_k.
טענה: אם לאחר כל פעולת החלפה, נכתוב מחדש את המעגלים לפי הרצונות החדשים של האינדקסים עבור כל דובדבן למיקומו הסופי, אז פעולת החלפה בין אינדקסים ממעגלים שונים מהשלב הקודם מאחדת את שני המעגלים למעגל אחד, כלומר מקטינה את כמות המעגלים ב-1, ופעולה בין זוג אינדקסים בתוך אותו המעגל מפצלת את המעגל לשני מעגלים, כלומר מגדילה את כמות המעגלים ב-1.
אנו יודעים שבהתחלה בחלוקה שלנו למעגלים יש k מעגלים, ובחלוקה הסופית כל דובדבן נמצא במקומו, כל אינדקס מצביע לעצמו ולכן כל אינדקס יהווה מעגל באורך 1, כך שיהיו l מעגלים. בכל פעולה כמות המעגלים קטנה בלכל היותר 1 ולכן נדרשו לפחות l-k פעולות החלפה. בנוסף לכך, בגרף קשיר בעל k צמתים יש לפחות k-1 קשתות, בפרט כיוון שכל המעגלים שלנו ברכיב קשיר אחד בגרף שבנינו, בוצעו לפחות k-1 מהלכים בין אינדקסים ממעגלים שונים. מהטענה שלנו מתקבל שכל מהלך כזה הקטין את כמות המעגלים ב-1. בפרט היינו צריכים אחר כך לעשות עוד מהלך פירוק מעגלים נוסף על מנת שנגיע בסוף ל-l מעגלים כפי שרצינו. כלומר קיבלנו עוד 2(k-1) פעולות נוספות שנדרשנו לעשות.
בסך הכל בוצעו לפחות: l-k+2(k-1)=l+k-2 פעולות.
נסמן ב-w את משקל הדובדבן המינימלי מכל המעגלים ברכיב הקשיר, ונניח ללא הגבלת הכלליות כי הוא נמצא במעגל c_1. כל הפעולות ברכיב בוצעו אך ורק בין דובדבנים בתוך הרכיב, ובפרט עלות כל החלפה הייתה לפחות w. נקבל אז שהעלות הכוללת הינה לפחות:
(l+k-2)w=(l_1+⋯+l_k+k-2)w=
=((l_1-1)+(l_2+1)+(l_3+1)+⋯+(l_k+1))w=
=(l_1-1)w+(l_2+1)w+(l_3+1)w+⋯+(l_k+1)w≥
≥(l_1-1)w+(l_2+1)gw+(l_3+1)gw+⋯+(l_k+1)gw
כלומר העלות המתקבלת היא לא יותר טובה מלפתור את מעגל c_1 בדרך (1) ואת מעגלים c_2,…,c_k בדרך (2).
טענה זו נכונה בכל רכיב קשיר, ובפרט לכל המעגלים ההתחלתיים שלנו.
כך שמתקבל, שהעלות האופטימלית הינה כאשר מסדרים כל מעגל בנפרד באמצעות דרכים (1) או (2) כפי שרצינו להוכיח.
