Split Array Largest Sum

Q: מהי סיבוכיות הזמן של פיצול מערך כך שהסכום הגדול ביותר יהיה מינימלי?

החיפוש הבינארי רץ בזמן O(n log S) , כאשר n הוא האורך של nums ו- S הוא הסכום שלו. כל בדיקה חמדנית היא מעבר יחיד על המערך, וטווח הערכים המרביים נחצה לאחר כל בדיקה: כ-29 בדיקות כאשר S = 5 × 10^8 . הוא משתמש בזיכרון נוסף של O(1) . תכנות דינמי (DP) דורש זמן O(k·n²) וזיכרון של O(n) .

Q: למה בדיקת ההיתכנות מונוטונית?

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

Q: למה הבדיקה החמדנית מוצאת את מספר החלקים הקטן ביותר?

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

Q: האם החיפוש הבינארי עובד עם מספרים שליליים?

לא. עם ערכים שליליים, הוספת ערך יכולה להקטין את הסכום, ולכן אלגוריתם חמדני עלול לסגור חלק מוקדם מדי ולהחמיץ חלוקה שעובדת. גם פיצול של חלק יכול להגדיל את הסכום של אחד החלקים מעבר לסכום של החלק כולו, ולכן העובדה שיש פחות מ־ k חלקים כבר לא אומרת שחלוקה ל־ k חלקים תעבוד. ה־DP אינו מניח אף אחת מההנחות האלה ונשאר נכון, בזמן של O(k·n²) .

קשהחיפוש בינארי תכנון דינמי

+10

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

החזר את העלות הקטנה ביותר שניתן להשיג בכל חלוקה ל־k חלקים.

פונקציה

splitArray(nums: integer-array, k: integer) → integer

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

אילוצים

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
כל חלק מכיל לפחות ערך אחד. סכום הערכים בחלק שכל ערכיו הם 0 הוא 0, וזה מותר.

דוגמאות

קלט: nums = [6, 2, 9, 4, 7, 3]k = 3
פלט: 13
הסבר: לפיצול [6, 2], [9, 4], [7, 3] יש סכומים 8, 13 ו־10, ולכן העלות שלו היא 13. אין פיצול שעלותיו 12: אריזת החלקים משמאל לימין כך שכל סכום יהיה לכל היותר 12 נותנת [6, 2], [9], [4, 7], [3] — ארבעה חלקים, כשרק שלושה מותרים.

קלט: nums = [8, 1, 1, 1, 5]k = 2
פלט: 8
הסבר: ה־8 נמצא בחלק כלשהו, ולכן שום חלוקה לא יכולה לעלות פחות מ־8. גם [8] וגם [1, 1, 1, 5] מסתכמים ב־8, ולכן מגיעים ל־8.

+20 בדיקות נסתרות בשליחה

שאלת המשך

כל בדיקה חמדנית קוראת את כל ערכי n. בעזרת סכומי קידומות, בדיקה יכולה למצוא היכן כל חלק מסתיים באמצעות חיפוש בינארי. כמה מהר פועלת השיטה כולה כאשר k קטן ו-nums ארוך?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

שתי הדרישות מושכות לכיוונים מנוגדים: חייבים להשתמש בדיוק ב־k חלקים, ורוצים שהחלק הגדול ביותר יהיה קטן ככל האפשר. ניסיון לבדוק כל מיקום אפשרי עבור k-1 החיתוכים מוביל למספר עצום של אפשרויות, ותוכנית דינמית על קידומות מצמצמת זאת ל־O(k·n²), אבל זה עדיין איטי מדי עבור 5000 ערכים. הרעיון המהיר הופך את השאלה. במקום לחפש את החלוקה הטובה ביותר, מנחשים גבול עליון ושואלים אם אפשר להשאיר את k החלקים מתחתיו. מעבר חמדני אחד עונה על כך, התשובות מתהפכות פעם אחת בלבד כשהגבול העליון גדל, וחיפוש בינארי מוצא את נקודת ההיפוך בכ־29 מעברים.

תכנות דינמי על פני תחיליות

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

התבוננו בחלק האחרון של חלוקה. אם j הערכים הראשונים יוצרים p חלקים, אז החלק האחרון הוא קטע כלשהו nums[i..j-1], ו־i הערכים הראשונים יוצרים את p-1 החלקים האחרים. העלות היא הגדולה מבין שני מספרים: העלות של אותם p-1 חלקים, וסכום הקטע האחרון. לא משנה מהו הקטע האחרון, נרצה לחלק את i הערכים הראשונים בעלות הנמוכה ביותר האפשרית, והחלוקה הטובה ביותר הזאת אינה תלויה בדבר שנמצא אחריה. לכן אפשר לחשב אותה פעם אחת ולהשתמש בה שוב.

נסמן ב־best[p][j] את העלות הקטנה ביותר של חלוקת j הערכים הראשונים ל־p חלקים. כשיש חלק אחד אין ברירה: best[1][j] הוא סכום j הערכים הראשונים. כשיש יותר חלקים, ננסה כל התחלה i של החלק האחרון: best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), כאשר prefix[j] הוא סכום j הערכים הראשונים. ערכי ההתחלה של i הם מ־p-1, כי p-1 חלקים לא ריקים זקוקים לפחות ל־p-1 ערכים, ועד j-1, כי החלק האחרון זקוק לערך אחד. התשובה היא best[k][n]. שורה p קוראת רק את שורה p-1, ולכן מספיקות שתי שורות באורך n+1.

בדוגמה הראשונה, חלוקת [6, 2, 9, 4] לשני חלקים יכולה להסתיים אחרי 6 (עלות max(6, 15) = 15), אחרי 2 (max(8, 13) = 13) או אחרי 9 (max(17, 4) = 17), ולכן best[2][4] = 13. לאחר מכן, best[3][6] בודק את החלק האחרון [7, 3] ומקבל max(13, 10) = 13, תוצאה שאף נקודת התחלה אחרת אינה משפרת.

הבעיה היא כמות העבודה. יש k שורות, n נקודות סיום בכל שורה, ועד n נקודות התחלה לכל נקודת סיום: עד k·n²/2 צעדים. כאשר n = 5000 ו־k = 2500, הלולאה הפנימית רצה בערך 1.8 × 10^10 פעמים: 18 שניות, אפילו בקצב של 10^9 צעדים פשוטים בשנייה. עדיין כדאי להכיר את תכנות דינמי הזה: הוא אינו מניח שהערכים אינם שליליים, ולכן הוא ממשיך לעבוד במקרים שבהם השיטה המהירה אינה עובדת.

אלגוריתם

בנה את prefix, כאשר prefix[j] הוא הסכום של j הערכים הראשונים.
הגדר את השורה עבור חלק אחד: best[j] = prefix[j].
עבור כל מספר חלקים p מ-2 עד k, וכל נקודת סיום j מ-p עד n, קח את המינימום על פני i מ-p-1 עד j-1 של max(best[i], prefix[j] - prefix[i]).
שמור את ערכי המינימום האלה בשורה חדשה והגדר אותה בתור best.
החזר את best[n].

def splitArray(nums, k):
    n = len(nums)
    # prefix[j] is the sum of the first j values
    prefix = [0] * (n + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    # best[j]: the smallest largest part when the first j values form one part
    best = prefix[:]
    for parts in range(2, k + 1):
        nxt = [0] * (n + 1)
        for j in range(parts, n + 1):
            lowest = prefix[j]  # never worse than one part holding everything
            for i in range(parts - 1, j):
                # the first i values form parts-1 parts, nums[i..j-1] is the last part
                worst = max(best[i], prefix[j] - prefix[i])
                if worst < lowest:
                    lowest = worst
            nxt[j] = lowest
        best = nxt
    return best[n]

חיפוש בינארי על הסכום הגדול ביותר

האינטואיציה

הפכו את השאלה. בחרו מגבלה c ושאלו: האם אפשר לחלק את nums ל־k חלקים כך שסכום כל חלק יהיה לכל היותר c? התשובה לבעיה היא המגבלה הקטנה ביותר שעבורה התשובה היא כן. השאלה הזאת קלה בהרבה מהשאלה המקורית, משתי סיבות.

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

שנית, פחות חלקים מ־k טובים בדיוק כמו k חלקים. אם האלגוריתם החמדני זקוק ל־m < k חלקים, חלקו חלק שמכיל שני ערכים או יותר לשניים. סכומי החלקים אינם גדולים מסכום החלק כולו, כי אין ערכים שליליים, ומכיוון ש־n ≥ k, תמיד יהיה חלק כזה עד שתגיעו ל־k. לכן הבדיקה היא partsNeeded(c) ≤ k.

כעת לתכונה המרכזית: הבדיקה מונוטונית. אם המגבלה c עובדת, גם c+1 עובדת, כי אותה חלוקה עדיין עומדת במגבלה גדולה יותר. בטווח המגבלות מ־max(nums) ועד sum(nums), התשובות הן לא, לא, ..., לא, כן, כן, ..., כן, ואתם רוצים את הכן הראשון. הטווח בטוח בשני קצותיו: שום מגבלה הנמוכה מ־max(nums) אינה יכולה להכיל את הערך הזה, והסכום הכולל תמיד נכנס בחלק אחד. הכן הראשון הוא גם עלות ממשית, ולא רק חסם: אם סכום אף אחד מהחלקים בחלוקה שלו אינו בדיוק c, גם המגבלה c-1 תעבוד.

עקבו אחר הדוגמה הראשונה, [6, 2, 9, 4, 7, 3] עם k = 3. המגבלות נעות בין 9 ל־31. במגבלה 20 מתקבלים החלקים [6, 2, 9], [4, 7, 3]: שני חלקים, כן, ולכן הטווח מצטמצם מ־9 עד 20. במגבלה 14 מתקבלים [6, 2], [9, 4], [7, 3]: שלושה חלקים, כן, והטווח הוא 9 עד 14. במגבלה 11 מתקבלים [6, 2], [9], [4, 7], [3]: ארבעה חלקים, לא, והטווח הוא 12 עד 14. במגבלה 13 נדרשים שלושה חלקים, כן, והטווח הוא 12 עד 13. במגבלה 12 נדרשים ארבעה חלקים, לא, ולכן התשובה היא 13.

כל מעבר קורא n ערכים והטווח נחצה בכל פעם. עם סכום כולל S של עד 5 × 10^8, מדובר בכ־29 מעברים על פני 5000 ערכים, כלומר בערך 150000 צעדים.

אלגוריתם

הגדירו את lo = max(nums) ואת hi = sum(nums).
כל עוד lo < hi, קחו את mid = lo + (hi - lo) / 2.
ספרו כמה חלקים נדרשים בגישה חמדנית תחת מגבלת mid: התחילו עם חלק אחד וסכום מצטבר של 0; כאשר הוספת ערך תחרוג מ-mid, הוסיפו חלק והתחילו מחדש את הסכום עם אותו ערך.
אם המספר הוא לכל היותר k, הגדירו hi = mid; אחרת הגדירו lo = mid + 1.
החזירו את lo.

def splitArray(nums, k):
    def parts_needed(cap):
        # Fill each part left to right and start a new one only when the next value would pass cap.
        parts, current = 1, 0
        for x in nums:
            if current + x > cap:
                parts += 1
                current = x
            else:
                current += x
        return parts

    lo, hi = max(nums), sum(nums)  # one value per part at best, everything in one part at worst
    while lo < hi:
        mid = (lo + hi) // 2
        if parts_needed(mid) <= k:
            hi = mid  # mid works, so the answer is mid or smaller
        else:
            lo = mid + 1  # mid needs more than k parts, so the answer is larger
    return lo

מלכודות ומקרי קצה

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

התחלה של lo מתחת ל-max(nums). הבדיקה החמדנית שמה ערך שגדול מהמגבלה בחלק משלו וממשיכה, ולכן מדווחת שמגבלה של 5 מתאימה עבור [1, 9] עם k = 2. התחילו מהערך הגדול ביותר, או גרמו לבדיקה להיכשל כשערך בודד חורג מהמגבלה.
בדיקה של partsNeeded(c) == k. לעיתים קרובות האלגוריתם החמדני זקוק לפחות חלקים מ-k: עבור [3, 0, 4] ו-k = 3, מגבלה של 4 מחלקת ל-[3, 0], [4]. עם == שום מגבלה לא תעבור. תמיד אפשר לחלק עוד חלקים, ולכן בדקו ≤ k.
ספירת החלקים החל מ-0. החלק הראשון קיים עוד לפני שערך כלשהו חורג ממנו, לכן הספירה מתחילה ב-1.
הצבת hi = mid - 1 כאשר mid מצליח. כך אפשר לדלג על התשובה עצמה. השאירו את hi = mid והשתמשו בלולאה כל עוד lo < hi.
התחלת ה-i של ה-DP ב-0. תא best[i] כאשר i < p-1 מייצג פחות ערכים ממספר החלקים, דבר שאף חלוקה לא יכולה לעשות, ובשורה שמלאה באפסים הוא נקרא כעלות 0. עבור [100, 1, 1] עם k = 3, ה-DP מדווח אז 2 במקום 100. התחילו את i מ-p-1.
גלישה בגבולות גדולים יותר. כאן הסכום הוא לכל היותר 5 × 10^8, ולכן מספרים שלמים בני 32 סיביות מספיקים. אם הערכים מגיעים ל-10^6, כבר 2148 מהם חורגים מ-2^31-1, ולכן השתמשו בסכומים בני 64 סיביות.

שאלות נפוצות4

מהי סיבוכיות הזמן של פיצול מערך כך שהסכום הגדול ביותר יהיה מינימלי?

החיפוש הבינארי רץ בזמן O(n log S), כאשר n הוא האורך של nums ו-S הוא הסכום שלו. כל בדיקה חמדנית היא מעבר יחיד על המערך, וטווח הערכים המרביים נחצה לאחר כל בדיקה: כ-29 בדיקות כאשר S = 5 × 10^8. הוא משתמש בזיכרון נוסף של O(1). תכנות דינמי (DP) דורש זמן O(k·n²) וזיכרון של O(n).

למה בדיקת ההיתכנות מונוטונית?

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

למה הבדיקה החמדנית מוצאת את מספר החלקים הקטן ביותר?

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

האם החיפוש הבינארי עובד עם מספרים שליליים?

לא. עם ערכים שליליים, הוספת ערך יכולה להקטין את הסכום, ולכן אלגוריתם חמדני עלול לסגור חלק מוקדם מדי ולהחמיץ חלוקה שעובדת. גם פיצול של חלק יכול להגדיל את הסכום של אחד החלקים מעבר לסכום של החלק כולו, ולכן העובדה שיש פחות מ־k חלקים כבר לא אומרת שחלוקה ל־k חלקים תעבוד. ה־DP אינו מניח אף אחת מההנחות האלה ונשאר נכון, בזמן של O(k·n²).

Python

def splitArray(nums, k):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

nums = [6, 2, 9, 4, 7, 3]
k = 3

צפוי