והפעם נדבר על שאלת 2612. LeetCode - Minimum Reverse Operations הבאה:
לדוגמה: נתון המספר N = 10. ונתון גם עוד מספר בין 0 לבין 9. לדוגמה 3.
דהיינו, כל הערכים של המערך ARR הם 0, למעט במיקום P, שהערך שם הוא 1.
![]()
במילים אחרות, יש לנו מערך ARR באורך N כלשהו.
יש לנו מערך Banned שמייצג מקומות בתוך המערך ARR.
ויש לנו את הערך P, שמייצג מיקום בתוך המערך ARR.
כל המערך ARR מאותחל ל 0, למעט המיקום P שמאותחל ל 1.
כאשר בוודאות P לא יכול להיות אף אחד מהערכים שנמצאים במערך Banned.
![]()
דהיינו, נתון לנו גם משתנה K, שמייצג את האורך האפשרי של תת המערך שאפשרי לבצע עליו היפוך. ואנחנו יכולים לקחת מקטע / תת מערך מתוך המערך ARR, שתת המקטע יהיה באורך K. ואנחנו יכולים לעשות איתו פעולת היפוך בתוך המערך ARR.
דהיינו, אנחנו יכולים לקחת מקטעים באורך K מתוך המערך ARR ולעשות להם פעולת היפוך. לדוגמה, בהינתן ש K = 4.
![]()
אז תתי מקטעים באורך 4 יכולים להיות אלו:
![]()
כאשר פעולת היפוך תיראה כך:
נניח שלקחנו את המיקום, מ 3 ועד 6, אז פעולת ההיפוך תיראה כך:
![]()
ואם נניח שלקחנו את המיקום, מ 2 ועד 5, אז פעולת ההיפוך תיראה כך:
![]()
דהיינו, פעולת היפוך, במידה והיא על מתבצעת על טווח שנמצא בו הערך P, הרי שהיא יכולה להזיז את P ממקום למקום. והערך P עובר למקום חדש.
כמובן שהערך P לא תמיד יזוז בפעולת היפוך, או אם פעולת ההיפוך לא מתבצעת על מקום שהוא נמצא בו. או אם הוא נמצא במרכז של פעולת ההיפוך, כאשר תת המערך הוא אי זוגי. לדוגמה:
![]()
וכאן נעיר, כי מי שניסח את השאלה, היה קודם כל צריך להסביר, מה זה ההיפוך K ורק אחר כך להוסיף את העניין של ה Banned.
כי הערכים של Banned, אומרים לנו היכן P לא יכול להיות בפעולת היפוך. דהיינו, שאסור לנו לבצע פעולת היפוך באורך K, שתגרום ל P להיות אחרי פעולת ההיפוך, במקום שנמצא בתוך המערך Banned. זה כל הסיפור כולו.
כאשר בתוך המערך ANS, אנחנו צריכים בכל אחד מהמקומות שבו, לכתוב את מינימום פעולות ההיפוך הנדרשות, לצורך הבאת הערך 1 למיקום החדש.
ואם אין אפשרות להביא את הערך 1 למיקום במערך ANS, אז באותו מיקום במערך ANS, צריך להיות - 1.
לדוגמה, ניקח את הדוגמה הקודמת ונקבל:
![]()
דהיינו, במקום 3 נכתוב 0, כי לא צריך לעשות שום היפוך, כדי להביא לשם את הערך 1.
ובמקום 4 נכתוב 1. כי במידה ו K הוא 4, אז בהיפוך אחד, ניתן להביא את הערך 1 מהמיקום 3 למיקום 4.
וכן על זה הדרך, ניתן לבצע את ההיפוך הבא:
![]()
וגם את ההיפוך הבא:
![]()
וכן על זה הדרך, ניתן להמשיך ולמלא את כל שאר האפשרויות של כל ההיפוכים האפשריים וכולי.
כל הערכים של Ans לא תלויים אחד בשני.
היפוך של מערך באורך K, הוא מחזיר את הערכים של המקטע של המערך Arr בסדר הפוך.
אז בעצם מה שואלים אותנו?
נותנים לנו מספר N שמייצג אורך של מערך ARR באורך N-1. לדוגמה 100. דהיינו, מערך עם 100 מקומות החל מ 0 ועד 99.
כל הערכים של המערך, הם 0.
עכשיו נותנים לנו מספר P, שמייצג מיקום בתוך המערך ARR, שבמיקום של P, יש את הערך 1 במקום 0.
לדוגמה P = 76, דהיינו, במערך ARR במיקום 76, יש את הערך 1 במקום 0.
עכשיו, אנחנו מנסים למקם את הערך 1 בכל אחד מהמקומות שבמערך ARR באמצעות פעולת ההיפוך הבאה:
מביאים לנו גם ערך K, שמייצג את האורך של תת המערך שאנחנו יכולים לקחת מהמערך ARR. לדוגמה K = 8. דהיינו, אנחנו יכולים לקחת מהמערך ARR מקטעים שונים באורך 8, ולהפוך אותם. דהיינו, למקם מחדש את הערכים של אותם 8 מקומות, בסדר הפוך לסדר הקודם.
ואם הערך 1 היה בתוך אותו הטווח 8, אז ממילא הערך 1 יתחיל לזוז ממקום למקום.
כאשר אחרי כל היפוך K, הערך 1, יהיה במיקום חדש. ואם אחרי היפוך ראשון, הערך 1 זז מנקודה X לנקודה Y בתוך המערך ARR, אז עכשיו אנחנו יכולים לעשות שוב פעם פעולת היפוך נוספת, באורך K = 8 כנ"ל, ואז ממילא נוכל להזיז שוב ושוב את הערך 1 ממקום למקום.
דהיינו, באמצעות פעולות היפוך באורך K, נוכל להזיז את הערך 1 בתוך המערך ARR, ממקום למקום.
ועלינו לחשב, תוך כמה מינימום פעולות היפוך, נוכל להעביר את הערך 1, מנקודת המוצא שלו, לכל אחד מהמיקומים בתוך המערך ARR. אחרי כמה מינימום פעולות היפוך.
ואת התשובה לכך, אנחנו צריכים להחזיר בתוך מערך ANS.
דהיינו, במערך ANS, בכל מקום בתוכו, אנחנו נצטרך לכתוב, בכמה מינימום פעולות היפוך ניתן להזיז את 1 מנקודת ההתחלה שלו, למערך ARR במקום 0 ובמקום 1 ובמקום 2 וכולי, עד לסוף המערך.
ואם הערך 1 לא יכול להגיע בשום דרך, למיקום X במערך ARR, אז במערך ANS, באותו המיקום שאליו לא יכול להגיע הערך 1, נכתוב - 1. דהיינו, לכאן לא ניתן להביא את הערך 1.
כאשר, כדי לסבך אותנו עוד קצת, נתנו לנו גם רשימה של מקומות בשם Banned שאומרת, שלכאן הערך 1 לא יכול להגיע בשום שלב.
ועכשיו אחרי שהבנו את השאלה, עכשיו כמובן נשאל, איך ניגשים לפתור את השאלה הזאת?
אז ננסה להפוך את השאלה הנ"ל לשאלה יותר קלה. ואיך?
אז קודם כל ננסה לפתור את השאלה, במקרה פשוט שבו אין ערכים של Banned כלשהם. כי תמיד צריכים להתחיל מהמקרה הפשוט ביותר, דהיינו, בלי Banned.
ועכשיו אני אעשה דילוג קטן, לכיוון אפשרי לפתור את הבעיה הזאת, ואחר כך אסביר איך באמת לגשת לפתרון של הבעיה הזאת.
אז לכאורה הדרך לפתרון היא פשוטה ביותר. עלינו לקחת את המערך ARR ואת הערך K ולסמן את כל ההיפוכים האפשריים שאפשרי לעשות על המערך ARR, היפוכים באורך K. ולסמן אחרי כל היפוך, היכן יהיה הערך 1.
ועלינו לבדוק את כל האפשרויות האפשריות של לעשות כל היפוך באורך K על המערך ARR. ואחרי הכל עלינו לראות היכן נמצא הערך 1. ועלינו לבדוק, מה היה מינימום ההיפוכים האפשריים, כדי להביא לשם את הערך 1.
דהיינו, בדוק את כל האפשרויות האפשריות להעביר את 1 ממקום למקום. ואז תראה מהי הדרך הקצרה ביותר להעביר את 1 ממקום למקום.
והשיטה הזאת, כמובן שהיא תעבוד במציאות, אבל כמובן גם שהיא לא יעילה לחלוטין.
כי אם ניקח לדוגמה מערך באורך 1,000,000 ונניח ש K הוא 6, ונניח ש P = 546. אז כמות האפשרויות לבדוק את כל האפשרויות האפשריות, היא מאוד גדולה וכולי. ולכן כמובן שאנחנו מחפשים פתרון יותר יעיל וקצר. אז איך ניגשים לנתח את השאלה הזאת?
אז תמיד לעולמי עולמים, עלינו לנסות לפרק את השאלה, לחלקים הקטנים ביותר שיש ולחפש את המקרה הפשוט ביותר והקל ביותר.
וכדי לפתור את השאלה, עלינו לנסות להבין את החוקיות של מה שקורה כאן, על ידי ניתוח של המקרה הקל ביותר, אל המקרה הקשה יותר. ולנסות למצוא חוקיות כלשהי, להבין איך הדברים עובדים. מהקל אל הכבד.
ובפועל, הפתרון לשאלה הזאת, הוא די פשוט, די מאוד פשוט. אם רק נלך עם החשיבה של מה בטוח נכון. אבל כדי להבין מה בטוח נכון, צריך לנסות לא למצוא תשובה לשאלה הגדולה, אלא לנסות לפרק את התהליך לחלקים הכי קטנים, כמו שתכף נעשה.
והמטרה כאן, היא להרגיל את המוח, לפרק את התהליך לחלקים קטנים, כדי להתרגל לחלק לחלקים קטנים, שאז ומתוך זה, המוח יבין מה בטוח נכון, החלק הכי קטן. וכך אפשרי למצוא את התשובה הפשוטה לשאלה הגדולה.
אז לשם כך נתחיל בלנתח את המקרה הפשוט ביותר, רק כדי להבין קצת את החוקיות של התהליך שלפנינו. ומהו המקרה הפשוט ביותר?
אז המקרה הפשוט ביותר, הוא כאשר N = 1 ו P = 0. דהיינו, המערך הוא באורך של תא אחד בלבד. ו הערך 1 נמצא בתא היחיד של המערך ARR. והרי שבמקרה כזה, לא משנה מה יהיה הערך של K, הרי שהערך 1 לא יכול בכלל לזוז ממקומו, ולכן נקבל את התוצאה הבאה:
![]()
עכשיו ננסה להעלות את רמת המורכבות, אבל בכמה שפחות. ואז נגיע למצב שלצורך העניין ש ARR הוא באורך של 2. ונניח שבמקום הראשון יש לנו את הערך 1. ונניח ש K = 1. מה יקרה במקרה כזה?
![]()
במקרה כזה הערך 1 לא יוכל לזוז ממקומו בכל מקרה, כי עם תת מערך באורך של 1, לא ניתן להזיז את הערך 1 ממקומו. כי לא ניתן להפוך שום דבר כאשר תת המערך הוא 1.
ולכן ANS במיקום 0 יהיה בערך 0, כי ה 1 כבר נמצא שם בלי שום פעולת היפוך.
ו ANS במיקום 1 יהיה שווה ל - 1, כי הערך 1 לא יכול להגיע לשם בשום היפוך, כי מקדם ההיפוך הוא 1 בלבד שלא מאפשר להזיז את הערך 1 ממקום למקום.
ונעשה עוד בדיקה עם מערך באורך 10, כאשר המיקום ההתחלתי הוא 5 והמקדם היפוך הוא 1 ונקבל את זה:
![]()
בשורה התחתונה, אנחנו מבינים בוודאות שמקדם היפוך 1, לא יכול להזיז את הערך 1 מהמקום ההתחלתי שלו P לשום מקום אחר. ולכן כל הערכים של ANS יהיו - 1, כי הערך 1 לא יכול לעבור אליהם. למעט כמובן המיקום ההתחלתי שהוא P.
אז עד עכשיו בדקנו מקדם היפוך K = 1, ב 3 מצבים. במצב של אורך N= 1 אורך N= 2 וגם אורך N = 10, כאשר בפעם האחרונה שיחקנו קצת גם עם המיקום של P ששמנו אותו באמצע המערך.
עכשיו ננסה להעלות עוד קצת רמת הקושי, ונבדוק מה קורה כאשר K = 2, דהיינו, שמקדם ההיפוך הוא 2.
אז לצורך העניין נבדוק את המקרה הבא, שבו N = 2, K = 2 ו P = 0.
![]()
במקרה הזה, אנחנו נעשה היפוך באורך 2, של המקומות [0,1] שיהפכו להיות עם הערכים של [1,0] ואז נעביר את הערך 1 מהמיקום ההתחלתי שלו שהוא 0 למיקום החדש שהוא 1.
דהיינו, ANS במקום 0, יהיה 0, כי לא צריך שום היפוך כדי להביא לשם את הערך 1.
אבל ANS במיקום 1, יהיה 1, כי צריך פעולת היפוך 1 באורך 2, כדי להעביר לשם את הערך 1, מהמיקום 0 אל המיקום 1 כמו שניתן לראות בתמונה.
ועכשיו נעלה את רמת הקושי, למקרה ש N = 10 ונקבל את המקרה הבא:
![]()
ואם לצורך העניין N = 10, K = 2 אבל P = נניח 5, אז נקבל את התוצאה הבאה, אם נעשה היפוכים ימינה:
![]()
וגם את התוצאה הבאה, אם נעשה היפוכים שמאלה:
![]()
בקיצור, עד כה הבנו, שמקדם K=1, לא מצליח להעביר את המיקום של ה P ממקום למקום
ומקדם K=2, מעביר ממקום למקום את המיקום ההתחלתי של P, בדילוגים של מקום 1 בכל פעם.
ועכשיו כמובן ננסה להבין את K=3 ונבדוק את המקרה הבא, כאשר P=5:
![]()
ועכשיו אני ממליץ לקורא לבדוק עוד מקרים נוספים, למרות שאני מקצר כאן את התהליך ומתקדם למסקנות שעדיין אולי לא ברורות מאליהן. אבל מי שיבדוק עוד מקרים כאשר K=3 וישנה בכל פעם את הערך של P, אז הוא יראה תופעה מעניינת שקורית כאשר K=3.
כי נראה שכאשר K = 3, הרי שיש היפוכים של 3, שלא מזיזים את הערך 1 ממקום למקום. וכאשר K=3, הרי שהערך 1 יכול לזוז רק בדילוגים של 2 מקומות.
דהיינו, עד כה הבנו, שכאשר K=1 אז הערך P לא יכול לזוז ממקום למקום. וכאשר K=2, אז הערך P יכול לזוז לכל מקום, בדילוגים של צעד 1 בכל פעם. וכאשר K=3, אז יש מקומות שאליהם לא ניתן להזיז את הערך P. כי הערך P יכול לזוז רק ב 2 דילוגים, אבל הוא לא יכול באמצעות מקדם K=3, לעבור מקום 1 ימינה או שמאלה.
ועכשיו ננסה לבדוק את K=4 כאשר N=14 ונקבל את זה:
אני מדגיש, כי לא הבאתי כאן את כל האפשרויות האפשריות, אלא רק את האפשרויות הטובות ביותר, כדי לקדם את הערך P ממקום למקום.
![]()
ונוכל לראות, כי כאשר K=4, אנחנו יכולים להעביר את P מכל מקום לכל מקום, רק השאלה היא, תוך כמה מינימום מהלכים.
איך לבדוק חוקיות של תהליכים?
אני מדגיש שכאשר אנחנו מנסים לבדוק חוקיות של תהליכים, אנחנו צריכים להתעלם ממקרי קצה ולנסות להבין רק את המקרה הכללי בלבד. דהיינו,, לא לנסות להבין מיד את החוקיות בכל המקרים האפשריים, אלא לנסות קודם כל להבין את החוקיות של המקרים הנפוצים ביותר.
לדוגמה, כאשר N=3, אז אם המקדם K=4, הרי שהוא לא יכול להזיז את הערך P ממקום למקום. או בכל מקרה שהערך K קטן מהערך N, הרי שזה נחשב למקרה קצה. או במילים אחרות, צריכים לנסות להבין את החוקיות, במקרה הכללי, לפני שמנסים להבין את החוקיות בכל מקרה הקצה האפשריים.
ואם נבדוק את K=5, נגלה שיש בו תופעה דומה לכאשר K=3 או כאשר נבדוק גם את K=7 או כאשר K=מספר לא זוגי. כי נגלה את החוקיות הבאה:
אם K=מספר לא זוגי, הרי שאין שום אפשרות בעולם להעביר את P ממיקום זוגי למיקום אי זוגי. דהיינו, אם K = מספר אי זוגי, אז, אם הערך ההתחלתי של P הוא מספר זוגי, הרי שאין שום אפשרות להעביר את P למיקום אי זוגי. ואם הערך ההתחלתי של P הוא מספר אי זוגי, הרי שלא משנה מה, תמיד P יישאר במספר אי זוגי ולא יעבור למיקום זוגי.
ואם נמשיך לבדוק את K=6 או K=8 וכולי, נראה שברמה העקרונית (דהיינו לאו דווקא בכל מקרי הקצה), הרי שניתן להזיז את P מכל מקום לכל מקום, ממקום זוגי לאי זוגי ולהפך. רק השאלה תהיה מהי הדרך היעילה והמהירה ביותר להזיז את הערך P ממקום למקום.
אז מה הבנו עד כה לגבי חוקיות של התהליך?
אז הבנו ש K=1, לא מזיז את P לשום מקום.
ו K=מספר זוגי, יכול להזיז את P לכל מקום.
ואם K=אי זוגי, הרי שP חייב להישאר על זוגי / אי זוגי, בהתאם לנקודת ההתחלה שלו.
ואם K=מספר זוגי, הרי שניתן במהלך אחד להזיז את P ל K מקומות אפשריים (במידה ו N לא מגביל אותנו).
ואם K = אי זוגי, הרי שניתן במהלך אחד להזיז את P, ל / 2(K+1) מקומות.
דהיינו, בכל מקרה:
אם K= מספר כלשהו, אז הרי שבהיפוך 1, ניתן להזיז את הערך P, ללא יותר מ K מקומות.
אם K=2, אז במהלך של היפוך 1, נוכל להזיז את P ללא יותר מ 2 מקומות.
ואם K = 4, הרי שיש רק 4 אפשרויות שאליהם ניתן להזיז את P, בהיפוך 1.
ואם K = 3, הרי שניתן להזיז את P בהיפוך 1 רק ל 2 מקומות בלבד.
או אם K = 5, הרי שניתן להזיז את P בהיפוך 1 ל 3 מקומות בלבד.
ואם K = 99, אז בהיפוך 1 ניתן להזיז את P ל 50 מקומות בלבד.
ואם K = 200, אז ניתן להזיז את P במהלך 1 ל 200 מקומות.
והכל כמובן במקרה הכללי, דהיינו, שאין חסימת ומגבלת מיקום מצד ימין או שמאל, שמגבילה את ההיפוך האפשרי.
ובעצם עד כאן, הבנו קצת או אולי אפילו המון, את החוקיות של ההיפוכים האפשריים.
ואחרי שהבנו את כל זה, עכשיו ננסה להבין, לגבי המקרה הכללי, מה בטוח נכון? האם יש משהו שהוא בטוח נכון?
וכמובן שאנחנו נתעלם מהערכים של Banned שהם מגבילים את התנועה של P. וננסה לפתור את השאלה, בהנחה שאין שום ערכים חסומים כלשהם.
אז מה בטוח נכון?
אז כבר יש כמה דברים שהם בטוח נכונים, לדוגמה, שאם 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 היפוכים וכולי, ואין שום אפשרות להגיע למיקום 18 בפחות מ 6 היפוכים.
ובדוגמה שהבאתי, אנחנו עושים את כל ההיפוכים ימינה. אבל כמובן שצריכים לעשות את זה גם שמאלה, במידה ויש להיכן להפוך שמאלה בהתאם למקרה שמביאים לנו.
או במילים אחרות, יש מיקומים מסויימים, שאנחנו יכולים להגיע אליהם בהיפוך 1 או ב 2 היפוכים או 10 היפוכים. והמשימה שלנו היא לדעת מהו המינימום היפוכים האפשרי, להגיע לכל נקודה.
אבל אם מראש נסמן את המיקום הרחוק ביותר ימינה, שניתן להגיע בהיפוך 1 ימינה, אז משם נוכל לדעת בוודאות, שמכאן ואילך ימינה, אפשרי להגיע רק ב 2 היפוכים ומעלה. ואחר כך נסמן שוב ימינה את הנקודה הרחוקה ביותר שאפשרי להגיע אליה עם 2 היפוכים ימינה. ונדע בוודאות, שאין שום אפשרות להגיע ימינה ממנה, בפחות מ 3 היפוכים וכולי.
דהיינו, השלב הראשון בלפתור את התרגיל, הוא לרוץ על המערך ANS החל מנקודת ההתחלה של P לכיוון ימינה ו/או שמאלה (במידה ואפשרי לרוץ ימינה או שמאלה על הרשימה בהתאם) בדילוגים בגודל של K-1, ולסמן בסדר עולה 1-2-3 וכולי. דהיינו, קודם כל לנסות לסמן בתוך ANS את המקומות שבטוח נכונים שאליהם בוודאות לא ניתן להגיע בפחות מ X דילוגים ימינה או שמאלה.
ואם תוך כדי שאנחנו עושים דילוג ימינה, אנחנו מגיעים לתוך מקום שנמצא בו הערך Banned, דהיינו, שלא ניתן להגיע אליו, אז ניקח מיקום 1 שמאלה דהיינו, K-2 וכולי. ומשם נמשיך לדלג ימינה. ואם גם בו יש Banned אז נחזור עוד צעד אחד אחורה וכולי, עד שנגיע למצב שנדע בוודאות שלא ניתן לדלג יותר ימינה.
דהיינו, אם יש רצף של מקומות חסומים, שהם באורך (K-1), הרי שברגע שנגיע אליהם, לא נוכל יותר לזוז משם ימינה או שמאלה בהתאם ומשם ואילך הכל יהיה - 1 בהתאם.
ובמידה ועד כה פעלנו תקין לפי ההוראות הקודמות, הרי שכרגע יש לנו פרישה ימינה ושמאלה, מנקודת ה P על עבר 2 הקצוות, של עוגנים ונקודות של וודאות, שבכל נקודה אנחנו יודעים בוודאות שלא ניתן להגיע אליה, בפחות היפוכים מהערך שכתוב בה.
כי כמו שאמרנו בדוגמה הקודמת, אנחנו יודעים בוודאות, שאין שום אפשרות בעולם להגיע למיקום 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 הוא אי זוגי, אז יהיה עוד יותר קל לפתור את זה. ואם K הוא זוגי, גם קל לפתור את זה, אבל קצת יותר ארוך.
ובעצם זה אומר, שעכשיו אנחנו צריכים להבין את החוקיות של התזוזה בתוך K עצמו בלבד. בלי קשר לנקודת ההתחלה של P.
דהיינו, אנחנו צריכים להבין, במידה ולדוגמה K=11. תוך כמה היפוכים ניתן להגיע ממיקום 1 למיקום 3-5-7-9. ואם K = 6, אנחנו צריכים להבין תוך כמה היפוכים אפשרי להגיע ממיקום 1 למיקום 2-3-4-5. כי אלו בעצם הטווחים שאליהם אנחנו רוצים להגיע בתוך הוודאות שמצאנו קודם.
בקיצור... את ההמשך, נסו לגלות לבד.
סיכום:
לקחנו שאלה שנחשבת לדי מסובכת, שגם להבין אותה די קשה, בגלל שהיא מנוסחת בצורה די קלוקלת. מפה לשם ניסינו להבין את החוקיות של התהליך וגילינו שיש כאן חוקיות. מפה לשם הפתרון במהותו הוא, לסמן קודם כל את כל נקודות הוודאות לגבי הנקודות הרחוקות ביותר שאליהן צריך לפחות X היפוכים. והכל בהתאם למיקומים חסומים. ומכאן ואילך עלינו רק לסמן את המיקומים שבין המיקומים הוודאיים שאנחנו כבר יודעים אותם.
בהצלחה.
You are given an integer n and an integer p in the range [0, n - 1]. Representing a 0-indexed array arr of length n where all positions are set to 0's, except position p which is set to 1.
You are also given an integer array banned containing some positions from the array. For the ith position in banned, arr[banned[i]] = 0, and banned[i] ! = p.
You can perform multiple operations on arr. In an operation, you can choose a subarray with size k and reverse the subarray. However, the 1 in arr should never go to any of the positions in banned. In other words, after each operation arr[banned[i]] remains 0.
Return an array ans where for each i from [0, n - 1], ans[i] is the minimum number of reverse operations needed to bring the 1 to position i in arr, or -1 if it is impossible.
A subarray is a contiguous non-empty sequence of elements within an array.
The values of ans[i] are independent for all i's.
The reverse of an array is an array containing the values in reverse order.
Example 1:
Input: n = 4, p = 0, banned = [1,2], k = 4
Output: [0,- 1,- 1,1]
Explanation: In this case k = 4 so there is only one possible reverse operation we can perform, which is reversing the whole array. Initially, 1 is placed at position 0 so the amount of operations we need for position 0 is 0. We can never place a 1 on the banned positions, so the answer for positions 1 and 2 is -1. Finally, with one reverse operation we can bring the 1 to index 3, so the answer for position 3 is 1.
Example 2:
Input: n = 5, p = 0, banned = [2,4], k = 3
Output: [0,- 1,- 1,- 1,- 1]
Explanation: In this case the 1 is initially at position 0, so the answer for that position is 0. We can perform reverse operations of size 3. The 1 is currently located at position 0, so we need to reverse the subarray [0, 2] for it to leave that position, but reversing that subarray makes position 2 have a 1, which shouldn't happen. So, we can't move the 1 from position 0, making the result for all the other positions -1.
Example 3:
Input: n = 4, p = 2, banned = [0,1,3], k = 1
Output: [ - 1,- 1,0,- 1]
Explanation: In this case we can only perform reverse operations of size 1. So the 1 never changes its position.
וכמו שאמרנו, המאמץ הראשוני צריך להיות בלהבין את השאלה. ואם השאלה עצמה לא מנוסחת בצורה ברורה, זאת בעיה שלך. כי בעולם האמיתי, לא תמיד השאלה ברורה. והשאלה הספציפית הזאת, נחשבת באתר ליטקוד לשאלה די קשה, אפילו להבנה. ולכן קודם כל נבין את השאלה.You are also given an integer array banned containing some positions from the array. For the ith position in banned, arr[banned[i]] = 0, and banned[i] ! = p.
You can perform multiple operations on arr. In an operation, you can choose a subarray with size k and reverse the subarray. However, the 1 in arr should never go to any of the positions in banned. In other words, after each operation arr[banned[i]] remains 0.
Return an array ans where for each i from [0, n - 1], ans[i] is the minimum number of reverse operations needed to bring the 1 to position i in arr, or -1 if it is impossible.
A subarray is a contiguous non-empty sequence of elements within an array.
The values of ans[i] are independent for all i's.
The reverse of an array is an array containing the values in reverse order.
Example 1:
Input: n = 4, p = 0, banned = [1,2], k = 4
Output: [0,- 1,- 1,1]
Explanation: In this case k = 4 so there is only one possible reverse operation we can perform, which is reversing the whole array. Initially, 1 is placed at position 0 so the amount of operations we need for position 0 is 0. We can never place a 1 on the banned positions, so the answer for positions 1 and 2 is -1. Finally, with one reverse operation we can bring the 1 to index 3, so the answer for position 3 is 1.
Example 2:
Input: n = 5, p = 0, banned = [2,4], k = 3
Output: [0,- 1,- 1,- 1,- 1]
Explanation: In this case the 1 is initially at position 0, so the answer for that position is 0. We can perform reverse operations of size 3. The 1 is currently located at position 0, so we need to reverse the subarray [0, 2] for it to leave that position, but reversing that subarray makes position 2 have a 1, which shouldn't happen. So, we can't move the 1 from position 0, making the result for all the other positions -1.
Example 3:
Input: n = 4, p = 2, banned = [0,1,3], k = 1
Output: [ - 1,- 1,0,- 1]
Explanation: In this case we can only perform reverse operations of size 1. So the 1 never changes its position.
You are given an integer n and an integer p in the range [0, n - 1].
נתון לך מספר N וגם עוד מספר P שנמצא בטווח שבין 0 לבין N-1.לדוגמה: נתון המספר N = 10. ונתון גם עוד מספר בין 0 לבין 9. לדוגמה 3.
Representing a 0-indexed array arr of length n where all positions are set to 0's, except position p which is set to 1.
המספרים האלו מייצגים מערך שמתחיל בערך 0, מערך בשם ARR שהוא באורך N. כאשר כל המיקומים במערך מאותחלים לערך 0, למעט המיקום P שנמצא בתוך המערך, שהוא מאותחל ל 1.דהיינו, כל הערכים של המערך ARR הם 0, למעט במיקום P, שהערך שם הוא 1.
You are also given an integer array banned containing some positions from the array.
נותנים לך גם עוד מערך בשם Banned שמכיל בתוכו מיקומים בתוך המערך ARR. דהיינו, בתוך המערך Banned, יש מספרים של מקומות שנמצאים בתוך המערך ARR.
For the ith position in banned, arr[banned[i]] = 0, and banned[i] ! = p.
כאשר בעצם המערך Banned מייצג מקומות שבהם חסום הערך P. דהיינו, בכל המקומות של שנמצאים במערך Banned, חייב להיות הערך 0 ולא יכול להיות הערך P דהיינו, 1.במילים אחרות, יש לנו מערך ARR באורך N כלשהו.
יש לנו מערך Banned שמייצג מקומות בתוך המערך ARR.
ויש לנו את הערך P, שמייצג מיקום בתוך המערך ARR.
כל המערך ARR מאותחל ל 0, למעט המיקום P שמאותחל ל 1.
כאשר בוודאות P לא יכול להיות אף אחד מהערכים שנמצאים במערך Banned.
You can perform multiple operations on arr.
אתה יכול לבצע פעולת הכפלה / היפוך על המערך ARR. צריך לשים לב, שלמילה multiple יש כל מיני פירושים אפשריים. אחד מהקשיים להבין את השאלה, נובע מכך שלמילה הזאת יש כל מיני פירושים אפשריים. הפירוש הנכון כאן, הוא שאתה יכול לבצע פעולת הכפלה / היפוך על המערך ARR כדלקמן.
In an operation, you can choose a subarray with size k and reverse the subarray.
בכל פעולת היפוך, אתה יכול לבחור תת מערך, באורך K ולהפוך אותו בתוך המערך ARR.דהיינו, נתון לנו גם משתנה K, שמייצג את האורך האפשרי של תת המערך שאפשרי לבצע עליו היפוך. ואנחנו יכולים לקחת מקטע / תת מערך מתוך המערך ARR, שתת המקטע יהיה באורך K. ואנחנו יכולים לעשות איתו פעולת היפוך בתוך המערך ARR.
דהיינו, אנחנו יכולים לקחת מקטעים באורך K מתוך המערך ARR ולעשות להם פעולת היפוך. לדוגמה, בהינתן ש K = 4.
אז תתי מקטעים באורך 4 יכולים להיות אלו:
כאשר פעולת היפוך תיראה כך:
נניח שלקחנו את המיקום, מ 3 ועד 6, אז פעולת ההיפוך תיראה כך:
ואם נניח שלקחנו את המיקום, מ 2 ועד 5, אז פעולת ההיפוך תיראה כך:
דהיינו, פעולת היפוך, במידה והיא על מתבצעת על טווח שנמצא בו הערך P, הרי שהיא יכולה להזיז את P ממקום למקום. והערך P עובר למקום חדש.
כמובן שהערך P לא תמיד יזוז בפעולת היפוך, או אם פעולת ההיפוך לא מתבצעת על מקום שהוא נמצא בו. או אם הוא נמצא במרכז של פעולת ההיפוך, כאשר תת המערך הוא אי זוגי. לדוגמה:
וכאן נעיר, כי מי שניסח את השאלה, היה קודם כל צריך להסביר, מה זה ההיפוך K ורק אחר כך להוסיף את העניין של ה Banned.
כי הערכים של Banned, אומרים לנו היכן P לא יכול להיות בפעולת היפוך. דהיינו, שאסור לנו לבצע פעולת היפוך באורך K, שתגרום ל P להיות אחרי פעולת ההיפוך, במקום שנמצא בתוך המערך Banned. זה כל הסיפור כולו.
However, the 1 in arr should never go to any of the positions in banned. In other words, after each operation arr[banned[i]] remains 0.
שזה מה שהסברנו כרגע, ש הערך 1 שנמצא במיקום P, לעולם לא יכול להיות במיקום של ערך שנמצא בתוך רשימת המקומות החסומים. ולכן תמיד רשימת המקומות החסומים, תהיה 0.
Return an array ans where for each i from [0, n - 1], ans[i] is the minimum number of reverse operations needed to bring the 1 to position i in arr, or -1 if it is impossible.
עכשיו מבקשים מאיתנו, להחזיר מערך בשם ANS, שהוא יהיה באורך N-1, דהיינו, שהוא יהיה באותו האורך בדיוק של המערך ARR.כאשר בתוך המערך ANS, אנחנו צריכים בכל אחד מהמקומות שבו, לכתוב את מינימום פעולות ההיפוך הנדרשות, לצורך הבאת הערך 1 למיקום החדש.
ואם אין אפשרות להביא את הערך 1 למיקום במערך ANS, אז באותו מיקום במערך ANS, צריך להיות - 1.
לדוגמה, ניקח את הדוגמה הקודמת ונקבל:
דהיינו, במקום 3 נכתוב 0, כי לא צריך לעשות שום היפוך, כדי להביא לשם את הערך 1.
ובמקום 4 נכתוב 1. כי במידה ו K הוא 4, אז בהיפוך אחד, ניתן להביא את הערך 1 מהמיקום 3 למיקום 4.
וכן על זה הדרך, ניתן לבצע את ההיפוך הבא:
וגם את ההיפוך הבא:
וכן על זה הדרך, ניתן להמשיך ולמלא את כל שאר האפשרויות של כל ההיפוכים האפשריים וכולי.
A subarray is a contiguous non-empty sequence of elements within an array.
The values of ans[i] are independent for all i's.
The reverse of an array is an array containing the values in reverse order.
כל תת מערך מכיל ערכים רציפים ולא ריקים מתוך המערך המקורי.The values of ans[i] are independent for all i's.
The reverse of an array is an array containing the values in reverse order.
כל הערכים של Ans לא תלויים אחד בשני.
היפוך של מערך באורך K, הוא מחזיר את הערכים של המקטע של המערך Arr בסדר הפוך.
אז בעצם מה שואלים אותנו?
נותנים לנו מספר N שמייצג אורך של מערך ARR באורך N-1. לדוגמה 100. דהיינו, מערך עם 100 מקומות החל מ 0 ועד 99.
כל הערכים של המערך, הם 0.
עכשיו נותנים לנו מספר P, שמייצג מיקום בתוך המערך ARR, שבמיקום של P, יש את הערך 1 במקום 0.
לדוגמה P = 76, דהיינו, במערך ARR במיקום 76, יש את הערך 1 במקום 0.
עכשיו, אנחנו מנסים למקם את הערך 1 בכל אחד מהמקומות שבמערך ARR באמצעות פעולת ההיפוך הבאה:
מביאים לנו גם ערך K, שמייצג את האורך של תת המערך שאנחנו יכולים לקחת מהמערך ARR. לדוגמה K = 8. דהיינו, אנחנו יכולים לקחת מהמערך ARR מקטעים שונים באורך 8, ולהפוך אותם. דהיינו, למקם מחדש את הערכים של אותם 8 מקומות, בסדר הפוך לסדר הקודם.
ואם הערך 1 היה בתוך אותו הטווח 8, אז ממילא הערך 1 יתחיל לזוז ממקום למקום.
כאשר אחרי כל היפוך K, הערך 1, יהיה במיקום חדש. ואם אחרי היפוך ראשון, הערך 1 זז מנקודה X לנקודה Y בתוך המערך ARR, אז עכשיו אנחנו יכולים לעשות שוב פעם פעולת היפוך נוספת, באורך K = 8 כנ"ל, ואז ממילא נוכל להזיז שוב ושוב את הערך 1 ממקום למקום.
דהיינו, באמצעות פעולות היפוך באורך K, נוכל להזיז את הערך 1 בתוך המערך ARR, ממקום למקום.
ועלינו לחשב, תוך כמה מינימום פעולות היפוך, נוכל להעביר את הערך 1, מנקודת המוצא שלו, לכל אחד מהמיקומים בתוך המערך ARR. אחרי כמה מינימום פעולות היפוך.
ואת התשובה לכך, אנחנו צריכים להחזיר בתוך מערך ANS.
דהיינו, במערך ANS, בכל מקום בתוכו, אנחנו נצטרך לכתוב, בכמה מינימום פעולות היפוך ניתן להזיז את 1 מנקודת ההתחלה שלו, למערך ARR במקום 0 ובמקום 1 ובמקום 2 וכולי, עד לסוף המערך.
ואם הערך 1 לא יכול להגיע בשום דרך, למיקום X במערך ARR, אז במערך ANS, באותו המיקום שאליו לא יכול להגיע הערך 1, נכתוב - 1. דהיינו, לכאן לא ניתן להביא את הערך 1.
כאשר, כדי לסבך אותנו עוד קצת, נתנו לנו גם רשימה של מקומות בשם Banned שאומרת, שלכאן הערך 1 לא יכול להגיע בשום שלב.
ועכשיו אחרי שהבנו את השאלה, עכשיו כמובן נשאל, איך ניגשים לפתור את השאלה הזאת?
אז ננסה להפוך את השאלה הנ"ל לשאלה יותר קלה. ואיך?
אז קודם כל ננסה לפתור את השאלה, במקרה פשוט שבו אין ערכים של Banned כלשהם. כי תמיד צריכים להתחיל מהמקרה הפשוט ביותר, דהיינו, בלי Banned.
ועכשיו אני אעשה דילוג קטן, לכיוון אפשרי לפתור את הבעיה הזאת, ואחר כך אסביר איך באמת לגשת לפתרון של הבעיה הזאת.
אז לכאורה הדרך לפתרון היא פשוטה ביותר. עלינו לקחת את המערך ARR ואת הערך K ולסמן את כל ההיפוכים האפשריים שאפשרי לעשות על המערך ARR, היפוכים באורך K. ולסמן אחרי כל היפוך, היכן יהיה הערך 1.
ועלינו לבדוק את כל האפשרויות האפשריות של לעשות כל היפוך באורך K על המערך ARR. ואחרי הכל עלינו לראות היכן נמצא הערך 1. ועלינו לבדוק, מה היה מינימום ההיפוכים האפשריים, כדי להביא לשם את הערך 1.
דהיינו, בדוק את כל האפשרויות האפשריות להעביר את 1 ממקום למקום. ואז תראה מהי הדרך הקצרה ביותר להעביר את 1 ממקום למקום.
והשיטה הזאת, כמובן שהיא תעבוד במציאות, אבל כמובן גם שהיא לא יעילה לחלוטין.
כי אם ניקח לדוגמה מערך באורך 1,000,000 ונניח ש K הוא 6, ונניח ש P = 546. אז כמות האפשרויות לבדוק את כל האפשרויות האפשריות, היא מאוד גדולה וכולי. ולכן כמובן שאנחנו מחפשים פתרון יותר יעיל וקצר. אז איך ניגשים לנתח את השאלה הזאת?
אז תמיד לעולמי עולמים, עלינו לנסות לפרק את השאלה, לחלקים הקטנים ביותר שיש ולחפש את המקרה הפשוט ביותר והקל ביותר.
וכדי לפתור את השאלה, עלינו לנסות להבין את החוקיות של מה שקורה כאן, על ידי ניתוח של המקרה הקל ביותר, אל המקרה הקשה יותר. ולנסות למצוא חוקיות כלשהי, להבין איך הדברים עובדים. מהקל אל הכבד.
ובפועל, הפתרון לשאלה הזאת, הוא די פשוט, די מאוד פשוט. אם רק נלך עם החשיבה של מה בטוח נכון. אבל כדי להבין מה בטוח נכון, צריך לנסות לא למצוא תשובה לשאלה הגדולה, אלא לנסות לפרק את התהליך לחלקים הכי קטנים, כמו שתכף נעשה.
והמטרה כאן, היא להרגיל את המוח, לפרק את התהליך לחלקים קטנים, כדי להתרגל לחלק לחלקים קטנים, שאז ומתוך זה, המוח יבין מה בטוח נכון, החלק הכי קטן. וכך אפשרי למצוא את התשובה הפשוטה לשאלה הגדולה.
אז לשם כך נתחיל בלנתח את המקרה הפשוט ביותר, רק כדי להבין קצת את החוקיות של התהליך שלפנינו. ומהו המקרה הפשוט ביותר?
אז המקרה הפשוט ביותר, הוא כאשר N = 1 ו P = 0. דהיינו, המערך הוא באורך של תא אחד בלבד. ו הערך 1 נמצא בתא היחיד של המערך ARR. והרי שבמקרה כזה, לא משנה מה יהיה הערך של K, הרי שהערך 1 לא יכול בכלל לזוז ממקומו, ולכן נקבל את התוצאה הבאה:
עכשיו ננסה להעלות את רמת המורכבות, אבל בכמה שפחות. ואז נגיע למצב שלצורך העניין ש ARR הוא באורך של 2. ונניח שבמקום הראשון יש לנו את הערך 1. ונניח ש K = 1. מה יקרה במקרה כזה?
במקרה כזה הערך 1 לא יוכל לזוז ממקומו בכל מקרה, כי עם תת מערך באורך של 1, לא ניתן להזיז את הערך 1 ממקומו. כי לא ניתן להפוך שום דבר כאשר תת המערך הוא 1.
ולכן ANS במיקום 0 יהיה בערך 0, כי ה 1 כבר נמצא שם בלי שום פעולת היפוך.
ו ANS במיקום 1 יהיה שווה ל - 1, כי הערך 1 לא יכול להגיע לשם בשום היפוך, כי מקדם ההיפוך הוא 1 בלבד שלא מאפשר להזיז את הערך 1 ממקום למקום.
ונעשה עוד בדיקה עם מערך באורך 10, כאשר המיקום ההתחלתי הוא 5 והמקדם היפוך הוא 1 ונקבל את זה:
בשורה התחתונה, אנחנו מבינים בוודאות שמקדם היפוך 1, לא יכול להזיז את הערך 1 מהמקום ההתחלתי שלו P לשום מקום אחר. ולכן כל הערכים של ANS יהיו - 1, כי הערך 1 לא יכול לעבור אליהם. למעט כמובן המיקום ההתחלתי שהוא P.
אז עד עכשיו בדקנו מקדם היפוך K = 1, ב 3 מצבים. במצב של אורך N= 1 אורך N= 2 וגם אורך N = 10, כאשר בפעם האחרונה שיחקנו קצת גם עם המיקום של P ששמנו אותו באמצע המערך.
עכשיו ננסה להעלות עוד קצת רמת הקושי, ונבדוק מה קורה כאשר K = 2, דהיינו, שמקדם ההיפוך הוא 2.
אז לצורך העניין נבדוק את המקרה הבא, שבו N = 2, K = 2 ו P = 0.
במקרה הזה, אנחנו נעשה היפוך באורך 2, של המקומות [0,1] שיהפכו להיות עם הערכים של [1,0] ואז נעביר את הערך 1 מהמיקום ההתחלתי שלו שהוא 0 למיקום החדש שהוא 1.
דהיינו, ANS במקום 0, יהיה 0, כי לא צריך שום היפוך כדי להביא לשם את הערך 1.
אבל ANS במיקום 1, יהיה 1, כי צריך פעולת היפוך 1 באורך 2, כדי להעביר לשם את הערך 1, מהמיקום 0 אל המיקום 1 כמו שניתן לראות בתמונה.
ועכשיו נעלה את רמת הקושי, למקרה ש N = 10 ונקבל את המקרה הבא:
ואם לצורך העניין N = 10, K = 2 אבל P = נניח 5, אז נקבל את התוצאה הבאה, אם נעשה היפוכים ימינה:
וגם את התוצאה הבאה, אם נעשה היפוכים שמאלה:
בקיצור, עד כה הבנו, שמקדם K=1, לא מצליח להעביר את המיקום של ה P ממקום למקום
ומקדם K=2, מעביר ממקום למקום את המיקום ההתחלתי של P, בדילוגים של מקום 1 בכל פעם.
ועכשיו כמובן ננסה להבין את K=3 ונבדוק את המקרה הבא, כאשר P=5:
ועכשיו אני ממליץ לקורא לבדוק עוד מקרים נוספים, למרות שאני מקצר כאן את התהליך ומתקדם למסקנות שעדיין אולי לא ברורות מאליהן. אבל מי שיבדוק עוד מקרים כאשר K=3 וישנה בכל פעם את הערך של P, אז הוא יראה תופעה מעניינת שקורית כאשר K=3.
כי נראה שכאשר K = 3, הרי שיש היפוכים של 3, שלא מזיזים את הערך 1 ממקום למקום. וכאשר K=3, הרי שהערך 1 יכול לזוז רק בדילוגים של 2 מקומות.
דהיינו, עד כה הבנו, שכאשר K=1 אז הערך P לא יכול לזוז ממקום למקום. וכאשר K=2, אז הערך P יכול לזוז לכל מקום, בדילוגים של צעד 1 בכל פעם. וכאשר K=3, אז יש מקומות שאליהם לא ניתן להזיז את הערך P. כי הערך P יכול לזוז רק ב 2 דילוגים, אבל הוא לא יכול באמצעות מקדם K=3, לעבור מקום 1 ימינה או שמאלה.
ועכשיו ננסה לבדוק את K=4 כאשר N=14 ונקבל את זה:
אני מדגיש, כי לא הבאתי כאן את כל האפשרויות האפשריות, אלא רק את האפשרויות הטובות ביותר, כדי לקדם את הערך P ממקום למקום.
ונוכל לראות, כי כאשר K=4, אנחנו יכולים להעביר את P מכל מקום לכל מקום, רק השאלה היא, תוך כמה מינימום מהלכים.
איך לבדוק חוקיות של תהליכים?
אני מדגיש שכאשר אנחנו מנסים לבדוק חוקיות של תהליכים, אנחנו צריכים להתעלם ממקרי קצה ולנסות להבין רק את המקרה הכללי בלבד. דהיינו,, לא לנסות להבין מיד את החוקיות בכל המקרים האפשריים, אלא לנסות קודם כל להבין את החוקיות של המקרים הנפוצים ביותר.
לדוגמה, כאשר N=3, אז אם המקדם K=4, הרי שהוא לא יכול להזיז את הערך P ממקום למקום. או בכל מקרה שהערך K קטן מהערך N, הרי שזה נחשב למקרה קצה. או במילים אחרות, צריכים לנסות להבין את החוקיות, במקרה הכללי, לפני שמנסים להבין את החוקיות בכל מקרה הקצה האפשריים.
ואם נבדוק את K=5, נגלה שיש בו תופעה דומה לכאשר K=3 או כאשר נבדוק גם את K=7 או כאשר K=מספר לא זוגי. כי נגלה את החוקיות הבאה:
אם K=מספר לא זוגי, הרי שאין שום אפשרות בעולם להעביר את P ממיקום זוגי למיקום אי זוגי. דהיינו, אם K = מספר אי זוגי, אז, אם הערך ההתחלתי של P הוא מספר זוגי, הרי שאין שום אפשרות להעביר את P למיקום אי זוגי. ואם הערך ההתחלתי של P הוא מספר אי זוגי, הרי שלא משנה מה, תמיד P יישאר במספר אי זוגי ולא יעבור למיקום זוגי.
ואם נמשיך לבדוק את K=6 או K=8 וכולי, נראה שברמה העקרונית (דהיינו לאו דווקא בכל מקרי הקצה), הרי שניתן להזיז את P מכל מקום לכל מקום, ממקום זוגי לאי זוגי ולהפך. רק השאלה תהיה מהי הדרך היעילה והמהירה ביותר להזיז את הערך P ממקום למקום.
אז מה הבנו עד כה לגבי חוקיות של התהליך?
אז הבנו ש K=1, לא מזיז את P לשום מקום.
ו K=מספר זוגי, יכול להזיז את P לכל מקום.
ואם K=אי זוגי, הרי שP חייב להישאר על זוגי / אי זוגי, בהתאם לנקודת ההתחלה שלו.
ואם K=מספר זוגי, הרי שניתן במהלך אחד להזיז את P ל K מקומות אפשריים (במידה ו N לא מגביל אותנו).
ואם K = אי זוגי, הרי שניתן במהלך אחד להזיז את P, ל / 2(K+1) מקומות.
דהיינו, בכל מקרה:
אם K= מספר כלשהו, אז הרי שבהיפוך 1, ניתן להזיז את הערך P, ללא יותר מ K מקומות.
אם K=2, אז במהלך של היפוך 1, נוכל להזיז את P ללא יותר מ 2 מקומות.
ואם K = 4, הרי שיש רק 4 אפשרויות שאליהם ניתן להזיז את P, בהיפוך 1.
ואם K = 3, הרי שניתן להזיז את P בהיפוך 1 רק ל 2 מקומות בלבד.
או אם K = 5, הרי שניתן להזיז את P בהיפוך 1 ל 3 מקומות בלבד.
ואם K = 99, אז בהיפוך 1 ניתן להזיז את P ל 50 מקומות בלבד.
ואם K = 200, אז ניתן להזיז את P במהלך 1 ל 200 מקומות.
והכל כמובן במקרה הכללי, דהיינו, שאין חסימת ומגבלת מיקום מצד ימין או שמאל, שמגבילה את ההיפוך האפשרי.
ובעצם עד כאן, הבנו קצת או אולי אפילו המון, את החוקיות של ההיפוכים האפשריים.
ואחרי שהבנו את כל זה, עכשיו ננסה להבין, לגבי המקרה הכללי, מה בטוח נכון? האם יש משהו שהוא בטוח נכון?
וכמובן שאנחנו נתעלם מהערכים של Banned שהם מגבילים את התנועה של P. וננסה לפתור את השאלה, בהנחה שאין שום ערכים חסומים כלשהם.
אז מה בטוח נכון?
אז כבר יש כמה דברים שהם בטוח נכונים, לדוגמה, שאם 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 היפוכים וכולי, ואין שום אפשרות להגיע למיקום 18 בפחות מ 6 היפוכים.
ובדוגמה שהבאתי, אנחנו עושים את כל ההיפוכים ימינה. אבל כמובן שצריכים לעשות את זה גם שמאלה, במידה ויש להיכן להפוך שמאלה בהתאם למקרה שמביאים לנו.
או במילים אחרות, יש מיקומים מסויימים, שאנחנו יכולים להגיע אליהם בהיפוך 1 או ב 2 היפוכים או 10 היפוכים. והמשימה שלנו היא לדעת מהו המינימום היפוכים האפשרי, להגיע לכל נקודה.
אבל אם מראש נסמן את המיקום הרחוק ביותר ימינה, שניתן להגיע בהיפוך 1 ימינה, אז משם נוכל לדעת בוודאות, שמכאן ואילך ימינה, אפשרי להגיע רק ב 2 היפוכים ומעלה. ואחר כך נסמן שוב ימינה את הנקודה הרחוקה ביותר שאפשרי להגיע אליה עם 2 היפוכים ימינה. ונדע בוודאות, שאין שום אפשרות להגיע ימינה ממנה, בפחות מ 3 היפוכים וכולי.
דהיינו, השלב הראשון בלפתור את התרגיל, הוא לרוץ על המערך ANS החל מנקודת ההתחלה של P לכיוון ימינה ו/או שמאלה (במידה ואפשרי לרוץ ימינה או שמאלה על הרשימה בהתאם) בדילוגים בגודל של K-1, ולסמן בסדר עולה 1-2-3 וכולי. דהיינו, קודם כל לנסות לסמן בתוך ANS את המקומות שבטוח נכונים שאליהם בוודאות לא ניתן להגיע בפחות מ X דילוגים ימינה או שמאלה.
ואם תוך כדי שאנחנו עושים דילוג ימינה, אנחנו מגיעים לתוך מקום שנמצא בו הערך Banned, דהיינו, שלא ניתן להגיע אליו, אז ניקח מיקום 1 שמאלה דהיינו, K-2 וכולי. ומשם נמשיך לדלג ימינה. ואם גם בו יש Banned אז נחזור עוד צעד אחד אחורה וכולי, עד שנגיע למצב שנדע בוודאות שלא ניתן לדלג יותר ימינה.
דהיינו, אם יש רצף של מקומות חסומים, שהם באורך (K-1), הרי שברגע שנגיע אליהם, לא נוכל יותר לזוז משם ימינה או שמאלה בהתאם ומשם ואילך הכל יהיה - 1 בהתאם.
ובמידה ועד כה פעלנו תקין לפי ההוראות הקודמות, הרי שכרגע יש לנו פרישה ימינה ושמאלה, מנקודת ה P על עבר 2 הקצוות, של עוגנים ונקודות של וודאות, שבכל נקודה אנחנו יודעים בוודאות שלא ניתן להגיע אליה, בפחות היפוכים מהערך שכתוב בה.
כי כמו שאמרנו בדוגמה הקודמת, אנחנו יודעים בוודאות, שאין שום אפשרות בעולם להגיע למיקום 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 הוא אי זוגי, אז יהיה עוד יותר קל לפתור את זה. ואם K הוא זוגי, גם קל לפתור את זה, אבל קצת יותר ארוך.
ובעצם זה אומר, שעכשיו אנחנו צריכים להבין את החוקיות של התזוזה בתוך K עצמו בלבד. בלי קשר לנקודת ההתחלה של P.
דהיינו, אנחנו צריכים להבין, במידה ולדוגמה K=11. תוך כמה היפוכים ניתן להגיע ממיקום 1 למיקום 3-5-7-9. ואם K = 6, אנחנו צריכים להבין תוך כמה היפוכים אפשרי להגיע ממיקום 1 למיקום 2-3-4-5. כי אלו בעצם הטווחים שאליהם אנחנו רוצים להגיע בתוך הוודאות שמצאנו קודם.
בקיצור... את ההמשך, נסו לגלות לבד.
סיכום:
לקחנו שאלה שנחשבת לדי מסובכת, שגם להבין אותה די קשה, בגלל שהיא מנוסחת בצורה די קלוקלת. מפה לשם ניסינו להבין את החוקיות של התהליך וגילינו שיש כאן חוקיות. מפה לשם הפתרון במהותו הוא, לסמן קודם כל את כל נקודות הוודאות לגבי הנקודות הרחוקות ביותר שאליהן צריך לפחות X היפוכים. והכל בהתאם למיקומים חסומים. ומכאן ואילך עלינו רק לסמן את המיקומים שבין המיקומים הוודאיים שאנחנו כבר יודעים אותם.
בהצלחה.
050-3331-331