... ARR במקום 0 ובמקום 1 ובמקום 2 וכולי, עד לסוף המערך. ואם הערך 1 לא יכול
להגיע בשום דרך, למיקום X במערך ARR, אז במערך ANS, באותו המיקום שאליו לא יכול
להגיע הערך 1, נכתוב - 1. דהיינו, לכאן לא ניתן להביא את הערך 1. כאשר, כדי לסבך אותנו עוד קצת, נתנו לנו גם רשימה של מקומות בשם Banned שאומרת, שלכאן הערך 1 לא יכול
להגיע בשום שלב. ועכשיו אחרי שהבנו את השאלה, עכשיו כמובן נשאל, איך ניגשים לפתור את השאלה הזאת? אז ננסה להפוך את השאלה הנל לשאלה יותר קלה. ... שם בלי שום פעולת היפוך. ו ANS במיקום 1 יהיה שווה ל - 1, כי הערך 1 לא יכול
להגיע לשם בשום היפוך, כי מקדם ההיפוך הוא 1 בלבד שלא מאפשר להזיז את הערך 1 ממקום למקום. ונעשה עוד בדיקה עם מערך באורך 10, כאשר המיקום ... נגלה, שקודם כל עלינו לסמן את הנקודות הרחוקות ביותר שאליהן בטוח לא ניתן
להגיע בפחות מ X צעדים. בצורה הבאה: זאת אומרת, שאם מציגים לנו את מקרה ש: N=20, P=0, ו K=4. ומבקשים מאיתנו לסמן את מה שבטוח נכון בוודאות, ... הרי שאנחנו נסמן את המקומות הנל. דהיינו, נסמן את המקום הרחוק ביותר שניתן
להגיע אליו בהיפוך 1. דהיינו, נדע בוודאות, שאין שום אפשרות
להגיע יותר רחוק בהיפוך 1. ואת המיקום שהגענו אליו, גם אותו נהפוך בעוד היפוך 1, למיקום הרחוק ביותר שאפשרי
להגיע ב 2 היפוכים וכך הלאה. כי אנחנו יודעים בוודאות, שאין שום אפשרות בעולם
להגיע למיקום 3 בפחות מ 1 היפוכים. ומכך נובע שאין שום אפשרות
להגיע למיקום 6 בפחות מ 2 היפוכים. ומכך נובע שאין שום אפשרות
להגיע למיקום 9 בפחות מ 3 היפוכים וכולי, ואין שום אפשרות
להגיע למיקום 18 בפחות מ 6 היפוכים. ובדוגמה שהבאתי, אנחנו עושים את כל ההיפוכים ימינה. אבל כמובן שצריכים לעשות את זה גם שמאלה, במידה ויש ... למקרה שמביאים לנו. או במילים אחרות, יש מיקומים מסויימים, שאנחנו יכולים
להגיע אליהם בהיפוך 1 או ב 2 היפוכים או 10 היפוכים. והמשימה שלנו היא לדעת מהו המינימום היפוכים האפשרי,
להגיע לכל נקודה. אבל אם מראש נסמן את המיקום הרחוק ביותר ימינה, שניתן
להגיע בהיפוך 1 ימינה, אז משם נוכל לדעת בוודאות, שמכאן ואילך ימינה, אפשרי
להגיע רק ב 2 היפוכים ומעלה. ואחר כך נסמן שוב ימינה את הנקודה הרחוקה ביותר שאפשרי
להגיע אליה עם 2 היפוכים ימינה. ונדע בוודאות, שאין שום אפשרות
להגיע ימינה ממנה, בפחות מ 3 היפוכים וכולי. דהיינו, השלב הראשון בלפתור את התרגיל, הוא לרוץ על המערך ANS החל מנקודת ההתחלה של P לכיוון ... כל לנסות לסמן בתוך ANS את המקומות שבטוח נכונים שאליהם בוודאות לא ניתן
להגיע בפחות מ X דילוגים ימינה או שמאלה. ואם תוך כדי שאנחנו עושים דילוג ימינה, אנחנו מגיעים לתוך מקום שנמצא בו הערך Banned, דהיינו, שלא ניתן
להגיע אליו, אז ניקח מיקום 1 שמאלה דהיינו, K-2 וכולי. ומשם נמשיך לדלג ימינה. ואם גם בו יש Banned אז נחזור עוד צעד אחד אחורה וכולי, עד ... של עוגנים ונקודות של וודאות, שבכל נקודה אנחנו יודעים בוודאות שלא ניתן
להגיע אליה, בפחות היפוכים מהערך שכתוב בה. כי כמו שאמרנו בדוגמה הקודמת, אנחנו יודעים בוודאות, שאין שום אפשרות בעולם
להגיע למיקום 3 בפחות מ 1 היפוכים. ומכך נובע שאין שום אפשרות
להגיע למיקום 6 בפחות מ 2 היפוכים. ומכך נובע שאין שום אפשרות
להגיע למיקום 9 בפחות מ 3 היפוכים וכולי, ואין שום אפשרות
להגיע למיקום 18 בפחות מ 6 היפוכים כנל. ואחרי שפתרנו את כל העוגנים הראשונים של הוודאות, הרי שבעצם עכשיו השאלה הפכה להיות הרבה יותר קלה. ... העניין על מיקום 19 או 20, אנחנו לא צריכים לנסות להבין בכמה היפוכים ניתן
להגיע אליהם ממיקום P=0. אלא אנחנו צריכים לנסות להבין בכמה היפוכים ניתן
להגיע ממיקום 18 למיקום 19 או 20. ולמיקום 18, אנחנו כבר יודעים שבוודאות צריך 6 היפוכים. או אם נסתכל על מיקום 10 או 11, אנחנו לא צריכים לנסות להבין בכמה היפוכים אפשרי
להגיע לשם ממיקום P=0. אלא אנחנו ננסה להבין מהי הדרך הקצרה ביותר
להגיע אליהם ממקום 9 שאליו צריך 3 היפוכים, או אולי ממקום 12 שאליו צריך 4 היפוכים. ואם K הוא אי זוגי, אז יהיה עוד יותר קל לפתור את זה. ואם ... P. דהיינו, אנחנו צריכים להבין, במידה ולדוגמה K=11. תוך כמה היפוכים ניתן
להגיע ממיקום 1 למיקום 3-5-7-9. ואם K = 6, אנחנו צריכים להבין תוך כמה היפוכים אפשרי