The Celebrity Problem

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

פתרונות האלימינציה רצים בזמן O(n) : ‏ n-1 חיפושים מוצאים את המועמד, ולכל היותר 2(n-1) בדיקות מוודאות זאת. גרסת שני המצביעים משתמשת בזיכרון נוסף של O(1) , וגרסת המחסנית ב- O(n) . בדיקת כל אדם מול ההגדרה עולה O(n²) .

Q: האם יכולה להיות יותר מסלבריטאי אחד?

לא. אם שני אנשים היו ידוענים, כל אחד מהם היה מוכר לכולם, ולכן כל אחד מהם היה מכיר את השני. אבל ידוען לא מכיר אף אחד, ולכן במסיבה יש לכל היותר ידוען אחד.

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

המטריצה היא מטריצת הסמיכויות של גרף מכוון: קשת מ־ i ל־ j פירושה ש־ i מכיר את j . סלבריטאי הוא צומת שדרגת היציאה שלו היא 0 ודרגת הכניסה שלו היא n-1 , כלומר בור אוניברסלי. ספירת הדרגות מצריכה קריאה של כל המטריצה, ואילו שיטת האלימינציה מוצאת את הבור לאחר קריאת O(n) תאים בלבד.

בינונימחסנית שני מצביעים גרפים

+10

יש n אנשים במסיבה, שממוספרים מ־0 עד n-1. ניתנת לך מטריצה בגודל n × n, שבה matrix[i][j] הוא 1 אם אדם i מכיר את אדם j, ו־0 אם לא. היכרות היא חד־כיוונית: ייתכן ש־i מכיר את j, בעוד ש־j אינו מכיר את i.

סלבריטי הוא אדם שכל שאר האנשים מכירים ואינו מכיר אף אחד. החזר את המספר של הסלבריטי, או -1 אם אין סלבריטי.

פונקציה

findCelebrity(matrix: integer-2d-array) → integer

matrixinteger-2d-array: מי מכיר את מי: השורה i, העמודה j היא 1 אם אדם i מכיר את אדם j
מחזירהinteger: המספר של הסלבריטאי, או ‎-1 אם אין כזה

אילוצים

2 ≤ n ≤ 150, כאשר n הוא מספר השורות והעמודות
matrix[i][j] הוא 0 או 1
matrix[i][i] = 0 עבור כל אדם

דוגמאות

קלט: matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
פלט: 1
הסבר: כל הערכים בשורה 1 הם אפסים, ולכן אדם 1 לא מכיר אף אחד. בעמודה 1 יש 1 בשורות 0 ו-2, ולכן שני האנשים האחרים מכירים את אדם 1. אדם 1 הוא הסלבריטאי.

שאלת המשך

נניח שכל חיפוש הוא שאלה שעליך לשאול. כמה שפחות שאלות תצטרך במקרה הגרוע ביותר, והאם תוכל לרדת מתחת ל־3(n-1)?

רמזים

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

נפתחו 0 מתוך 3

פתרון

בדיקת כל אדם מול ההגדרה דורשת בערך 2n² חיפושים. תא אחד matrix[a][b] תמיד שולל אחד מבין a ו־b, ולכן n-1 חיפושים משאירים מועמד יחיד. מעבר אחד על השורה והעמודה של המועמד קובע אז אם הוא הסלבריטאי.

בדוק כל אדם

האינטואיציה

אדם c הוא הידוען כאשר בשורה c אין אף 1 (הוא לא מכיר אף אחד) ובעמודה c יש 1 בכל שורה מלבד השורה שלו (כולם מכירים אותו). בדוק את ההגדרה הזאת עבור כל אדם בתורו והחזר את הראשון שעונה עליה.

בדיקת כל אדם דורשת עד 2(n-1) שליפות, ובסך הכול בערך 2n²: כאשר n = 150, מדובר בכ-45,000 שליפות.

אלגוריתם

עבור כל אדם c מ-0 עד n-1, בדקו כל אדם אחר other.
אם matrix[c][other] הוא 1, או matrix[other][c] הוא 0, c אינו הידוען: עברו לאדם הבא.
אם אף אדם אחר אינו שולל את האפשרות ש-c הוא הידוען, החזירו את c.
אם כל האנשים נכשלים, החזירו -1.

def findCelebrity(matrix):
    n = len(matrix)
    for c in range(n):
        is_celebrity = True
        for other in range(n):
            # c must know no one, and everyone else must know c.
            if other != c and (matrix[c][other] == 1 or matrix[other][c] == 0):
                is_celebrity = False
                break
        if is_celebrity:
            return c
    return -1

פתרון באמצעות מחסנית

האינטואיציה

אם matrix[a][b] הוא 1, אז a מכיר מישהו ולכן אינו יכול להיות הסלבריטי. אם הוא 0, אז a לא מכיר את b, ולכן b אינו יכול להיות הסלבריטי. כך או כך, בדיקה אחת מוציאה אדם אחד מהאפשרויות לצמיתות. שים את כולם בערימה, הוצא ממנה שניים, שאל, והחזר לערימה את מי שעדיין אפשרי: לאחר n-1 סבבים נשאר אדם אחד.

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

אלגוריתם

דחוף כל אדם למחסנית.
כל עוד יש במחסנית יותר מאדם אחד, הוצא ממנה את a ואת b.
אם a מכיר את b, דחוף את b בחזרה; אחרת דחוף את a בחזרה.
קח את האדם האחרון כמועמד. אם הוא מכיר מישהו, או שמישהו אינו מכיר אותו, החזר -1.
אחרת החזר את המועמד.

def findCelebrity(matrix):
    n = len(matrix)
    candidates = list(range(n))
    # Each question removes one person who cannot be the celebrity.
    while len(candidates) > 1:
        a = candidates.pop()
        b = candidates.pop()
        candidates.append(b if matrix[a][b] == 1 else a)
    c = candidates[0]
    # The survivor is only a candidate: check every other person.
    for other in range(n):
        if other != c and (matrix[c][other] == 1 or matrix[other][c] == 0):
            return -1
    return c

שני מצביעים, ואז לאמת

האינטואיציה

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

בדוגמה הראשונה, matrix[0][2] הוא 0, לכן אדם 2 נשלל; לאחר מכן matrix[0][1] הוא 1, לכן אדם 0 נשלל. המצביעים נפגשים באדם 1, שעובר את הבדיקה. מדובר ב־n-1 גישות ועוד לכל היותר 2(n-1), עם שימוש בזיכרון נוסף של שני מספרים שלמים.

אלגוריתם

הגדר את a = 0 ואת b = n-1.
כל עוד a < b: אם matrix[a][b] הוא 1, הוסף 1 ל-a; אחרת, חסר 1 מ-b.
המועמד הוא a. עבור כל אדם אחר, בדוק שהמועמד אינו מכיר אותו ושהוא מכיר את המועמד.
החזר את המועמד אם כל הבדיקות מתקיימות, אחרת החזר -1.

def findCelebrity(matrix):
    n = len(matrix)
    a, b = 0, n - 1
    # Each question rules out one of the two people.
    while a < b:
        if matrix[a][b] == 1:
            a += 1  # a knows someone, so a is not the celebrity
        else:
            b -= 1  # a does not know b, so b is not the celebrity
    # a is the only person left who could be the celebrity: check it.
    for other in range(n):
        if other != a and (matrix[a][other] == 1 or matrix[other][a] == 0):
            return -1
    return a

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

החזרת השורד בלי לבדוק אותו. ב-[[0, 1], [1, 0]] השורד הוא אחד משני אנשים שמכירים זה את זה, והתשובה היא ‎-1.
בדיקת צד אחד בלבד. הדוגמה השלישית נכשלת רק בשורה: כולם מכירים את אדם 2, אבל אדם 2 מכיר את אדם 3.
ספירת האלכסון. matrix[c][c] הוא 0, ולכן בדיקת עמודה שלא מדלגת על other == c פוסלת כל סלבריטאי אמיתי.
קריאה של התא בכיוון ההפוך. matrix[a][b] = 1 פוסלת את a, ולא את b. החלפת התפקידים משמיטה את הסלבריטאי האמיתי.
החזרת אינדקס שמתחיל ב-1 ב-Lua או ב-R. מספרי האנשים מתחילים ב-0, לכן יש להפחית 1 לפני ההחזרה.

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

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

פתרונות האלימינציה רצים בזמן O(n): ‏n-1 חיפושים מוצאים את המועמד, ולכל היותר 2(n-1) בדיקות מוודאות זאת. גרסת שני המצביעים משתמשת בזיכרון נוסף של O(1), וגרסת המחסנית ב-O(n). בדיקת כל אדם מול ההגדרה עולה O(n²).

האם יכולה להיות יותר מסלבריטאי אחד?

לא. אם שני אנשים היו ידוענים, כל אחד מהם היה מוכר לכולם, ולכן כל אחד מהם היה מכיר את השני. אבל ידוען לא מכיר אף אחד, ולכן במסיבה יש לכל היותר ידוען אחד.

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

המטריצה היא מטריצת הסמיכויות של גרף מכוון: קשת מ־i ל־j פירושה ש־i מכיר את j. סלבריטאי הוא צומת שדרגת היציאה שלו היא 0 ודרגת הכניסה שלו היא n-1, כלומר בור אוניברסלי. ספירת הדרגות מצריכה קריאה של כל המטריצה, ואילו שיטת האלימינציה מוצאת את הבור לאחר קריאת O(n) תאים בלבד.

def findCelebrity(matrix):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]

הפלט הצפוי

The Celebrity Problem

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

בדוק כל אדם

פתרון באמצעות מחסנית

שני מצביעים, ואז לאמת

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

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

בעיות דומות