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