והפעם נדבר על שאלת 135. LeetCode - Candy הבאה:
יש לנו מספר ילדים כלשהו (N) ויש לנו רשימת ערכים (חיוביים), שכל ערך בתוכה מציג את הציון של כל ילד ברשימה. לדוגמא יש לנו 3 ילדים (N=3) ויש לנו רשימה שנראית כך [1,0,2] שאומרת ש: ילד 1 הציון שלו הוא 1. ילד 2 הציון שלו הוא 0. ילד 3 הציון שלו הוא 2.
עכשיו, עלינו לחלק סוכריות לילדים האלו, ע"פ החוקים הבאים:
חוק 1 - כל ילד צריך לקבל לפחות סוכריה 1.
חוק 2 - כל ילד עם ציון יותר גבוה, צריך לקבל יותר סוכריות מאשר כל ילד שצמוד אליו.
והחידה היא, מהו מספר הסוכריות המינימאלי והקטן ביותר שצריך לתת לילדים האלו? כדי ליישם את 2 החוקים הקודמים.
וכמובן שעלינו למצוא נוסחה כללית שתתאים באופן כללי לכל סוגי המקרים האפשריים.
אז איך ניגשים לשאלה הזאת ואיך אפשרי לנסות לחלק אותה לחלקים יותר קטנים. אז קודם כל ננסה להבין אותה יותר טוב. בעצם נותנים לנו רשימה של ילדים ולכל ילד נותנים ציון כלשהו. ואנחנו צריכים לחלק סוכריות לילדים לפי הציון שלהם ולפי 2 חוקים כלשהם. כאשר אנחנו אמורים לנסות לתת כמה שפחות סוכריות לילדים.
עכשיו, אם נתבונן בשאלה נבין, שכמות הסוכריות שאנחנו צריכים לחלק לילדים, תלויה אך ורק בציון שלהם ולא בשום דבר אחר. שזה בעצם אומר, שאת הסוכריות אנחנו כאילו מחלקים לציונים ולא לילדים. שזה בעצם אומר, שאנחנו יכולים להתעלם מכך שיש בכלל ילדים ואנחנו יכולים לנסח את השאלה ולהבין אותה בצורה יותר פשוטה ושונה, כדלקמן:
"יש לנו רשימת מספרים כלשהי ועלינו לשים על כל מספר X כלשהו של סוכריות, בהתאם ל 2 חוקים. מהו המספר המינימאלי של סוכריות שצריך לשים על רשימת המספרים". ובעצם ככה אנחנו יכולים לנסח ולהבין את השאלה בצורה יותר פשוטה.
עכשיו ננסה להבין את 2 החוקים של חלוקת הסוכריות.
חוק 1 אומר, שלכל מספר, צריך לתת לפחות סוכריה 1.
חוק 2 אומר, שכל מי שהמספר שלו יותר גבוה, מקבל יותר סוכריות ממי שנמצא לידו.
וצריך לשים לב, שאם מישהו עומד ליד מישהו שיש לו ערך זהה, לגביו אין את האילוץ שהוא יקבל יותר סוכריות ממי שעומד לידו (כמו שניתן לראות בדוגמא ה 2 שהם הביאו באתר שלהם, במקרה של [1,2,2] ). דהיינו, יכול להיות שכמה ילדים עם אותו הציון, יקבלו מספר שונה של סוכריות, בהתאם למי שהם עומדים לידו.
אז איך בעצם ניגשים לפתור את השאלה הזאת?
אז בעצם יש לנו כאן 2 תהליכים. תהליך 1 הוא לחשב מה מינימום הסוכריות שצריך לקבל כל ילד. תהליך 2 הוא לחשב כמה סה"כ סוכריות קיבלו כל הילדים.
וכמובן שניתן להבין שתהליך החישוב של מה מינימום הסוכריות שצריך לקבל כל ילד שנמצא ברשימה, הוא התהליך הראשון ובמקרה הוא גם התהליך הקשה יותר בחישובים, ולכן נתחיל ממנו.
אז איך נדע כמה מינימום סוכריות צריך לקבל כל ילד שנמצא ברשימה?
אז ננסה לחלק את זה לחלקים. במקום לשאול את השאלה של "כמה מינימום סוכריות צריך לקבל כל ילד שנמצא ברשימה?" במקום זה ננסה לשאול בצורה יותר פשוטה, "כמה מינימום סוכריות צריך לקבל ילד 1 מסוים שעומד ברשימה?"
ולכאורה זה אולי נראה אותה השאלה, ואפילו אפשרי לומר שזאת כמעט אותה השאלה. אבל באמת אלו 2 צורות שונות לפקס את המוח. ובמקום לחשוב על: איך אני מוצא כמה סוכריות צריך לקבל כל ילד, צריך לחשוב על: איך אני מוצא כמה סוכריות צריך לקבל הילד ה X ברשימה. דהיינו, לנסות לחשוב רק על ילד 1 בלבד.
עכשיו ננסה להפוך את השאלה הזאת לעוד יותר פשוטה וקלה. ולצורך העניין ננסה לחשוב על הילד הראשון שעומד בשורה.
אז נניח שיש לנו את השורה הבאה
אבל מה יקרה אם לדוגמא הילד הראשון ברשימה יהיה לו ציון אחר, לדוגמא רשימה כזאת
אז כאשר אנחנו מנתחים את הדרך לפתור את השאלה הזאת, עלינו לשאול את השאלה הבאה
והיא: מה בטוח נכון, האם יש משהו שהוא בטוח נכון? מהו המקרה הקטן שהוא בטוח נכון? האם יש משהו אפילו הכי קטן? שהוא בטוח נכון? דהיינו, לחפש נקודת וודאות בתוך כל הבלאגן הזה...
ומי שיתבונן יראה, כי בעצם ממה נובע הקושי לגשת לתשובה, זה בגלל שכל מספר הציון שלו, הוא מושפע מהציון של מי שלידו. ולכן קשה להבין כמה סוכריות מקבל כל ילד.
אבל האם זאת כל האמת? האם באמת אין בכל הבלאגן הזה משהו שהוא בטוח נכון? והתשובה היא שיש.
והמקרה הפשוט ביותר, הוא המקרה שבו כמות הסוכריות שנותנים לילד, לא תלויה בדירוג של הילד שלידו. שזהו בעצם המקרה הפשוט ביותר. אבל האם באמת יש מקרה כזה? והתשובה היא שכן.
דהיינו, כל ילד שהדירוג שלו לא יותר גדול מאשר של הילד שלידו, הרי שאותו הילד אמור לקבל סוכריה 1 ולא יותר. כי עליו חל חוק 1 ולא חוק 2. כי חוק 2 אומר שכל ילד שהדירוג שלו גדול משל הילד שלידו, הוא צריך לקבל יותר סוכריות מאשר הילד שלידו, אבל אם הדירוג של הילד, הוא קטן או זהה לכל הילדים שלידו, הרי שהוא צריך לקבל סוכריה 1 בלבד.
וזה בעצם אומר, שבשלב הראשון, אנחנו נעבור על הרשימה וכל ילד שנמצא ברשימה שהדירוג שלו לא יותר גדול (דהיינו קטן או זהה) לדירוג של הילד שלידו, אנחנו ניתן לו סוכריה 1. כי זה בטוח נכון ואין שום אפשרות אחרת.
לדוגמא ברשימה [5,4,3,2,3,4,5] הילד שיש לו את הערך 2, הוא בטוח צריך לקבל סוכריה 1 בלבד. כי הוא לא יותר גדול מ 2 הילדים שלידו. וכל ילד צריך לקבל לפחות סוכריה 1. ולכן הוא צריך לקבל סוכריה 1.
או לדוגמא ברשימה הזאת:
[7,6,6,5,4,0,1,2,3,2]
![]()
שמעכשיו נייצג אותה כך:
מקום 01 [דירוג 7 = כמות? ]
מקום 02 [דירוג 6 = כמות? ]
מקום 03 [דירוג 6 = כמות? ]
מקום 04 [דירוג 5 = כמות? ]
מקום 05 [דירוג 4 = כמות? ]
מקום 06 [דירוג 0 = כמות? ]
מקום 07 [דירוג 1 = כמות? ]
מקום 08 [דירוג 2 = כמות? ]
מקום 09 [דירוג 3 = כמות? ]
מקום 10 [דירוג 2 = כמות? ]
הילד במקום השני, שיש לו את הדירוג 6, הוא בטוח צריך לקבל 1. כי הוא לא יותר גדול משום מספר אחר שעומד לידו. כי הוא יותר קטן מ 7 + הוא זהה ל 6 שאלו המספרים שעומדים לידו.
כמו כן גם הילד במקום השישי שיש לו דירוג 0 וגם הילד במקום העשירי שיש לו את הדירוג 2 גם שניהם בטוח צריכים לקבל כמות של סוכריה 1, כי הם לא יותר גדולים משום דירוג אחר שעומד לידם.
ועכשיו הרשימה שלנו תיראה כך:
![]()
מקום 01 [דירוג 7 = כמות? ]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות? ]
מקום 04 [דירוג 5 = כמות? ]
מקום 05 [דירוג 4 = כמות? ]
מקום 06 [דירוג 0 = כמות 1]
מקום 07 [דירוג 1 = כמות? ]
מקום 08 [דירוג 2 = כמות? ]
מקום 09 [דירוג 3 = כמות? ]
מקום 10 [דירוג 2 = כמות 1]
אז בעצם בשיטה הזאת, מצאנו משהו שהוא בטוח נכון, דהיינו, את כל הילדים שצריכים לקבל כמות וודאיות של סוכריה 1 בלבד.
ועכשיו בשיטה דומה לזאת, נחפש משהו שהוא בטוח נכון, ונגלה שהחוק הוא, שכל מי שנמצא ליד מקום שיש לו כמות וודאית של סוכריות דהיינו, של 1 ושהוא לא יותר גדול ממישהו אחר שעומד לידו ושעדיין לא קיבל סוכריות, הרי שהוא צריך לקבל כמות וודאית של 2 סוכריות, דהיינו, כמות גדולה ב 1 יותר מהכמות שלידו.
וכך נקבל את התוצאה הבאה:
![]()
מקום 01 [דירוג 7 = כמות 2]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות? ]
מקום 04 [דירוג 5 = כמות? ]
מקום 05 [דירוג 4 = כמות 2]
מקום 06 [דירוג 0 = כמות 1]
מקום 07 [דירוג 1 = כמות 2]
מקום 08 [דירוג 2 = כמות? ]
מקום 09 [דירוג 3 = כמות? ]
מקום 10 [דירוג 2 = כמות 1]
בגלל ש:
מקום 1 - מקבל 2 סוכריות, כי הוא ליד כמות וודאית של 1 סוכריות (ולכן הוא מקבל כמות גדולה ב 1) + הוא לא יותר גדול ממשהו אחר שעומד לידו שעדיין לא ידועה הכמות שלו.
מקום 3 - אומנם הוא ליד מקום שקיבל בוודאות 1 סוכריות, אבל הוא גדול ממקום אחר שעדיין לא קיבל סוכריות והוא יכול להיות מושפע ממנו בהמשך.
מקום 4 - לא נמצא ליד מישהו שקיבל מספר וודאי של סוכריות.
מקום 5 - מקבל 2 סוכריות, כי הוא ליד כמות וודאית של 1 סוכריות (ולכן הוא מקבל כמות גדולה ב 1) + הוא לא יותר גדול ממשהו אחר שעומד לידו שעדיין לא ידועה הכמות שלו.
מקום 7 - מקבל 2 סוכריות, כי הוא ליד כמות וודאית של 1 סוכריות (ולכן הוא מקבל כמות גדולה ב 1) + הוא לא יותר גדול ממשהו אחר שעומד לידו שעדיין לא ידועה הכמות שלו.
מקום 8 - לא נמצא ליד מישהו שקיבל מספר וודאי של סוכריות.
מקום 9 - אומנם הוא ליד מקום שקיבל בוודאות 1 סוכריות, אבל הוא גדול ממקום אחר שעדיין לא קיבל סוכריות והוא יכול להיות מושפע ממנו בהמשך.
ועכשיו נחזור שוב על התהליך ונחפש נקודת וודאות נוספת ונגלה שהחוק בנוסחה היותר כללית שלו הוא, שכל מי שנמצא ליד מקום שיש לו כמות וודאית של סוכריות + שהוא לא יותר גדול ממישהו אחר שעומד לידו ושעדיין לא קיבל סוכריות, הרי שהוא צריך לקבל בוודאות כמות שגדולה ב 1 סוכריות יותר מהכמות הכי גדולה שיש לידו.
דהיינו, אם לדוגמא הוא בין כמות וודאית של 1 לבין כמות וודאית של 2, אז הוא יקבל את הערך 3 וכן הלאה.
ובדרך הזאת בעצם נקבל את התוצאה הבאה:
![]()
מקום 01 [דירוג 7 = כמות 2]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות? ]
מקום 04 [דירוג 5 = כמות 3]
מקום 05 [דירוג 4 = כמות 2]
מקום 06 [דירוג 0 = כמות 1]
מקום 07 [דירוג 1 = כמות 2]
מקום 08 [דירוג 2 = כמות 3]
מקום 09 [דירוג 3 = כמות 4]
מקום 10 [דירוג 2 = כמות 1]
בגלל ש:
מקום 3 - אומנם הוא ליד מקום שקיבל בוודאות 1 סוכריות, אבל הוא גדול ממקום אחר שעדיין לא קיבל סוכריות והוא יכול להיות מושפע ממנו בהמשך.
מקום 4 - מקבל 3 סוכריות, כי הוא ליד כמות וודאית של 2 סוכריות (ולכן הוא מקבל כמות גדולה ב 1) + הוא לא יותר גדול ממשהו אחר שעומד לידו שעדיין לא ידועה הכמות שלו.
מקום 8 - מקבל 3 סוכריות, כי הוא ליד כמות וודאית של 2 סוכריות (ולכן הוא מקבל כמות גדולה ב 1) + הוא לא יותר גדול ממשהו אחר שעומד לידו שעדיין לא ידועה הכמות שלו.
מקום 9 - מקבל 4 סוכריות, כי הוא ליד כמות וודאית של 3 סוכריות + וגם ליד כמות וודאית של 1 סוכריות. והוא חייב להיות יותר גדול מהכמות הכי גדולה שלידו, ולכן הוא יקבל 4.
דהיינו, נשים לב, כי מקום 9, הוא תחום ב דירוג 2 לפניו ואחריו. אבל ה 2 שאחריו קיבל 1 סוכריות ו ה 2 שלפניו קיבל 3 סוכריות. ולכן עד שלא היתה לנו וודאות לגבי כל הערכים שקטנים מהמקום ה 9, לא יכולנו לפתור אותו.
ואם נמשיך כך, אז קיבלנו את הרשימה הבאה:
![]()
מקום 01 [דירוג 7 = כמות 2]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות 4]
מקום 04 [דירוג 5 = כמות 3]
מקום 05 [דירוג 4 = כמות 2]
מקום 06 [דירוג 0 = כמות 1]
מקום 07 [דירוג 1 = כמות 2]
מקום 08 [דירוג 2 = כמות 3]
מקום 09 [דירוג 3 = כמות 4]
מקום 10 [דירוג 2 = כמות 1]
בגלל ש:
מקום 3 - מקבל 4 סוכריות, כי הוא ליד כמות וודאית של 3 סוכריות + וגם ליד כמות וודאית של 1 סוכריות. והוא חייב להיות יותר גדול מהכמות הכי גדולה שלידו, ולכן הוא יקבל 4. כמו שהיה לנו קודם עם מקום 9.
אז האם הצלחנו לפתור את התרגיל לפי הנוסחה האחרונה? כן. האם זה יעבוד במאה אחוז מהמקרים? כן.
אז מהי הנוסחה? הנוסחה היא, קודם כל לבדוק מה בטוח נכון, ומשם להתקדם צעד אחרי צעד.
אבל האם זאת הדרך היעילה ביותר?
אז יש לנו דרך יותר יעילה והיא בדרך הבאה, שהיא שיפור של הדרך הקודמת.
והדרך היא, שנחפש מה בטוח נכון, דהיינו, נתחיל לחפש את המקום הראשון שצריך לשים בו את הערך 1, דהיינו, מקום 2 כך:
![]()
מקום 01 [דירוג 7 = כמות? ]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות? ]
מקום 04 [דירוג 5 = כמות? ]
מקום 05 [דירוג 4 = כמות? ]
מקום 06 [דירוג 0 = כמות? ]
מקום 07 [דירוג 1 = כמות? ]
מקום 08 [דירוג 2 = כמות? ]
מקום 09 [דירוג 3 = כמות? ]
מקום 10 [דירוג 2 = כמות? ]
ועכשיו באופן מיידי ננסה להבין לגבי כל המקומות שמצד שמאל שלו או מצד ימין שלו, האם כבר אפשרי מיד לדעת בוודאות משהו לגביהם.
דהיינו? בכל פעם שנגיע לוודאות לגבי כמות במקום כלשהו, כבר נוכל לנסות לאתר וודאות מיידית אפשרית שנובעת ממנה.
ואז נראה כי במקום 1 יש לנו וודאות לגבי הכמות 2 - כי זה ליד 1 ולא יותר גדול ממקום אחר ואז קיבלנו את זה:
![]()
מקום 01 [דירוג 7 = כמות 2]
מקום 02 [דירוג 6 = כמות 1]
ואז נמשיך למקום 3 ונראה שאין בו וודאות כי הוא יותר גדול ממקום 4.
מקום 03 [דירוג 6 = כמות? ]
מקום 04 [דירוג 5 = כמות? ]
מקום 05 [דירוג 4 = כמות? ]
ואז נחזור לחפש את נקודת הוודאות הקודמת שהיא המקום ה 6 ונציב בה 1
![]()
מקום 06 [דירוג 0 = כמות 1]
ואז אם נחזור שמאלה נוכל להציב בוודאות במקום 5 כמות של 2. ואז בוודאות במקום 4 כמות של 3. ואז במקום 3 בוודאות כמות של 4.
![]()
![]()
![]()
ועכשיו הרשימה כבר נראית כך:
מקום 01 [דירוג 7 = כמות 2]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות 4]
מקום 04 [דירוג 5 = כמות 3]
מקום 05 [דירוג 4 = כמות 2]
מקום 06 [דירוג 0 = כמות 1]
מקום 07 [דירוג 1 = כמות? ]
מקום 08 [דירוג 2 = כמות? ]
מקום 09 [דירוג 3 = כמות? ]
מקום 10 [דירוג 2 = כמות? ]
ואז נמשיך במקום ה 7 וננסה להבין את הוודאות שלו, ביחס למקום ה 6 שכבר יש לנו וודאות של כמות 1
ובמקום ה 7 יש לנו וודאות של כמות 2
![]()
מקום 07 [דירוג 1 = כמות 2]
ואז נבדוק וודאות של מקום 8, בגלל הוודאות של מקום 7
ואז נקבל וודאות של כמות 3
![]()
מקום 08 [דירוג 2 = כמות 3]
ואז נבדוק וודאות של מקום 9 ונראה שעדיין אין לנו וודאות, כי מקום 9 אמור להיות מושפע גם ממקום 10, כי הוא גדול גם מ 10.
מקום 09 [דירוג 3 = כמות? ]
ואז שוב נחפש נקודת וודאות ונגיע למקום 10 ונציב בו כמות 1
![]()
מקום 10 [דירוג 2 = כמות 1]
ואז נחזור לנסות לגזור ממנו וודאות לגבי מקום 9 ונציב במקום 9 4, כדי שהוא יהיה גדול מהכמות של מקום 8.
![]()
וכך שוב קיבלנו את הפתרון הקודם שהוא
מקום 01 [דירוג 7 = כמות 2]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות 4]
מקום 04 [דירוג 5 = כמות 3]
מקום 05 [דירוג 4 = כמות 2]
מקום 06 [דירוג 0 = כמות 1]
מקום 07 [דירוג 1 = כמות 2]
מקום 08 [דירוג 2 = כמות 3]
מקום 09 [דירוג 3 = כמות 4]
מקום 10 [דירוג 2 = כמות 1]
ועכשיו נזכיר שיש לנו גם את התהליך השני, שהוא לסכום את כל הכמויות. ואותו אפשרי לעשות בדרך הפשוטה ביותר, אחרי שיודעים את כל הכמויות לסכום את כל הכמויות. או בדרך יעילה יותר, שבכל פעם שיודעים על כמות וודאית כלשהי, אז באותו הרגע כבר מעדכנים ערך מצטבר של חישוב הכמות הוודאית שנקבל בסוף התהליך.
אז מה בעצם היה לנו:
חיפשנו נקודת וודאות בתוך כל האפשרויות. ולכן התחלנו לחפש בהכרח את הדירוג שאמור לקבל כמות של 1. כי זאת הוודאות היחידה האפשרית. וזה אפשרי רק היכן שאין שום מספר שגדול שצמוד למספר הנוכחי.
מכאן בגרסה הראשונה, סיימנו את הסיבוב ועשינו סיבוב נוסף של וודאות וכולי. ובגרסה היותר מתקדמת, בכל פעם שהיתה לנו וודאות, מיד חיפשנו להבין האם ומה הוודאות שניתן להסיק מהוודאות הקודמת. וכך פתרנו את התרגיל בצורה יותר יעילה.
לסיכום: חפש את נקודת הוודאות הקטנה ביותר ומשם תתחיל לפתור את התרגיל בדרך כלשהי, גם אם היא אינה יעילה. אל תחשוב על יעילות אלא על משהו וודאי גם אם הוא אינו יעיל.
מכאן להתקדם לנסות לשפר יעילות וכולי.
בהצלחה.
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Example 1:
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
אז קודם כל נסביר את השאלה.You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Example 1:
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
יש לנו מספר ילדים כלשהו (N) ויש לנו רשימת ערכים (חיוביים), שכל ערך בתוכה מציג את הציון של כל ילד ברשימה. לדוגמא יש לנו 3 ילדים (N=3) ויש לנו רשימה שנראית כך [1,0,2] שאומרת ש: ילד 1 הציון שלו הוא 1. ילד 2 הציון שלו הוא 0. ילד 3 הציון שלו הוא 2.
עכשיו, עלינו לחלק סוכריות לילדים האלו, ע"פ החוקים הבאים:
חוק 1 - כל ילד צריך לקבל לפחות סוכריה 1.
חוק 2 - כל ילד עם ציון יותר גבוה, צריך לקבל יותר סוכריות מאשר כל ילד שצמוד אליו.
והחידה היא, מהו מספר הסוכריות המינימאלי והקטן ביותר שצריך לתת לילדים האלו? כדי ליישם את 2 החוקים הקודמים.
וכמובן שעלינו למצוא נוסחה כללית שתתאים באופן כללי לכל סוגי המקרים האפשריים.
אז איך ניגשים לשאלה הזאת ואיך אפשרי לנסות לחלק אותה לחלקים יותר קטנים. אז קודם כל ננסה להבין אותה יותר טוב. בעצם נותנים לנו רשימה של ילדים ולכל ילד נותנים ציון כלשהו. ואנחנו צריכים לחלק סוכריות לילדים לפי הציון שלהם ולפי 2 חוקים כלשהם. כאשר אנחנו אמורים לנסות לתת כמה שפחות סוכריות לילדים.
עכשיו, אם נתבונן בשאלה נבין, שכמות הסוכריות שאנחנו צריכים לחלק לילדים, תלויה אך ורק בציון שלהם ולא בשום דבר אחר. שזה בעצם אומר, שאת הסוכריות אנחנו כאילו מחלקים לציונים ולא לילדים. שזה בעצם אומר, שאנחנו יכולים להתעלם מכך שיש בכלל ילדים ואנחנו יכולים לנסח את השאלה ולהבין אותה בצורה יותר פשוטה ושונה, כדלקמן:
"יש לנו רשימת מספרים כלשהי ועלינו לשים על כל מספר X כלשהו של סוכריות, בהתאם ל 2 חוקים. מהו המספר המינימאלי של סוכריות שצריך לשים על רשימת המספרים". ובעצם ככה אנחנו יכולים לנסח ולהבין את השאלה בצורה יותר פשוטה.
עכשיו ננסה להבין את 2 החוקים של חלוקת הסוכריות.
חוק 1 אומר, שלכל מספר, צריך לתת לפחות סוכריה 1.
חוק 2 אומר, שכל מי שהמספר שלו יותר גבוה, מקבל יותר סוכריות ממי שנמצא לידו.
וצריך לשים לב, שאם מישהו עומד ליד מישהו שיש לו ערך זהה, לגביו אין את האילוץ שהוא יקבל יותר סוכריות ממי שעומד לידו (כמו שניתן לראות בדוגמא ה 2 שהם הביאו באתר שלהם, במקרה של [1,2,2] ). דהיינו, יכול להיות שכמה ילדים עם אותו הציון, יקבלו מספר שונה של סוכריות, בהתאם למי שהם עומדים לידו.
אז איך בעצם ניגשים לפתור את השאלה הזאת?
אז בעצם יש לנו כאן 2 תהליכים. תהליך 1 הוא לחשב מה מינימום הסוכריות שצריך לקבל כל ילד. תהליך 2 הוא לחשב כמה סה"כ סוכריות קיבלו כל הילדים.
וכמובן שניתן להבין שתהליך החישוב של מה מינימום הסוכריות שצריך לקבל כל ילד שנמצא ברשימה, הוא התהליך הראשון ובמקרה הוא גם התהליך הקשה יותר בחישובים, ולכן נתחיל ממנו.
אז איך נדע כמה מינימום סוכריות צריך לקבל כל ילד שנמצא ברשימה?
אז ננסה לחלק את זה לחלקים. במקום לשאול את השאלה של "כמה מינימום סוכריות צריך לקבל כל ילד שנמצא ברשימה?" במקום זה ננסה לשאול בצורה יותר פשוטה, "כמה מינימום סוכריות צריך לקבל ילד 1 מסוים שעומד ברשימה?"
ולכאורה זה אולי נראה אותה השאלה, ואפילו אפשרי לומר שזאת כמעט אותה השאלה. אבל באמת אלו 2 צורות שונות לפקס את המוח. ובמקום לחשוב על: איך אני מוצא כמה סוכריות צריך לקבל כל ילד, צריך לחשוב על: איך אני מוצא כמה סוכריות צריך לקבל הילד ה X ברשימה. דהיינו, לנסות לחשוב רק על ילד 1 בלבד.
עכשיו ננסה להפוך את השאלה הזאת לעוד יותר פשוטה וקלה. ולצורך העניין ננסה לחשוב על הילד הראשון שעומד בשורה.
אז נניח שיש לנו את השורה הבאה
[0,1,2,3,4,5,6,7]
דהיינו, שהילד הראשון הערך שלו הוא 0. אז כמה סוכריות הוא צריך לקבל הכי פחות? תשובה: 1. כי הוא יכול לקבל את המינימום ההכרחי של סוכריות. ואין לו ציון יותר גבוה משום ילד אחר ברשימה. האם זאת האמת? כן. האם זאת תמיד האמת? כן. האם אין אפשרות שבמקרה כלשהו הוא יצטרך לקבל יותר מ 1? כן, אין אפשרות כזו.אבל מה יקרה אם לדוגמא הילד הראשון ברשימה יהיה לו ציון אחר, לדוגמא רשימה כזאת
[73, 51, 89, 42, 67, 28, 15, 64, 37, 20, 56, 84, 93, 78, 49, 30, 12, 76, 98, 13, 61]
דהיינו, שהציון של הילד הראשון הוא 73. כמה סוכריות צריך לקבל הילד הראשון? איך מחשבים את זה? איך ניגשים לזה?אז כאשר אנחנו מנתחים את הדרך לפתור את השאלה הזאת, עלינו לשאול את השאלה הבאה
והיא: מה בטוח נכון, האם יש משהו שהוא בטוח נכון? מהו המקרה הקטן שהוא בטוח נכון? האם יש משהו אפילו הכי קטן? שהוא בטוח נכון? דהיינו, לחפש נקודת וודאות בתוך כל הבלאגן הזה...
ומי שיתבונן יראה, כי בעצם ממה נובע הקושי לגשת לתשובה, זה בגלל שכל מספר הציון שלו, הוא מושפע מהציון של מי שלידו. ולכן קשה להבין כמה סוכריות מקבל כל ילד.
אבל האם זאת כל האמת? האם באמת אין בכל הבלאגן הזה משהו שהוא בטוח נכון? והתשובה היא שיש.
והמקרה הפשוט ביותר, הוא המקרה שבו כמות הסוכריות שנותנים לילד, לא תלויה בדירוג של הילד שלידו. שזהו בעצם המקרה הפשוט ביותר. אבל האם באמת יש מקרה כזה? והתשובה היא שכן.
דהיינו, כל ילד שהדירוג שלו לא יותר גדול מאשר של הילד שלידו, הרי שאותו הילד אמור לקבל סוכריה 1 ולא יותר. כי עליו חל חוק 1 ולא חוק 2. כי חוק 2 אומר שכל ילד שהדירוג שלו גדול משל הילד שלידו, הוא צריך לקבל יותר סוכריות מאשר הילד שלידו, אבל אם הדירוג של הילד, הוא קטן או זהה לכל הילדים שלידו, הרי שהוא צריך לקבל סוכריה 1 בלבד.
וזה בעצם אומר, שבשלב הראשון, אנחנו נעבור על הרשימה וכל ילד שנמצא ברשימה שהדירוג שלו לא יותר גדול (דהיינו קטן או זהה) לדירוג של הילד שלידו, אנחנו ניתן לו סוכריה 1. כי זה בטוח נכון ואין שום אפשרות אחרת.
לדוגמא ברשימה [5,4,3,2,3,4,5] הילד שיש לו את הערך 2, הוא בטוח צריך לקבל סוכריה 1 בלבד. כי הוא לא יותר גדול מ 2 הילדים שלידו. וכל ילד צריך לקבל לפחות סוכריה 1. ולכן הוא צריך לקבל סוכריה 1.
או לדוגמא ברשימה הזאת:
[7,6,6,5,4,0,1,2,3,2]
שמעכשיו נייצג אותה כך:
מקום 01 [דירוג 7 = כמות? ]
מקום 02 [דירוג 6 = כמות? ]
מקום 03 [דירוג 6 = כמות? ]
מקום 04 [דירוג 5 = כמות? ]
מקום 05 [דירוג 4 = כמות? ]
מקום 06 [דירוג 0 = כמות? ]
מקום 07 [דירוג 1 = כמות? ]
מקום 08 [דירוג 2 = כמות? ]
מקום 09 [דירוג 3 = כמות? ]
מקום 10 [דירוג 2 = כמות? ]
הילד במקום השני, שיש לו את הדירוג 6, הוא בטוח צריך לקבל 1. כי הוא לא יותר גדול משום מספר אחר שעומד לידו. כי הוא יותר קטן מ 7 + הוא זהה ל 6 שאלו המספרים שעומדים לידו.
כמו כן גם הילד במקום השישי שיש לו דירוג 0 וגם הילד במקום העשירי שיש לו את הדירוג 2 גם שניהם בטוח צריכים לקבל כמות של סוכריה 1, כי הם לא יותר גדולים משום דירוג אחר שעומד לידם.
ועכשיו הרשימה שלנו תיראה כך:
מקום 01 [דירוג 7 = כמות? ]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות? ]
מקום 04 [דירוג 5 = כמות? ]
מקום 05 [דירוג 4 = כמות? ]
מקום 06 [דירוג 0 = כמות 1]
מקום 07 [דירוג 1 = כמות? ]
מקום 08 [דירוג 2 = כמות? ]
מקום 09 [דירוג 3 = כמות? ]
מקום 10 [דירוג 2 = כמות 1]
אז בעצם בשיטה הזאת, מצאנו משהו שהוא בטוח נכון, דהיינו, את כל הילדים שצריכים לקבל כמות וודאיות של סוכריה 1 בלבד.
ועכשיו בשיטה דומה לזאת, נחפש משהו שהוא בטוח נכון, ונגלה שהחוק הוא, שכל מי שנמצא ליד מקום שיש לו כמות וודאית של סוכריות דהיינו, של 1 ושהוא לא יותר גדול ממישהו אחר שעומד לידו ושעדיין לא קיבל סוכריות, הרי שהוא צריך לקבל כמות וודאית של 2 סוכריות, דהיינו, כמות גדולה ב 1 יותר מהכמות שלידו.
וכך נקבל את התוצאה הבאה:
מקום 01 [דירוג 7 = כמות 2]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות? ]
מקום 04 [דירוג 5 = כמות? ]
מקום 05 [דירוג 4 = כמות 2]
מקום 06 [דירוג 0 = כמות 1]
מקום 07 [דירוג 1 = כמות 2]
מקום 08 [דירוג 2 = כמות? ]
מקום 09 [דירוג 3 = כמות? ]
מקום 10 [דירוג 2 = כמות 1]
בגלל ש:
מקום 1 - מקבל 2 סוכריות, כי הוא ליד כמות וודאית של 1 סוכריות (ולכן הוא מקבל כמות גדולה ב 1) + הוא לא יותר גדול ממשהו אחר שעומד לידו שעדיין לא ידועה הכמות שלו.
מקום 3 - אומנם הוא ליד מקום שקיבל בוודאות 1 סוכריות, אבל הוא גדול ממקום אחר שעדיין לא קיבל סוכריות והוא יכול להיות מושפע ממנו בהמשך.
מקום 4 - לא נמצא ליד מישהו שקיבל מספר וודאי של סוכריות.
מקום 5 - מקבל 2 סוכריות, כי הוא ליד כמות וודאית של 1 סוכריות (ולכן הוא מקבל כמות גדולה ב 1) + הוא לא יותר גדול ממשהו אחר שעומד לידו שעדיין לא ידועה הכמות שלו.
מקום 7 - מקבל 2 סוכריות, כי הוא ליד כמות וודאית של 1 סוכריות (ולכן הוא מקבל כמות גדולה ב 1) + הוא לא יותר גדול ממשהו אחר שעומד לידו שעדיין לא ידועה הכמות שלו.
מקום 8 - לא נמצא ליד מישהו שקיבל מספר וודאי של סוכריות.
מקום 9 - אומנם הוא ליד מקום שקיבל בוודאות 1 סוכריות, אבל הוא גדול ממקום אחר שעדיין לא קיבל סוכריות והוא יכול להיות מושפע ממנו בהמשך.
ועכשיו נחזור שוב על התהליך ונחפש נקודת וודאות נוספת ונגלה שהחוק בנוסחה היותר כללית שלו הוא, שכל מי שנמצא ליד מקום שיש לו כמות וודאית של סוכריות + שהוא לא יותר גדול ממישהו אחר שעומד לידו ושעדיין לא קיבל סוכריות, הרי שהוא צריך לקבל בוודאות כמות שגדולה ב 1 סוכריות יותר מהכמות הכי גדולה שיש לידו.
דהיינו, אם לדוגמא הוא בין כמות וודאית של 1 לבין כמות וודאית של 2, אז הוא יקבל את הערך 3 וכן הלאה.
ובדרך הזאת בעצם נקבל את התוצאה הבאה:
מקום 01 [דירוג 7 = כמות 2]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות? ]
מקום 04 [דירוג 5 = כמות 3]
מקום 05 [דירוג 4 = כמות 2]
מקום 06 [דירוג 0 = כמות 1]
מקום 07 [דירוג 1 = כמות 2]
מקום 08 [דירוג 2 = כמות 3]
מקום 09 [דירוג 3 = כמות 4]
מקום 10 [דירוג 2 = כמות 1]
בגלל ש:
מקום 3 - אומנם הוא ליד מקום שקיבל בוודאות 1 סוכריות, אבל הוא גדול ממקום אחר שעדיין לא קיבל סוכריות והוא יכול להיות מושפע ממנו בהמשך.
מקום 4 - מקבל 3 סוכריות, כי הוא ליד כמות וודאית של 2 סוכריות (ולכן הוא מקבל כמות גדולה ב 1) + הוא לא יותר גדול ממשהו אחר שעומד לידו שעדיין לא ידועה הכמות שלו.
מקום 8 - מקבל 3 סוכריות, כי הוא ליד כמות וודאית של 2 סוכריות (ולכן הוא מקבל כמות גדולה ב 1) + הוא לא יותר גדול ממשהו אחר שעומד לידו שעדיין לא ידועה הכמות שלו.
מקום 9 - מקבל 4 סוכריות, כי הוא ליד כמות וודאית של 3 סוכריות + וגם ליד כמות וודאית של 1 סוכריות. והוא חייב להיות יותר גדול מהכמות הכי גדולה שלידו, ולכן הוא יקבל 4.
דהיינו, נשים לב, כי מקום 9, הוא תחום ב דירוג 2 לפניו ואחריו. אבל ה 2 שאחריו קיבל 1 סוכריות ו ה 2 שלפניו קיבל 3 סוכריות. ולכן עד שלא היתה לנו וודאות לגבי כל הערכים שקטנים מהמקום ה 9, לא יכולנו לפתור אותו.
ואם נמשיך כך, אז קיבלנו את הרשימה הבאה:
מקום 01 [דירוג 7 = כמות 2]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות 4]
מקום 04 [דירוג 5 = כמות 3]
מקום 05 [דירוג 4 = כמות 2]
מקום 06 [דירוג 0 = כמות 1]
מקום 07 [דירוג 1 = כמות 2]
מקום 08 [דירוג 2 = כמות 3]
מקום 09 [דירוג 3 = כמות 4]
מקום 10 [דירוג 2 = כמות 1]
בגלל ש:
מקום 3 - מקבל 4 סוכריות, כי הוא ליד כמות וודאית של 3 סוכריות + וגם ליד כמות וודאית של 1 סוכריות. והוא חייב להיות יותר גדול מהכמות הכי גדולה שלידו, ולכן הוא יקבל 4. כמו שהיה לנו קודם עם מקום 9.
אז האם הצלחנו לפתור את התרגיל לפי הנוסחה האחרונה? כן. האם זה יעבוד במאה אחוז מהמקרים? כן.
אז מהי הנוסחה? הנוסחה היא, קודם כל לבדוק מה בטוח נכון, ומשם להתקדם צעד אחרי צעד.
אבל האם זאת הדרך היעילה ביותר?
אז יש לנו דרך יותר יעילה והיא בדרך הבאה, שהיא שיפור של הדרך הקודמת.
והדרך היא, שנחפש מה בטוח נכון, דהיינו, נתחיל לחפש את המקום הראשון שצריך לשים בו את הערך 1, דהיינו, מקום 2 כך:
מקום 01 [דירוג 7 = כמות? ]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות? ]
מקום 04 [דירוג 5 = כמות? ]
מקום 05 [דירוג 4 = כמות? ]
מקום 06 [דירוג 0 = כמות? ]
מקום 07 [דירוג 1 = כמות? ]
מקום 08 [דירוג 2 = כמות? ]
מקום 09 [דירוג 3 = כמות? ]
מקום 10 [דירוג 2 = כמות? ]
ועכשיו באופן מיידי ננסה להבין לגבי כל המקומות שמצד שמאל שלו או מצד ימין שלו, האם כבר אפשרי מיד לדעת בוודאות משהו לגביהם.
דהיינו? בכל פעם שנגיע לוודאות לגבי כמות במקום כלשהו, כבר נוכל לנסות לאתר וודאות מיידית אפשרית שנובעת ממנה.
ואז נראה כי במקום 1 יש לנו וודאות לגבי הכמות 2 - כי זה ליד 1 ולא יותר גדול ממקום אחר ואז קיבלנו את זה:
מקום 01 [דירוג 7 = כמות 2]
מקום 02 [דירוג 6 = כמות 1]
ואז נמשיך למקום 3 ונראה שאין בו וודאות כי הוא יותר גדול ממקום 4.
מקום 03 [דירוג 6 = כמות? ]
מקום 04 [דירוג 5 = כמות? ]
מקום 05 [דירוג 4 = כמות? ]
ואז נחזור לחפש את נקודת הוודאות הקודמת שהיא המקום ה 6 ונציב בה 1
מקום 06 [דירוג 0 = כמות 1]
ואז אם נחזור שמאלה נוכל להציב בוודאות במקום 5 כמות של 2. ואז בוודאות במקום 4 כמות של 3. ואז במקום 3 בוודאות כמות של 4.
ועכשיו הרשימה כבר נראית כך:
מקום 01 [דירוג 7 = כמות 2]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות 4]
מקום 04 [דירוג 5 = כמות 3]
מקום 05 [דירוג 4 = כמות 2]
מקום 06 [דירוג 0 = כמות 1]
מקום 07 [דירוג 1 = כמות? ]
מקום 08 [דירוג 2 = כמות? ]
מקום 09 [דירוג 3 = כמות? ]
מקום 10 [דירוג 2 = כמות? ]
ואז נמשיך במקום ה 7 וננסה להבין את הוודאות שלו, ביחס למקום ה 6 שכבר יש לנו וודאות של כמות 1
ובמקום ה 7 יש לנו וודאות של כמות 2
מקום 07 [דירוג 1 = כמות 2]
ואז נבדוק וודאות של מקום 8, בגלל הוודאות של מקום 7
ואז נקבל וודאות של כמות 3
מקום 08 [דירוג 2 = כמות 3]
ואז נבדוק וודאות של מקום 9 ונראה שעדיין אין לנו וודאות, כי מקום 9 אמור להיות מושפע גם ממקום 10, כי הוא גדול גם מ 10.
מקום 09 [דירוג 3 = כמות? ]
ואז שוב נחפש נקודת וודאות ונגיע למקום 10 ונציב בו כמות 1
מקום 10 [דירוג 2 = כמות 1]
ואז נחזור לנסות לגזור ממנו וודאות לגבי מקום 9 ונציב במקום 9 4, כדי שהוא יהיה גדול מהכמות של מקום 8.
וכך שוב קיבלנו את הפתרון הקודם שהוא
מקום 01 [דירוג 7 = כמות 2]
מקום 02 [דירוג 6 = כמות 1]
מקום 03 [דירוג 6 = כמות 4]
מקום 04 [דירוג 5 = כמות 3]
מקום 05 [דירוג 4 = כמות 2]
מקום 06 [דירוג 0 = כמות 1]
מקום 07 [דירוג 1 = כמות 2]
מקום 08 [דירוג 2 = כמות 3]
מקום 09 [דירוג 3 = כמות 4]
מקום 10 [דירוג 2 = כמות 1]
ועכשיו נזכיר שיש לנו גם את התהליך השני, שהוא לסכום את כל הכמויות. ואותו אפשרי לעשות בדרך הפשוטה ביותר, אחרי שיודעים את כל הכמויות לסכום את כל הכמויות. או בדרך יעילה יותר, שבכל פעם שיודעים על כמות וודאית כלשהי, אז באותו הרגע כבר מעדכנים ערך מצטבר של חישוב הכמות הוודאית שנקבל בסוף התהליך.
אז מה בעצם היה לנו:
חיפשנו נקודת וודאות בתוך כל האפשרויות. ולכן התחלנו לחפש בהכרח את הדירוג שאמור לקבל כמות של 1. כי זאת הוודאות היחידה האפשרית. וזה אפשרי רק היכן שאין שום מספר שגדול שצמוד למספר הנוכחי.
מכאן בגרסה הראשונה, סיימנו את הסיבוב ועשינו סיבוב נוסף של וודאות וכולי. ובגרסה היותר מתקדמת, בכל פעם שהיתה לנו וודאות, מיד חיפשנו להבין האם ומה הוודאות שניתן להסיק מהוודאות הקודמת. וכך פתרנו את התרגיל בצורה יותר יעילה.
לסיכום: חפש את נקודת הוודאות הקטנה ביותר ומשם תתחיל לפתור את התרגיל בדרך כלשהי, גם אם היא אינה יעילה. אל תחשוב על יעילות אלא על משהו וודאי גם אם הוא אינו יעיל.
מכאן להתקדם לנסות לשפר יעילות וכולי.
בהצלחה.
050-3331-331