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

שאלה ראשונה - אשכוליות

פוג'י אוהב אשכוליות!

הוא קיבל במתנה n אשכוליות, שהמשקלים שלהן נתונים במערך A (שבאורך n).

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

פוג'י גם מאוד אוהב את המספר שלוש.

הוא תוהה בכמה דרכים הוא יכול לבחור 3 אשכוליות מתוך n האשכוליות שקיבל, כך שסכום המשקלים שלהן יתחלק ב-3 ללא שארית. 2 דרכים יחשבו שונות אם יש אשכולית שפוג'י בחר באחת הדרכים שהוא לא בחר בדרך השנייה (כלומר סדר השלשה לא משנה).

עזרו לפוג'י וכתבו עבורו אלגוריתם, שמקבל את n (מספר האשכוליות), ואת המערך A (משקלי האשכוליות שקיבל), וידפיס את מספר השלשות של אשכוליות שסכום משקליהן מתחלק ב-3.

הצג פתרון

תובנות:

סכום 3 מספרים יתחלק ב-3 אמ"מ שארית החלוקה שלהם ב-3 שונה זו מזו, או זהה זו לזו.
משנה לנו לכן רק מה שאריות החלוקה ב-3 של כל המשקלים, או יותר במדויק – כמה אשכוליות יש ששארית החלוקה של משקלן ב-3 היא 0, כמה יש ששארית החלוקה של משקלן ב-3 היא 1, וכמה יש ששארית החלוקה של משקלן ב-3 היא 2.

אלגוריתם:

הסבר:

מספר הדרכים לבחור 3 אשכוליות מתוך x הוא (x∙(x-1)∙(x-2))/6 (x אפשרויות לאשכולית הראשונה שבוחרים, ואז x-1 נשארות מתוכן בוחרים את השנייה, ואז x-2 לשלישית, ומחלקים ב-6 שזה מספר הפעמים שספרנו את אותה השלשה בסדרים שונים), וכך נחשב לכל שארית חלוקה (0, 1 או 2) מה מספר השלשות עם אותה שארית החלוקה ונסכום אפשרויות אלו.
בנוסף, מספר השלשות שבהן יש אשכולית אחת מתוך M[0] אפשריות, אשכולית אחת מתוך M[1] אפשריות, ואשכולית אחת מבין M[2] אפשריות, הוא M[0]∙M[1]∙M[2], כי כל הקבוצות האלו זרות (לכל משקל של אשכולית יש שארית חלוקה אחת ב-3).
מהתובנות כיסינו את כל הדרכים האפשריות לבחור 3 אשכוליות שסכום משקלן מתחלק ב-3. לא נדרשה הוכחה להבחנה, אבל אפשר להראות ששארית חלוקה זהה או שונה מתאימות:
3x+(3y+1)+(3z+2)=3(x+y+z)+3=3(x+y+z+1) 3x+i+3y+i+3z+i=3(x+y+z+i)
ושאם 2 שאריות חלוקה ב-3 זהות גם השלישית חייבת להיות זהה כדי שהסכום יתחלק ב-3 (אפשר גם כמובן לבדוק את כל המקרים, אין הרבה כאלו): 3x+i+3y+i+3z+j=3a ⟹ j=3(a-x-y-z-i)+i

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

שאלה שניה - בילימבי

בילימבי הוא פרי דמוי מלפפון בעל טעם חמוץ יחסית.

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

בילימבי רגיש מאוד לטמפרטורה, וחשוב לאכסן כל פרי בטמפרטורה המתאימה לו.
סבתא סמית קיבלה n פירות בילימבי. לכל אחד מהפירות יש טווח טמפרטורות שבו חייבים לאכסן אותו. את הפרי i יש לאכסן בטמפרטורה בין Bmin[i] (כולל) לבין Bmax[i] (כולל). שתי הטמפרטורות הללו יהיו מספרים שלמים וחיוביים עבור כל פרי.
לצורך האכסון של הפירות סבתא סמית יכולה לקנות מקררים מיוחדים. כל מקרר נפרד היא יכולה לכוון לטמפרטורה קבועה לבחירתה, וכל אחד מהמקררים מספיק גדול כדי לאכסן כמה פירות בילימבי שהיא רוצה.
סבתא סמית מעוניינת לקנות כמה שפחות מקררים, כך שהיא תוכל לאכסן את כל n הפירות שקיבלה במקררים אלו (לאחר שתקבע את הטמפרטורות של כל מקרר כרצונה), ושכל אחד מהפירות יהיה במקרר שהטמפרטורה שלו מתאימה לו.
עזרו לסבתא סמית וכתבו עבורה אלגוריתם, שמקבל את n (מספר פירות הבילימבי), ואת המערכים Bmin, Bmax (המייצגים את טווח הטמפרטורות המתאים לאכסון כל פרי, כל אחד מהמערכים באורך n), וידפיס את מספר המקררים הקטן ביותר שסבתא סמית חייבת לקנות לצורך המשימה.

הצג פתרון

תובנות:

נסתכל על הפרי שהטמפרטורה הגבוהה ביותר שמתאימה לו נמוכה ביותר (Bmax מינימלי). חייב להיות מקרר בטווח שלו, ואפשר לכוון מקרר זה ל-Bmax שלו בדיוק, שכן ה-Bmax של שאר הפירות גבוה יותר, כך שטמפרטורה זו לא יכולה להיות גבוהה מידי עבורם (רק נמוכה מידי, אבל במקרה זה הם לא היו יכולים להיות עם הפרי הזה ביחד בכל מקרה כי אין חפיפה בטווחים – לפרי זה לא מתאימה אף טמפרטורה גבוהה יותר). מכאן כבר נובע אלגוריתם בסיבוכיות של O(n^2) – לקחת פרי זה, לכוון מקרר ל-Bmax שלו, להוריד את כל הפירות שהמקרר בטווח שלהם, וחוזר חלילה.
נניח ששמנו מקרר בטמפרטורה של Bmax המינימלי (נסמנו t0). מהי הטמפרטורה שכדאי לשים למקרר הבא, אחרי שהורדנו את כל הפירות ש-t0 בטווח שלהם?

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

אלגוריתם:

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

סיבוכיות: O(n log n)

אלטרנטיבות:

זהו לא הפתרון היחיד.

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

שאלה שלישית - משחק הגויאבות

האחים רד וגולדן משחקים במשחק הגויאבות!
במשחק יש 4 סלסלות, בכל אחת מהן יש מספר שלם אי-שלילי כלשהו (יכול להיות 0) של גויאבות. שני השחקנים רואים בדיוק כמה גויאבות יש בכל סלסלה בכל רגע נתון.
רד וגולדן משחקים במשחק לסירוגין כשרד מתחיל, כלומר רד מבצע תור, ואז גולדן, ואז רד, ואז גולדן, וכו'.
בכל תור, על השחקן שזהו תורו לבחור 2 סלסלות (לא ריקות) מתוך ה-4 לבחירתו, ולהוציא מכל אחת מהן מספר שלם חיובי (כלומר אסור 0) של גויאבות. מספר זה לא תלוי בין הסלסלות או בין התורות, כלומר בכל תור באופן בלתי תלוי השחקן בוחר את 2 הסלסלות שהוא רוצה, ובאופן בלתי תלוי הוא בוחר כמה גויאבות להוציא מהסלסלה הראשונה וכמה להוציא מהסלסלה השנייה
(אפשר את אותו המספר, אפשר מספרים שונים).
מי שאין לו בתורו מהלך חוקי – מפסיד במשחק, וכאמור רד מבצע את המהלך הראשון.
בהנחה שרד וגולדן הם שחקנים שלא עושים טעויות ומשחקים תמיד את האסטרטגיה הטובה ביותר (כלומר אם לאחד מהם יש אסטרטגיה שהוא יכול לנצח בה, הוא ישחק לפיה ולא יעשה טעות שתאפשר לשחקן השני לנצח), כתבו אלגוריתם שמקבל את מספר הגויאבות בכל סלסלה בתחילת המשחק (4 מספרים שלמים אי-שליליים - c1, c2, c3, c4), ויקבע מי ינצח – רד (שמתחיל) או גולדן.
מזכירים (כמו בכל השאלות) להסביר את תשובתכם (למשל תארו כיצד המנצח ישחק בכל שלב במשחק).

הצג פתרון

תובנות:

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

אלגוריתם:

נמיין את c1, c2, c3, c4 בסדר עולה.
אם c1≠c3 רד מנצח, אחרת גולדן מנצח.

הוכחה:

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

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

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

לאדון חרמון יש n דלוריות, שהגדלים שלהן (מספרים שלמים וחיוביים) נתונים במערך D (שבאורך n), אותן הוא סידר בשורה משמאל לימין.

D[i] הוא גודל הדלורית במקום ה-i משמאל בשורה.

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

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

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

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

לדוגמה, אם {1, 8, 1} = D התשובה תהיה 21, כאשר המקטעים הרציפים הם {1} (הפרש 0), {1, 8} (הפרש 7), {1, 8, 1} (הפרש 7), {8} (הפרש 0), {8, 1} (הפרש 7), ו-{1} (הפרש 0). סה"כ סכום ההפרשים בכל המקטעים הוא 0+7+7+0+7+0=21.

הצג פתרון

תובנות:

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

הבעיות של למצוא את סכום המקסימומים ואת סכום המינימומים שקולות. נראה איך מוצאים את סכום המקסימום בכל מקטע.
בהנחה שכל האיברים היו שונים זה מזה – אפשר היה לספור לכל דלורית בכמה מקטעים היא המקסימום, ואז לסכום עבור כל דלורית את מספר המקטעים הזה * גודל הדלורית.
- נניח שאנחנו בדלורית i. יהי l מיקום הדלורית הימנית ביותר שמשמאל ל-i וגדולה מהדלורית i (כלומר l<i מקסימלי המקיים D[l]>D[i]), או 1- אם אין כזו. יהי r בדומה מיקום הדלורית השמאלית ביותר שמימין ל-i וגדולה ממנה (r>i מינימלי המקיים D[r]>D[i]), או n אם אין כזו.
- המקטעים שבהם הדלורית i מקסימלית הם כל המקטעים שמתחילים אחרי הדלורית l, מסתיימים לפני הדלורית r ושהדלורית i נמצאת בהן, כלומר מתחילים בין l+1 לבין i (i-l אפשרויות) ומסתיימים בין i לבין r-1 (r-i אפשרויות), כלומר יש בדיוק (i-l)∙(r-i) מקטעים כאלו.
אפשר להתמודד גם עם גדלים זהים של דלוריות: הבעיה בגדלים זהים היא שיכול להיות שבחלק מהמקטעים יהיו כמה דלוריות שהן המקסימום במקטע, ואנחנו לא רוצים לספור לאותו הקטע את המקסימום פעמיים (בדמות דלוריות שונות). לכן נרצה הגדרה עבור כל מקטע של דלורית יחידה שתחשב מקסימלית. ניתן לעשות זאת אם למשל לכל מקטע קובעים שסופרים את הדלורית המקסימלית הימנית ביותר (כשובר שוויון – אם יש כמה דלוריות בגודל מקסימלי, ניקח את הימנית ביותר). ואז השאלה היא עבור כל דלורית בכמה מקטעים היא המקסימלית הימנית ביותר?
- הפתרון מאוד דומה – המקום השמאלי ביותר שיכול להיות באותו המקטע הוא בדלורית הכי ימנית (משמאל לנוכחית) שגדולה ממש מהדלורית הנוכחית, אבל המקום הימני ביותר הוא בלורית הכי שמאלית (מימין לנוכחית) שגדולה או שווה לדלורית הנוכחית, שכן אם יש דלורית באותו הגודל אבל ימנית יותר, הנוכחית כבר לא תהיה המקסימלית הימנית ביותר במקטע.
נניח i<j<k וגם D[i]<D[j]. לא ייתכן ש-D[i] היא הדלורית הימנית ביותר משמאל ל-k שגדולה מ-D[k], כי אז גם D[j] גדול מ-D[k] אבל j ימנית יותר וגם משמאל ל-k.
- לכן, כדי למצוא את הדלורית הימנית ביותר הגדולה מדלורית כלשהי ומשמאל לה, לא רלוונטיות אף פעם דלוריות שכבר ראינו דלוריות גדולות יותר מהן מימינן.
- אפשר (למציאת הדלורית שסימנו l לכל דלורית – הימנית ביותר שגדולה ממנה משמאלה) לשמור את כל הדלוריות שרלוונטיות עד כה במחסנית / מערך. בכל פעם כשיש דלורית חדשה, אפשר להוציא מהמחסנית מהסוף את כל הדלוריות שקטנות ממנה (או שוות לה בכיוון הזה), כי הן לא יהיו רלוונטיות יותר לעולם. הדלורית הראשונה שלא נוציא היא הימנית ביותר שגדולה מהדלורית הנוכחית ומשמאל לה (או אם המחסנית התרוקנה – אין כזו). עכשיו אפשר להכניס את הדלורית הנוכחית (שקטנה יותר) למחסנית ולהמשיך הלאה.
  המחסנית תכיל בכל שלב סדרה של דלוריות שכל אחד קטנה שווה / קטנה יותר (תלוי בכיוון האם אנו מאפשרים שוויון) מזו שלפניה, שהן הדלוריות שיכולות להיות רלוונטיות להבא.

אלגוריתם:

הסבר:

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

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