Chocolate Distribution Problem

Q: מהי סיבוכיות הזמן של בעיית חלוקת השוקולד?

מיון דורש O(n log n) , והזזת החלון של m חבילות דורשת O(n) , ולכן הסיבוכיות הכוללת היא O(n log n) . המקום הנוסף הוא O(n) עבור עותק ממוין, או O(1) מעבר למיון עצמו אם ממיינים את הקלט במקום.

Q: האם בעיית חלוקת השוקולד היא בעיית חלון הזזה?

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

Q: האם אפשר לפתור את בעיית חלוקת השוקולד בלי למיין?

הגדלים כאן הם לכל היותר 10^5 , ולכן מיון ספירה מסדר אותם בזמן O(n + 10^5) , ואותו טיעון תקף. כשאין חסם על הגדלים, אי אפשר לנצח את O(n log n) באמצעות השוואות בלבד: כאשר m = 2 , התשובה היא 0 בדיוק כאשר שתי חבילות שוות, וזיהוי כפילות דורש מספר כזה של השוואות במקרה הגרוע ביותר.

קלמיון חלון נע

+10

יש לך כמה חבילות שוקולד, ו-packets[i] הוא מספר השוקולדים בחבילה i. כל אחד מ-m התלמידים מקבל חבילה אחת בדיוק, ולכן מחלקים m חבילות שונות. בחר אותן כך שההפרש בין החבילה הגדולה ביותר לקטנה ביותר מבין החבילות שחולקו יהיה קטן ככל האפשר.

כתוב פונקציה בשם minDifference שמחזירה את ההפרש הקטן ביותר האפשרי.

פונקציה

minDifference(packets: integer-array, m: integer) → integer

packetsinteger-array: מספר השוקולדים בכל חבילה
minteger: מספר התלמידים, כשכל אחד מקבל חבילה אחת
מחזירהinteger: ההפרש הקטן ביותר האפשרי בין החבילה הגדולה ביותר לחבילה הקטנה ביותר שחולקו

אילוצים

2 ≤ m ≤ packets.length ≤ 10⁴
1 ≤ packets[i] ≤ 10⁵
שתי חבילות יכולות להכיל אותו מספר של שוקולדים.

דוגמאות

קלט: packets = [9, 3, 15, 7, 11, 4]m = 3
פלט: 4
הסבר: לאחר המיון, החבילות הן 3, 4, 7, 9, 11 ו-15. גם 3, 4, 7 וגם 7, 9, 11 נותנים הפרש של 4, ואין שלוש חבילות קרובות יותר זו לזו.

קלט: packets = [8, 1, 5]m = 3
פלט: 7
הסבר: יש שלושה תלמידים ושלוש חבילות, לכן כל חבילה נמסרת וההפרש הוא 8 - 1 = 7.

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

תקן את החבילה הקטנה ביותר

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

האינטואיציה

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

כל אחת מ-n הבחירות מסננת וממיינת עד n חבילות: O(n² log n). כשיש n = 10^4 גדלים שונים, פעולות המיון לבדן דורשות כ-6 × 10^8 השוואות.

אלגוריתם

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

def minDifference(packets, m):
    best = max(packets) - min(packets)  # no gap can be wider than this
    for low in packets:
        # The packets that could go out alongside low, smallest first (low is one of them).
        bigger = sorted(x for x in packets if x >= low)
        if len(bigger) >= m:
            best = min(best, bigger[m - 1] - low)
    return best

מיינו והזיזו חלון של m חבילות

האינטואיציה

בסדר ממוין, בחלון sizes[i..i+m-1] החבילה הקטנה ביותר נמצאת ראשונה והגדולה ביותר אחרונה, ולכן ההפרש שלו הוא sizes[i+m-1] - sizes[i].

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

בדוגמה הראשונה, החלונות בגודל שלוש נותנים 4, 5, 4 ו-6, ולכן התשובה היא 4. המיון עולה O(n log n) וההזזה O(n).

אלגוריתם

מיינו את החבילות בסדר עולה לתוך sizes.
הגדירו את best בתור sizes[m-1] - sizes[0], החלון הראשון.
עבור כל נקודת התחלה i מ-1 עד n-m, השוו את sizes[i+m-1] - sizes[i] ל-best ושמרו את הקטן מביניהם.
החזירו את best.

def minDifference(packets, m):
    sizes = sorted(packets)
    best = sizes[m - 1] - sizes[0]
    # The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
    for i in range(1, len(sizes) - m + 1):
        best = min(best, sizes[i + m - 1] - sizes[i])
    return best

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

סיום החלון ב־i+m במקום ב־i+m-1, כך שהוא מודד m+1 חבילות.
עצירה חלון אחד מוקדם מדי. ערכי ההתחלה נעים מ־0 עד n-m כולל. עבור [1, 10, 20, 21] עם m = 2, לולאה עם i < n-m מפספסת את ההפרש היחיד בגודל 1.
דילוג על המיון. ב־[9, 3, 15, 7, 11, 4] שלוש החבילות הראשונות נבדלות זו מזו ב־12, בעוד שהתשובה היא 4.
מדידת החלון הראשון בלבד. m החבילות הקטנות ביותר הן אפשרות אחת, אבל הקבוצה הטובה ביותר יכולה להתחיל בכל מקום.
מיון מספרים כטקסט. ב־JavaScript, sort() ללא פונקציית השוואה מציב את 100000 לפני 9.

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

מהי סיבוכיות הזמן של בעיית חלוקת השוקולד?

מיון דורש O(n log n), והזזת החלון של m חבילות דורשת O(n), ולכן הסיבוכיות הכוללת היא O(n log n). המקום הנוסף הוא O(n) עבור עותק ממוין, או O(1) מעבר למיון עצמו אם ממיינים את הקלט במקום.

האם בעיית חלוקת השוקולד היא בעיית חלון הזזה?

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

האם אפשר לפתור את בעיית חלוקת השוקולד בלי למיין?

הגדלים כאן הם לכל היותר 10^5, ולכן מיון ספירה מסדר אותם בזמן O(n + 10^5), ואותו טיעון תקף. כשאין חסם על הגדלים, אי אפשר לנצח את O(n log n) באמצעות השוואות בלבד: כאשר m = 2, התשובה היא 0 בדיוק כאשר שתי חבילות שוות, וזיהוי כפילות דורש מספר כזה של השוואות במקרה הגרוע ביותר.

def minDifference(packets, m):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

packets = [9, 3, 15, 7, 11, 4]
m = 3

הפלט הצפוי