... הגדלה 1 בלבד, נעשה זאת לדוגמה בדרך הבאה: בנוסף אומרים לנו את הדבר הבא: באפשרותך לבצע פעולה אחת בכל פעם, של הוספת הערך 1, כדי
להגדיל את כל המספרים, לערך הגדול ביותר, דהיינו, לבצע 9 פעולות של הגדלה ב 1, כנל. ... 4 פעמים נעשה הגדלה של שני מספרים שונים בערך 1 ופעם אחת אחרונה, נגדיל רק ערך אחד בלבד, בערך 1, כי כבר אין ערכים נוספים שצריכים
להגדיל. ועד כאן הבנו, שיש לנו רשימת מספרים, שאנחנו צריכים ליישר קו
להגדיל את כל הערכים לערך הגדול ביותר, באמצעות פעולת הוספה של הערך 1 עד שכל ... + מחיר2 כלשהם, לדוגמה מחיר1 הוא 10 ומחיר2 הוא 15, במקרה כזה השאלה היא, מה יהיה המחיר המינימאלי ההכרחי שנהיה חייבים לשלם, כדי
להגדיל את כל המספרים למספר הגדול ביותר? עד כאן הפירוש של השאלה... ועכשיו נצעד אל ... נחזור שוב על השאלה מההתחלה וננסה לחלק את כל התהליך לחלקים הכי קטנים, לדוגמה כך: שואלים אותנו: נותנים לנו רשימת מספרים. עלינו
להגדיל את כל רשימת המספרים, אל המספר הגדול ביותר ברשימה. עלינו לעשות זאת באמצעות ... מיישרים קו של כל המספרים. עכשיו, נניח שהיו אומרים לנו, שלכל פעולת הוספה, יש מחיר1 כלשהו. והיו שואלים אותנו, כמה יעלה לנו
להגדיל את כל המספרים? האם היינו יודעים לפתור את זה? תשובה: כן. היינו פשוט סופרים ... וכולי? אז לכאורה, אכן צריכים לרוץ על הרשימה, פעמיים. פעם ראשונה כדי לאתר את המספר הגדול ביותר. ורק אחר כך לעבור על כל הערכים
להגדיל אותם וכולי. אבל זאת לא כל האמת. כי בפועל, אפשרי לרוץ פעם אחת על כל הרשימה ... O(N). ועכשיו נמשיך לחלק לחלקים ונעבור לחלק קצת יותר קשה של השאלה, והוא, בהינתן רשימה של מספרים כנל, ובהינתן אפשרות אחת ויחידה
להגדיל את המספרים כנל, והיא באמצעות הגדלת 2 מספרים בכל פעם בבת אחת. דהיינו, שאנחנו חייבים
להגדיל בערך 1, אך ורק שני מספרים שונים בבת אחת. האם היינו יודעים לחשב את כמות ... של השאלה, שהיא, שיש לנו עוד חישוב אפשרי, לחשב, במידה ונבצע X הגדלות כפולות, כמה Y הגדלות בודדות נבצע. דהיינו, אם יש לנו צורך
להגדיל את כל המספרים נניח בסכום של 500. אז כעיקרון, במידה ונרצה לבצע כמה שיותר ... לנו מחיר1 שהוא עלות של הגדלה בודדת ובהינתן לנו מחיר2 שהוא עלות של הגדלה כפולה, אז, מה יהיה המחיר המינימאלי שנוכל לשלם, כדי
להגדיל את כל המספרים. ואיך ניגשים לפתור את החלק הזה של השאלה? אז לשם כך לכאורה בעצם עלינו לקחת רשימה, לחשב את כל האפשרויות האפשריות
להגדיל את הרשימה למקסימום. באמצעות כל השילובים של הגדלה בודדת ושל הגדלה כפולה. ומכאן נוכל לדעת, מהו המחיר המינימאלי שעלינו לשלם כדי
להגדיל את הרשימה כולה. אבל זהו כמובן חישוב לא יעיל מבחינת זמן ריצה. ולכן, אם ... משנה איך נבצע את ההגדלות. או במילים אחרות, מכך נוכל להסיק לגבי פתרון השאלה המקורית את הדבר הבא: בהינתן רשימת מספרים, שעלינו
להגדיל אותה למקסימום ב 2 דרכים אפשרויות עם 2 מחירים שונים. אז בשלב הראשון עלינו ... אז איך ניגשים לזה? אז איך ניגשים לזה? אז נתחיל מהמקרה הקל ביותר, נניח שיש לנו את הרשימה הבאה (1,2) דהיינו, שאנחנו צריכים
להגדיל את 1 לערך 2. האם ניתן לבצע זאת בהגדלה כפולה? כמובן שלא. אפשרי לבצע זאת בהגדלה אחת בודדת בלבד. ואם יש לנו את הרשימה (1, 100) דהיינו, שאנחנו צריכים
להגדיל את הערך 1 לערך 100. האם ניתן לעשות זאת בהגדלות כפולות? תשובה: לא. רק ב 99 הגדלות בודדות. או במילים אחרות, בטוח נכון שכאשר צריכים
להגדיל רק עמודה אחת בודדת, הרי שאין אפשרות לבצע הגדלה כפולה. ומה אם יש לנו
להגדיל 2 עמודות, לדוגמה (1, 1, 2), שעלינו
להגדיל את 2 העמודות של ה 1 אל הערך 2. הרי שניתן לבצע כאן הגדלה אחת כפולה שתהפוך ... יש לנו רשימה של (1, 1, 100). במקרה כזה נוכל לבצע 99 הגדלות כפולות, שיביאו את הרשימה ל (100,100,100). ואם לצורך העניין נצטרך
להגדיל 3 עמודות, לדוגמה (1,1,1,2), הרי שבמקרה כזה, נוכל לבצע הגדלה 1 כפולה, ... תהיה כמות ההגדלות הכפולות שניתן לבצע. את השארית, נגדיל בצורה של הגדלה בודדת. ומכך נובע ש, בהינתן עמודות שוות בגובהן, שצריך
להגדיל את כולן באותה כמות הגדלות, אז: אם יש לנו מספר זוגי של עמודות שצריכים
להגדיל, לדוגמה: (1,1,100) (1,1,1,1,100) (1,1,1,1,1,1,100) (1,1,1,1,1,1,1,1,100) ... את סהכ ההגדלות שצריכים לבצע, נחלק ל 2 ונקבל את כמות ההגדלות הכפולות שצריכים לבצע. ואם יש לנו מספר אי זוגי של עמודות שצריכים
להגדיל, לדוגמה: (1,100) (1,1,1,100) (1,1,1,1,1,100) (1,1,1,1,1,1,1,100) אז נצטרך ... שצריך לבצע, היא עצמה זוגית, דהיינו, לדוגמה במקרים הבאים: (2,100) (2,2,2,100) (2,2,2,2,2,100) (2,2,2,2,2,2,2,100) שצריכים
להגדיל את כל המספרים ב 98 שזה מספר זוגי, אז שוב כנל, ניקח את סהכ ההגדלות שצריכים לבצע, לחלק ל 2. וזו תהיה כמות ההגדלות הכפולות שניתן לבצע. אבל אם נצטרך
להגדיל את המספרים בערך אי זוגי וכמות המספרים עצמם שנצטרך
להגדיל תהיה אי זוגית, לדוגמה: (1,100) (1,1,1,100) (1,1,1,1,1,100) (1,1,1,1,1,1,1,100) שיש לנו כמות אי זוגית של עמודות שצריכים
להגדיל + צריכים
להגדיל כל עמודה ב 99, שזה מספר אי זוגי, אז במקרה כזה, ניקח את סהכ הסכום שצריך
להגדיל, נחלק אותו ב 2. וזו תהיה כמות ההגדלות הכפולות שצריכים לבצע. ואחר כך ... אנחנו באים לנתח את כמות ההגדלות הכפולות שאנחנו יכולים לבצע, עלינו לאתר את העמודה עם הערך הקטן ביותר, שאותה אנחנו הכי צריכים
להגדיל. דהיינו, בדיוק כמו שאנחנו מחפשים את הערך MAX שהוא הערך שאליו צריכים