Aggressive Cows

Q: מהי סיבוכיות הזמן של Aggressive Cows?

המיון דורש O(n log n) וחיפוש בינארי דורש O(n log D) , כאשר D הוא הטווח של הדוכנים חלקי k-1 . מלבד עותק ממוין, הזיכרון הנדרש הוא O(1) .

Q: למה הפרה הראשונה תמיד נכנסת לתא השמאלי ביותר?

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

Q: איך מזהים חיפוש בינארי לפי התשובה?

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

בינוניחיפוש בינארי מיון אלגוריתם חמדן

+10

ברפת יש תאים לאורך קו ישר אחד, ו־stalls[i] הוא המיקום של תא i. כל המיקומים שונים זה מזה ואינם מסודרים בסדר מסוים. עליך להציב k פרות ב־k תאים שונים. הפרות רבות כשהן עומדות קרוב זו לזו, ולכן ברצונך להרחיק ככל האפשר את שתי הפרות הקרובות ביותר.

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

פונקציה

aggressiveCows(stalls: integer-array, k: integer) → integer

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

אילוצים

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
כל המיקומים ב־stalls נבדלים זה מזה.
2 ≤ k ≤ stalls.length

דוגמאות

קלט: stalls = [10, 1, 7, 4, 15]k = 3
פלט: 6
הסבר: הפרות בעמדות 1, 7 ו-15 נמצאות במרחקים של 6 ו-8 זו מזו. פער של 7 נכשל: אחרי 1 הפרה הבאה מוצבת בעמדה 10, ואין עמדה ב-17 או מעבר לה.

שאלת המשך

מה משתנה אם הדוכנים עומדים במעגל, כך שהדוכן האחרון בסדר הוא גם שכן של הדוכן הראשון?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

מיין, ואז נסה כל פער בתורו

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

האינטואיציה

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

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

מרווח של 1 תמיד מתאים, לכן ננסה g = 2, 3, ... ונעצור במרווח הראשון שמציב פחות מ-k פרות. בדוגמה הראשונה, מרווח 6 מציב 3 פרות ומרווח 7 מציב רק 2, ולכן התשובה היא 6.

עם שתי פרות ודירים במיקומים 0 ו-10^9, מדובר בכ-10^9 מעברים על פני 5000 דירים, כלומר 5 × 10^12 צעדים.

אלגוריתם

מיין את המיקומים.
כתוב את הבדיקה עבור פער g: פרה אחת ב-pos[0], ואז פרה בכל דוכן שבו pos[i] - last ≥ g, תוך ספירת הפרות.
התחל עם gap = 1.
כל עוד הבדיקה עבור gap + 1 מציבה לפחות k פרות, הוסף 1 ל-gap.
החזר את gap.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    gap = 1  # positions are distinct, so a gap of 1 always fits every cow
    while cowsPlaced(pos, gap + 1) >= k:
        gap += 1
    return gap

חיפוש בינארי על הפער

האינטואיציה

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

החיפוש מתחיל מ־lo = 1, שתמיד עובד, ועד hi = הטווח חלקי k-1, בעיגול כלפי מטה: k פרות משאירות k-1 מרווחים בתוך הטווח, ולכן המרווח הקטן ביותר לא יכול להיות גדול יותר. בדיקה מוצלחת מציבה lo = mid, ולכן צריך לעגל את mid כלפי מעלה; בעיגול כלפי מטה, lo = 5 ו־hi = 6 יחזרו לנצח.

בדוגמה הראשונה הטווח הוא 14 ו־k = 3, ולכן hi = 7. מרווח 4 עובר, מרווח 6 עובר, מרווח 7 נכשל, והטווח נסגר על 6.

טווח ברוחב עד 10^9 נסגר בכ־30 בדיקות של 5000 דוכנים, כלומר בערך 150,000 צעדים.

אלגוריתם

מיינו את המיקומים.
הגדירו lo = 1 ואת hi = (pos[n-1] - pos[0]) / (k-1), בעיגול כלפי מטה.
כל עוד lo < hi, קחו את mid = lo + (hi - lo + 1) / 2.
אם הבדיקה החמדנית ב-mid מציבה לפחות k פרות, הגדירו lo = mid; אחרת הגדירו hi = mid - 1.
החזירו את lo.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    lo = 1  # positions are distinct, so a gap of 1 always works
    hi = (pos[-1] - pos[0]) // (k - 1)  # k-1 gaps share the whole span
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up so lo = mid always moves
        if cowsPlaced(pos, mid) >= k:
            lo = mid  # mid fits, so the answer is mid or larger
        else:
            hi = mid - 1  # mid does not fit, so the answer is smaller
    return lo

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

דילוג על המיון. במערך הלא ממוין [10, 1, 7, 4, 15] עם פער 6, הבדיקה מתחילה ב־10, לא מוצאת אחריו אף תא רחוק ממנו ב־6, ומדווחת על פרה אחת.
עיגול mid כלפי מטה כשבמעבר נקבע lo = mid. ברגע ש־hi = lo + 1, הטווח מפסיק להצטמצם והלולאה לא מסתיימת לעולם.
בדיקה אם יש בדיוק k פרות. בפער 1, הדוגמה הראשונה מציבה 5 פרות — יותר מ־3 — ובכל זאת הפער מתאים; יש לבדוק count ≥ k.
התחלת ספירת הפרות מ־0. הפרה שבתא השמאלי ביותר נספרת, ולכן הספירה מתחילה מ־1.

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

מהי סיבוכיות הזמן של Aggressive Cows?

המיון דורש O(n log n) וחיפוש בינארי דורש O(n log D), כאשר D הוא הטווח של הדוכנים חלקי k-1. מלבד עותק ממוין, הזיכרון הנדרש הוא O(1).

למה הפרה הראשונה תמיד נכנסת לתא השמאלי ביותר?

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

איך מזהים חיפוש בינארי לפי התשובה?

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

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

stalls = [10, 1, 7, 4, 15]
k = 3

הפלט הצפוי