... Banned. You can perform multiple operations on arr. אתה יכול לבצע פעולת הכפלה היפוך על המערך ARR. צריך לשים לב, שלמילה multiple יש כל מיני פירושים
אפשריים. אחד מהקשיים להבין את השאלה, נובע מכך שלמילה הזאת יש כל מיני פירושים
אפשריים. הפירוש הנכון כאן, הוא שאתה יכול לבצע פעולת הכפלה היפוך על המערך ARR כדלקמן. In an operation, you can ... and reverse the subarray. בכל פעולת היפוך, אתה יכול לבחור תת מערך, באורך K ולהפוך אותו בתוך המערך ARR. דהיינו, נתון לנו גם משתנה K, שמייצג את האורך
האפשרי של תת המערך
שאפשרי לבצע עליו היפוך. ואנחנו יכולים לקחת מקטע תת מערך מתוך המערך ARR, שתת המקטע יהיה באורך K. ואנחנו יכולים ... מהמיקום 3 למיקום 4. וכן על זה הדרך, ניתן לבצע את ההיפוך הבא: וגם את ההיפוך הבא: וכן על זה הדרך, ניתן להמשיך ולמלא את כל שאר האפשרויות של כל ההיפוכים
האפשריים וכולי. A subarray is a contiguous non-empty sequence of elements within an array. The values of ... את השאלה, במקרה פשוט שבו אין ערכים של Banned כלשהם. כי תמיד צריכים להתחיל מהמקרה הפשוט ביותר, דהיינו, בלי Banned. ועכשיו אני אעשה דילוג קטן, לכיוון
אפשרי לפתור את הבעיה הזאת, ואחר כך אסביר איך באמת לגשת לפתרון של הבעיה הזאת. אז לכאורה הדרך לפתרון היא פשוטה ביותר. עלינו לקחת את המערך ARR ואת הערך K ולסמן את כל ההיפוכים
האפשריים שאפשרי לעשות על המערך ARR, היפוכים באורך K. ולסמן אחרי כל היפוך, היכן יהיה הערך 1. ועלינו לבדוק את כל האפשרויות
האפשריות של לעשות כל היפוך באורך K על המערך ARR. ואחרי הכל עלינו לראות היכן נמצא הערך 1. ועלינו לבדוק, מה היה מינימום ההיפוכים
האפשריים, כדי להביא לשם את הערך 1. דהיינו, בדוק את כל האפשרויות
האפשריות להעביר את 1 ממקום למקום. ואז תראה מהי הדרך הקצרה ביותר להעביר את 1 ממקום למקום. והשיטה הזאת, כמובן ... אבל כמובן גם שהיא לא יעילה לחלוטין. כי אם ניקח לדוגמה מערך באורך 1,000,000 ונניח ש K הוא 6, ונניח ש P = 546. אז כמות האפשרויות לבדוק את כל האפשרויות
האפשריות, היא מאוד גדולה וכולי. ולכן כמובן שאנחנו מחפשים פתרון יותר יעיל וקצר. אז איך ניגשים לנתח את השאלה ... והמטרה כאן, היא להרגיל את המוח, לפרק את התהליך לחלקים קטנים, כדי להתרגל לחלק לחלקים קטנים, שאז ומתוך זה, המוח יבין מה בטוח נכון, החלק הכי קטן. וכך
אפשרי למצוא את התשובה הפשוטה לשאלה הגדולה. אז לשם כך נתחיל בלנתח את המקרה הפשוט ביותר, רק כדי להבין קצת את ... לא יכול באמצעות מקדם K=3, לעבור מקום 1 ימינה או שמאלה. ועכשיו ננסה לבדוק את K=4 כאשר N=14 ונקבל את זה: אני מדגיש, כי לא הבאתי כאן את כל האפשרויות
האפשריות, אלא רק את האפשרויות הטובות ביותר, כדי לקדם את הערך P ממקום למקום. ונוכל לראות, כי כאשר K=4, אנחנו ... מנסים לבדוק חוקיות של תהליכים, אנחנו צריכים להתעלם ממקרי קצה ולנסות להבין רק את המקרה הכללי בלבד. דהיינו,, לא לנסות להבין מיד את החוקיות בכל המקרים
האפשריים, אלא לנסות קודם כל להבין את החוקיות של המקרים הנפוצים ביותר. לדוגמה, כאשר N=3, אז אם המקדם K=4, הרי ... שהערך K קטן מהערך N, הרי שזה נחשב למקרה קצה. או במילים אחרות, צריכים לנסות להבין את החוקיות, במקרה הכללי, לפני שמנסים להבין את החוקיות בכל מקרה הקצה
האפשריים. ואם נבדוק את K=5, נגלה שיש בו תופעה דומה לכאשר K=3 או כאשר נבדוק גם את K=7 או כאשר K=מספר לא זוגי. ... את P לכל מקום. ואם K=אי זוגי, הרי שP חייב להישאר על זוגי אי זוגי, בהתאם לנקודת ההתחלה שלו. ואם K=מספר זוגי, הרי שניתן במהלך אחד להזיז את P ל K מקומות
אפשריים (במידה ו N לא מגביל אותנו). ואם K = אי זוגי, הרי שניתן במהלך אחד להזיז את P, ל 2(K+1) מקומות. דהיינו, ... ואם K = 200, אז ניתן להזיז את P במהלך 1 ל 200 מקומות. והכל כמובן במקרה הכללי, דהיינו, שאין חסימת ומגבלת מיקום מצד ימין או שמאל, שמגבילה את ההיפוך
האפשרי . ובעצם עד כאן, הבנו קצת או אולי אפילו המון, את החוקיות של ההיפוכים
האפשריים. ואחרי שהבנו את כל זה, עכשיו ננסה להבין, לגבי המקרה הכללי, מה בטוח נכון? האם יש משהו שהוא בטוח נכון? ... אליו בהיפוך 1. דהיינו, נדע בוודאות, שאין שום אפשרות להגיע יותר רחוק בהיפוך 1. ואת המיקום שהגענו אליו, גם אותו נהפוך בעוד היפוך 1, למיקום הרחוק ביותר
שאפשרי להגיע ב 2 היפוכים וכך הלאה. כי אנחנו יודעים בוודאות, שאין שום אפשרות בעולם להגיע למיקום 3 בפחות מ 1 ... או במילים אחרות, יש מיקומים מסויימים, שאנחנו יכולים להגיע אליהם בהיפוך 1 או ב 2 היפוכים או 10 היפוכים. והמשימה שלנו היא לדעת מהו המינימום היפוכים
האפשרי, להגיע לכל נקודה. אבל אם מראש נסמן את המיקום הרחוק ביותר ימינה, שניתן להגיע בהיפוך 1 ימינה, אז משם נוכל לדעת בוודאות, שמכאן ואילך ימינה,
אפשרי להגיע רק ב 2 היפוכים ומעלה. ואחר כך נסמן שוב ימינה את הנקודה הרחוקה ביותר
שאפשרי להגיע אליה עם 2 היפוכים ימינה. ונדע בוודאות, שאין שום אפשרות להגיע ימינה ממנה, בפחות מ 3 היפוכים וכולי. דהיינו, השלב הראשון בלפתור את התרגיל, הוא לרוץ על המערך ANS החל מנקודת ההתחלה של P לכיוון ימינה ו או שמאלה (במידה
ואפשרי לרוץ ימינה או שמאלה על הרשימה בהתאם) בדילוגים בגודל של K-1, ולסמן בסדר עולה 1-2-3 וכולי. דהיינו, קודם ... 18 למיקום 19 או 20. ולמיקום 18, אנחנו כבר יודעים שבוודאות צריך 6 היפוכים. או אם נסתכל על מיקום 10 או 11, אנחנו לא צריכים לנסות להבין בכמה היפוכים
אפשרי להגיע לשם ממיקום P=0. אלא אנחנו ננסה להבין מהי הדרך הקצרה ביותר להגיע אליהם ממקום 9 שאליו צריך 3 ... P. דהיינו, אנחנו צריכים להבין, במידה ולדוגמה K=11. תוך כמה היפוכים ניתן להגיע ממיקום 1 למיקום 3-5-7-9. ואם K = 6, אנחנו צריכים להבין תוך כמה היפוכים
אפשרי להגיע ממיקום 1 למיקום 2-3-4-5. כי אלו בעצם הטווחים שאליהם אנחנו רוצים להגיע בתוך הוודאות שמצאנו קודם. ...