חידה לסופ"ש

[אורי769]

חידה לסופ"ש

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

יש לנו טבלה גדולה עם N שורות ו-K עמודות. אנו נדרשים למלא את הטבלה לפי שני הכללים הבאים:

1. שמים בתא (i,j) מספר רק אחרי ששמנו מספר בכל התאים שהם גם בשורה שלו או מעל וגם בעמודה שלו או משמאל. או באופן יותר מפורש, בכל תא (s,t) כך ש-s<=i וגם t<=j
2. בתא ה-(i,j) שמים את המספר הטבעי (כולל 0) הקטן ביותר שלא נמצא כבר מעליו באותה העמודה או משמאלו באותה השורה. לדוגמא, אם בעמודה מעל כבר יש 1 ו-3 ובשורה משמאל כבר יש 0 ו-5 אז 2 הוא הקטן ביותר שעוד לא מופיע.

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

 

[אורי769]

פתרון

אם נמספר את העמודות והשורות מ-0 והלאה, אז הערך בעמודה n,m יהיה n XOR m, כאשר n,m מיוצגים בבסיס בינארי והפעולה היא על כל ספרה. לדוגמא, אם n=6 m=5 אז בבינארי n=110 ו-m=101 ולכן n XOR m = 011 = 3.

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

תודה לעריסטו על הפתרון. אני מקווה שמי שעוד ניסה לפתור לפחות נהנה מהתהליך יש לי עד יום ה' הבא לחשוב על חידה אחרת...

 

[מiטקה]

אפשר הסבר?

אני שובר את הראש, רואה את ההקשר לחזקות של 2 אבל לא מבין איך xor פתאום מסביר הכל.