נניח שנתונים n כדי מים אדומים ו-n כדי מים כחולים, שכל אחד מהם שונה מן האחרים בצורתו ובגודלו. נתון כי בין הכדים האדומים אין שני כדים בעלי אותה קיבולת, וכך גם בין הכדים הכחולים. וכן נתון כי לכל כד אדום מתאים כד כחול בעל קיבולת זהה (ולהיפך).
עליכם לזווג את הכדים לזוגות של כד אדום וכד כחול שקיבולת המים שלהם זהה. לשם כך אתם רשאים לבצע את הפעולה הבאה: בחרו זוג כדים, אחד אדום ואחד כחול, מלאו את האדום במים ושפכו את המים ממנו אל תוך הכד הכחול. בעזרת פעולה זו תוכלו לברר איזה מן הכדים מכיל יותר מים או לגלות שקיבולתם זהה. הניחו שהשוואה כזו אורכת יחידת זמן אחת.
המטרה שלכם היא למצוא אלגוריתם שמספר ההשוואות שנערכות בו לזיווג כל הכדים הוא מינימלי אסימפטוטית. זכרו, אינכם יכולים להשוות בין שני כדים אדומים או בין שני כדים כחולים באופן ישיר.
קיבולת כד היא מספר ממשי.
א) (13 נק') הציעו אלגוריתם שתוחלת מספר ההשוואות בו היא O(nlogn). מהו סדר הגודל של מספר ההשוואות שעושה האלגוריתם שלכם במקרה הגרוע?
אין צורך לנתח את היעילות באופן מפורט- אלא מספיק לומר לאיזו שגרה מהספר יש ניתוח יעילות דומה ולהסיק מכך על היעילות כאן.
ב) (12 נק') בהינתן שקיבולת הכדים הכחולים מוגבלת ב-m מ"ל, כאשר m=O(n), ואין אף כד עם קיבולת 0.
הציעו מבנה נתונים S שעושה עבודת הכנה ב-O(n), ולאחריה יכול לענות ב-O(1) על השאילתא:
RANGE(S, r1, r2) : בהינתן שני מספרים שלמים r1,r2, בטווח [0…m], מחזיר את מספר הכדים הכחולים עם קיבולת X, כך ש r1<X≤r2.