Μηνιαία Πρόκληση: Απρίλιος 2021

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
_kountardas
Δημοσιεύσεις: 6
Εγγραφή: Δευ Φεβ 01, 2021 6:25 pm

Μηνιαία Πρόκληση: Απρίλιος 2021

Δημοσίευση από _kountardas »

Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση.

Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς.

Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε 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
Έξοδος
6

Το ζευγάρια που ικανοποιούν τους περιορισμούς είναι τα 1-1, 1-2, 2-2, 3-3, 4-4, 5-5.

Στις 28 του μηνός θα δώσουμε ένα hint, θυμίστε το μας αν το ξεχάσουμε.

Καλή επιτυχία!


Υ.Γ : Συγγνώμη για την καθυστέρηση, θεωρήσαμε ότι ήταν καλύτερο να ανέβει μετά την Γ φάση :D
_kountardas
Δημοσιεύσεις: 6
Εγγραφή: Δευ Φεβ 01, 2021 6:25 pm

Re: Μηνιαία Πρόκληση: Απρίλιος 2021

Δημοσίευση από _kountardas »

Hint 1:
Spoiler: show
Σχετικά με το XOR ανάμεσα σε κόμβους μπορούμε να αποδείξουμε και να χρησιμοποιήσουμε τα εξής:
  • x XOR y = y XOR x
  • (x XOR y) XOR z = x XOR (y XOR z)
  • x XOR y = x αν και μόνο αν y=0

Επίσης καλό είναι να πούμε ότι, προγραμματίστηκε η μηνιαία συνάντηση στο zoom για το Σάββατο 15 Μαΐου, ώστε να προλάβουν να δούνε το πρόβλημα όσοι συμμετείχαν στο καμπ.

Kατά προτίμηση να κατεβάσετε την εφαρμογή του zoom σε περίπτωση που χρειαστεί να δείξετε κάτι στον πίνακα, μιας που δεν μπορείτε από την browser εφαρμογή.

Τα στοιχεία για το meeting θα ανέβουν αυτό το Σάββατο μαζί με το δεύτερο hint!
Απάντηση