מי שמכיר את הטריק - שלא יקפוץ בבקשה ויתן לאחרים לשבור קצת את הראש.
מי שרוצה שישלח לי הודעה פרטית עם פתרונות\שאלות וכו' ואני אשתדל לענות.


הבעיה:
כולנו יודעים שכשיוצרים מערך צריך לעבור על כל אחד מהאיברים שלו ולאפס אותו (אחרת מופיע שם זבל לא מוגדר).
פעולה כזו - מעבר בלולאה על כל אחד מאברי המערך - היא פעולה התלוייה בגודל המערך.

המטרה:
ליצור טיפוס מערך שיאותחל בזמן קבוע - שאינו תלוי בגודל המערך, תוך שימוש בתוספת זיכרון אפשרית שלא תעלה על יחס לינארי בגודל המערך (כלומר אם יש מערך בגודל 1000 אזי פתרון שישתמש ב-1000000 זיכרון לא מתקבל על הדעת, אבל 5000 כן.)

למי שקצת מכיר את המושגים:
סיבוכיות זמן: (O(1 לכל הפעולות של המערך - כולל איתחול.
סיבוכיות מקום: (O(n.

בהצלחה

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

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

הייתי רוצה לתת לאחרים לשבור קצת את הראש, אבל אם אתה רוצה, אתה מוזמן לשלוח לי את הפתרון שלך לפרטי ואני אחזיר לך אם לזה הייתה הכוונה ואם אפשר אחרת\טוב יותר

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

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

חבל רק שלא מספיק אנשים ניסו להפעיל את התאים האפורים...

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

השתמשתי בסימון A.member ולא בסימון הרגיל member[A] zz כדי שלא יהיה בלבול..
בכמה מילים:
המערך H2 ממען את האינדקס המבוקש לתא בו הוא באמת נשמר
המערך H1 מאמת את זה (כי יכול להיות מספרים כלשהם בH2)
המערך V מכיל את הערכים האמיתיים
c מאחסן את הערך שעד אליו מולאו H1 ו V
שאר המשתנים די ברורים

כשעושים set לתא i, אם הוא עוד לא נוצר אז יוצרים אותו בתא הפנוי הראשון (שנשמר בc) ואז מקדמים את c, ואחרת מציבים בתא הקיים.
כשעושים get בודקים אם תא i קיים ואם כן מחזירים את ערכו, אם לא מחזירים את הערך שאיתו איתחלו את המערך.

קל לראות שזה אכן O(1) עבור כל הפעולות, ו 3n+3 = O(n) zz מקום.

זה הפיתרון הראשון שקפץ לי לראש, יכול להיות שיש פיתרון טוב יותר (אתה מוזמן לשתף, אם אתה מכיר כזה).

*זה בתמונה כי משום מה FF קורס אצלי כל פעם שאני עושה תצוגה מקדימה לתגובה :O

אני לא יודע אם allocate תלוי ב n אבל פתרון יפה בהתחלה חשבתי שיכול להיות טעויות אם איתחול מסויים של H2 ו H1 אבל לאחר מכן גילתי ש H1 באמת עוזר בעזרת הבדיקה הבאה:

קוד:

x != y
A.H1[A.H2[x]] = x
A.H1[A.H2[y]] = y
If H2[x] and H2[y] are the same (so it will point to the same index)
than 
A.H1[A.H2[x]] = A.H1[A.H2[y]] = y = x
which is not possible.

כש X ו Y זה פרמטר I לפונקציה Set ככה שבשום מצב לא יקרה ש Set I יצביע לאותו תא...

Dark Knight אם שלך שונה אני מעוניין לראות אותו.

Error: Keyboard not found

Press F1 to continue

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

הערה:
בבדיקה בset וget אצלי אמור להיות\

קוד PHP:

 1<=A.H2[i]<=c 


ולא כמו שכתוב:

קוד PHP:

 1<=A.H2[i]<=A.length 


עכשיו ראיתי שהוספת משהו אבל אני לא ממש הבנתי למה אתה מתכוון,אם אתה יכול תסביר.

הייתי מוסיף עוד מתודה של is_garbage ומשתמש בה, אבל ביחד עם התיקון שהוספת - התשובה נכונה ומדויקת

הכרת את הטריק או שפיתחת אותו בעצמך?

בכל אופן - כל הכבוד

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

יום נעים!

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

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


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