Just a Girl

הבוטקה הזה במקרה פתוח גם ביום שישי? או שאני אופטימית מדי?

תודה לכולם על התגובות

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

מישהו יודע איך ואיפה מוציאים מדבקה לרכב? לא מצאתי שום דבר רשמי, והלינק שאמור לעסוק בזה שבור/סתם לא טרחו ליצור אותו: http://bitahon.technion.ac.il/ תודה

חשבתי להשתמש באלגוריתמים שלמדנו בכיתה, כמו פרים/קרוסקל, ולחסוך את המיון של הקשתות שעולה לנו ElogE. במקרה הזה, מיון של הקשתות לשתי קבוצות יעלה רק E. אבל בשניהם יש גם את השלב הבא (בקרוסקל Union-Find ובפרים ערימת מינימום), שממנו אני לא ממש מצליחה להמנע.... כלומר, אני לא מצליחה לחסוך פרט לעניין המיון, אבל נראה שזה לא עוזר לי הרבה....

אני מתקשה מאוד עם שאלה 2: נתון גרף ממושקל G=(V,E) שבו משקל כל קשת הוא 1 או 2. הציעו אלגוריתם המוצא עפ"מ בזמן O(V+E). אין לי ממש כיוון. חשבתי על BFS או DFS, אבל אני לא חושבת שזה יעזור לי איכשהו, כי גם אם אני אשנה את האלגוריתם איכשהו אני אצטרך להוכיח שהעץ שקיבלתי הוא מינימום, וזה נראה לי בכלל בכלל לא טריויאלי, כמו שההוכחה של DFS ו-BFS לא טריויאלית. להשתמש בקרוסקל או פרים - אני חושבת שזה בעייתי מבחינת הסיבוכיות (אגב, מה יותר גדול? E+V או ElogV? אני מניחה מהשאלה ש-ElogV, אחרת אפשר לפתור את זה עם קרוסקל/פרים, אבל לא ממש ברור לי למה...) בקיצור, אין לי ממש כיוון, אז אשמח לעזרה, כי ההגשה למחר בלילה.... תודה! :)