Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς.
Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου στο τέλος του μήνα θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Σημείωση: Ένας από τους συμμετέχοντες της σύσκεψης θα επιλέγεται ώστε να βοηθήσει τον Βαγγέλη με την επόμενη μηνιαία πρόκληση, αυτή του Μαΐου εν προκειμένω.
Οι αρμοδιότητές του θα είναι να λύσει το επόμενο πρόβλημα εντός του μήνα (εννοείται με συνεννόηση/βοήθεια από τον Βαγγέλη) ώστε να είναι σε θέση να λύνει απορίες στην επόμενη σύσκεψη και στο forum.
(Και πάλι, εννοείται θα είναι κι o Βαγγέλης στη σύσκεψη, οπότε δεν αγχωνόμαστε "Τι θα γίνει αν δε μπορώ να απαντήσω σε κάποια ερώτηση;").
Από τη σύσκεψη Μαρτίου έχει επιλεγεί ήδη ο Άκης(εγώ) ως βοηθός Απριλίου.
Σε αυτό το πρόβλημα μας δίνεται ένα δέντρο όπως αυτό της εικόνας.
(https://i.imgur.com/wnh5hGc.png)
Στο συγκεκριμένο πρόβλημα πρέπει να βρούμε πόσα ζευγάρια με πατρογονική σχέση κάνουν XOR μεταξύ τους και μας βγάζει 0.
To XOR είναι μία πράξη που γίνεται ανάμεσα σε δύο δυαδικούς αριθμούς σε ζευγάρια παράδειγμα:
(https://i.imgur.com/kYSrWXt.png)
Δηλαδή όπου στον πρώτο δυαδικό υπάρχει 0 και στον δεύτερο 1 (ή αντίστροφα) το αντίστοιχο ψηφίο στο αποτέλεσμα γίνεται 1.
Άν όμως έχουμε και στους δύο δυαδικούς την ίδια τιμή, τότε το αντίστοιχο ψηφίου στο αποτέλεσμα γίνεται 0.
Εμείς ψάχνουμε όλα τα ζευγάρια με πατρογονική σχέση που όταν κάνουμε XOR αυτά και όλες τις τιμές ενδιάμεσα(για να φτάσουμε από τον έναν κόμβο στον άλλο), παίρνουμε αποτέλεσμα 0.
Στην είσοδο θα μας δίνεται το Ν (πλήθος κόμβων). Ακολουθούν Ν-1 δυάδες αριθμών . Ο πρώτος αριθμός της i-οστής δυάδας είναι ένας κόμβος-πατέρας u, ο δεύτερος είναι ένας κόμβος-παιδί v.
Στην τελευταία γραμμή υπάρχουν όλες οι τιμές που θα πάρουν οι αντίστοιχοι κόμβοι. Για παράδειγμα ο πρώτος αριθμός της τελευταίας γραμμής είναι η τιμή του κόμβου με αναγνωριστικό 1.
Ζητείται αλγόριθμος είτε O(N), είτε Ο(NlogN), είτε Ο(Ν^2) είτε O(N^3).
Παράδειγμα (ίδιο με την εικόνα) :
5
1 2
2 3
2 4
1 5
1 1 7 4 10
Έξοδος
1
Το ζευγάρια που ικανοποιούν τους περιορισμούς είναι μόνο το 1-2.
Στις 28 του μηνός θα δώσουμε ένα hint, θυμίστε το μας αν το ξεχάσουμε.
Καλή επιτυχία!
Υ.Γ : Συγγνώμη για την καθυστέρηση, θεωρήσαμε ότι ήταν καλύτερο να ανέβει μετά την Γ φάση
