חייב עזרה דחוף

[lebron james2]

חייב עזרה דחוף

http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/

אני פשוט לא מצליח להבין, למה [S[j הוא המינימום מבין 3 האיברים שכתובים בנוסחה שבפתרון שם.

מאד אודה למי שיוכל להסביר את זה כי אני לא מבין איך אני אמור להסתכל על זה באופן כזה שיגרום לי להבין למה זה נכון, או לפחות להשתכנע במידה מסויימת שזה אכן נכון.

 

[אורי769]

הדרכה

s[j] = k אם הריבוע בגודל k שפינתו i,j הוא כולו אחדים ושכל ריבוע כזה הגדול מ-k יכיל איפשהו 0.
עכשיו אתה רוצה להוכיח
s[j] = min(s[i-1][j], s[i,j-1], s[i-1][j-1]) + 1
תוכיח אי-שוויון בשני הכיוונים
s[j] =< min(s[i-1][j], s[i,j-1], s[i-1][j-1]) + 1
s[j] >= min(s[i-1][j], s[i,j-1], s[i-1][j-1]) + 1

 

[lebron james2]

ניסיון

אנסה להוכיח: s[j] =< min(s[i-1][j], s[i,j-1], s[i-1][j-1]) + 1

נניח ש-[S[j גדול ממש מצד ימין.
נסמן: S[j]=t, כאשר t מספר כלשהו.
כלומר, הריבוע בגודל t שפינתו i,j הוא כולו 1-ים וכל ריבוע כזה הגדול מ-t יכיל איפשהו 0.

כעת,אם בה"כ המינימום מבין השלושה ביטויים בצד ימין הוא [s[i-1][j למשל, ונניח שערכו הוא מספר כלשהו p.
אזי הריבוע בגודל p שפינתו i-1,j, הוא כולו אחדים וכל ריבוע כזה הגדול מ-p יכיל
איפשהו 0.
מההנחה, t גדול ממש מצד ימין ולכן t>p+1.
האם כעת אני יכול להסיק שפירוש הדבר הוא ש- [s[j הוא ריבוע כנדרש על פי הגדרת [s[j, כפי שכתבת בשורה הראשונה של ההודעה שלך, אשר צלעו היא לפחות באורך p+2, ומכאן להסיק שיש ריבוע שפינתו i-1,j שכולו 1-ים, ושהוא גדול ממש מ-p? סתירה להגדרת [s[i-1][j...?

האם ההוכחה הזו נכונה?
ולגבי השימוש ב"בלי הגבלת הכלליות"...האם אני אכן לא מגביל את הכלליות כשאני בוחר את אחד מבין השלושה להיות מינימלי? אני לא כל כך בטוח לגבי זה.


אנסה להראות גם תכיוון השני:
s[j] >= min(s[i-1][j], s[i,j-1], s[i-1][j-1]) + 1

נניח שצד שמאל קטן ממש מצד ימין. כמו קודם, אסמן s[j]=t.
הפעם, נניח למשל שהמינימום מבין השלושה הוא דווקא [s[i-1][j-1.
ונניח שערכו הוא מספר p כלשהו.

מההנחה, t קטן ממש מצד ימין. כלומר t<p+1. לכן t קטן או שווה ל-p.
אמממ..כאן האמת אני לא רואה את הסתירה מגיעה.. :/
רגע.
בעצם הצלע של [s[j שהיא t, קטנה שווה ל-p.
אבל הריבועים [s[i+1][j ו- [s[j-1, מאחר והם גדולים (או שווים) מ-[s[i-1][j-1,
הרי שהצלע של כל אחד מהם היא לפחות p, ואז זה אומר שיש ריבוע שכולו 1-ים,
שפינתו i,j, ושצלעו גדולה מ-t, בסתירה להגדרת s[j]?

אודה על תגובתך:>
לילה טוב !

 

[אורי769]

תשובות

החלק הראשון בסה"כ בסדר. בהקשר של הגבלת הכלליות, יש סימטריה ברורה בין [s[j-1 לבין [s[i-1][j. לכן לא צריך לדון בשני המקרים האלה במלואם אלא מספיק אחד. לא כך לגבי [s[i-1][j-1.
לגבי החלק השני... נראה לי שהסתבכת שלא לצורך. לא צריך שלילה. מה זה אומר ש-
min(x,y,z) >= 6? זה אומר ששלושתם הם לפחות 6. ובהשאלה למקרה שלך, צד ימין של אי השוויון נותן חסם תחתון לגודל של ריבוע אחדים שבטוח קיים.

 

[lebron james2]

תודה רבה..אגב

האמת היא שכזכור צרפתי לינק עם הפתרון לשאלה הזו.
ואז כשנתת לי את ההדרכה, פשוט הלכתי על הוכחה פורמלית שלה וראיתי שזה יוצא בסדר ואכן הטענה נכונה.

האמת שבהדרכה שלך הגדרת בצורה מדוייקת את sij ואת מה שאני צריך להוכיח וזה מאד עזר.
העניין הוא שהשלב העוד יותר מוקדם לא הגעתי אליו...לא הגעתי לאינטואיציה שsij הוא באמת המינימום מבין השלושה ועוד 1.
לא ממש רואה איך מגיעים לזה..עזוב שאחרי ההוכחה הפורמלית ברור שזה נכון..
כשאתה ראית את השאלה, היה ברור לך שsij הוא באמת המינימום מבין השלושה ועוד 1? אם כן, מה הייתה בערך האינטואיציה לזה?

 

[אורי769]

האינטואיציה

כדי ש-s[j] = k צריך לדאוג שהריבוע בגודל k "מעליו" יהיה כולו אחדים. זה ש-
s[j-1] >= k-1
s[i-1][j] >= k-1
"דואג" לכך שיהיו k-1 אחדים בעמודה מעל i,j ובשורה ששמאל.
s[i-1][j-1] >= k-1
"דואג" לשאר הריבוע.