Κάθε αρχή του μήνα θα ανεβαίνει στο 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
Έξοδος
1
Το ζευγάρια που ικανοποιούν τους περιορισμούς είναι μόνο το 1-2.
Στις 28 του μηνός θα δώσουμε ένα hint, θυμίστε το μας αν το ξεχάσουμε.
Καλή επιτυχία!
Υ.Γ : Συγγνώμη για την καθυστέρηση, θεωρήσαμε ότι ήταν καλύτερο να ανέβει μετά την Γ φάση
Μηνιαία Πρόκληση: Απρίλιος 2021
-
- Δημοσιεύσεις: 9
- Εγγραφή: Δευ Φεβ 01, 2021 6:25 pm
-
- Δημοσιεύσεις: 9
- Εγγραφή: Δευ Φεβ 01, 2021 6:25 pm
Re: Μηνιαία Πρόκληση: Απρίλιος 2021
Hint 1:
Επίσης καλό είναι να πούμε ότι, προγραμματίστηκε η μηνιαία συνάντηση στο zoom για το Σάββατο 15 Μαΐου, ώστε να προλάβουν να δούνε το πρόβλημα όσοι συμμετείχαν στο καμπ.
Kατά προτίμηση να κατεβάσετε την εφαρμογή του zoom σε περίπτωση που χρειαστεί να δείξετε κάτι στον πίνακα, μιας που δεν μπορείτε από την browser εφαρμογή.
Τα στοιχεία για το meeting θα ανέβουν αυτό το Σάββατο μαζί με το δεύτερο hint!
- Spoiler: show
Επίσης καλό είναι να πούμε ότι, προγραμματίστηκε η μηνιαία συνάντηση στο zoom για το Σάββατο 15 Μαΐου, ώστε να προλάβουν να δούνε το πρόβλημα όσοι συμμετείχαν στο καμπ.
Kατά προτίμηση να κατεβάσετε την εφαρμογή του zoom σε περίπτωση που χρειαστεί να δείξετε κάτι στον πίνακα, μιας που δεν μπορείτε από την browser εφαρμογή.
Τα στοιχεία για το meeting θα ανέβουν αυτό το Σάββατο μαζί με το δεύτερο hint!
-
- Δημοσιεύσεις: 9
- Εγγραφή: Δευ Φεβ 01, 2021 6:25 pm
Re: Μηνιαία Πρόκληση: Απρίλιος 2021
Hint 2:
- Spoiler: show
- Χίλια συγγνώμη για την καθυστέρηση ελπίζω να φανεί χρήσιμο
- Η ώρα και τα στοιχεία του meeting θα ανέβουν λογικά Σάββατο ή Παρασκευή
-
- Δημοσιεύσεις: 9
- Εγγραφή: Δευ Φεβ 01, 2021 6:25 pm
Re: Μηνιαία Πρόκληση: Απρίλιος 2021
Καλησπέρα, προγραμματίστηκε το meeting για αύριο στις 17:00.
Kατά προτίμηση να κατεβάσετε την εφαρμογή του zoom σε περίπτωση που χρειαστεί να δείξετε κάτι στον πίνακα, μιας που δεν μπορείτε από την browser εφαρμογή.
Στοιχεία σύνδεσης στο zoom meeting:
https://ucph-ku.zoom.us/j/68657651872?p ... ZKenM5Zz09
Kατά προτίμηση να κατεβάσετε την εφαρμογή του zoom σε περίπτωση που χρειαστεί να δείξετε κάτι στον πίνακα, μιας που δεν μπορείτε από την browser εφαρμογή.
Στοιχεία σύνδεσης στο zoom meeting:
https://ucph-ku.zoom.us/j/68657651872?p ... ZKenM5Zz09
Re: Μηνιαία Πρόκληση: Απρίλιος 2021
Ερώτηση- απορία , στο παραπάνω τμήμα της εκφώνησης:Εμείς ψάχνουμε όλα τα ζευγάρια με πατρογονική σχέση που όταν κάνουμε XOR αυτά και όλες τις τιμές ενδιάμεσα(για να φτάσουμε από τον έναν κόμβο στον άλλο), παίρνουμε αποτέλεσμα 0.
Αν, στο δέντρο της εικόνας ίσχυε ότι πχ κόμβος 1 ^ κόμβος 3 = 0, θα πρέπει προηγουμένως, ΚΑΙ κόμβος 1^ κόμβος 2 να είναι =0 ; ( «όλες οι ενδιάμεσες τιμές»)
-
- Δημοσιεύσεις: 9
- Εγγραφή: Δευ Φεβ 01, 2021 6:25 pm
Re: Μηνιαία Πρόκληση: Απρίλιος 2021
Εμείς, αυτό που θέλουμε να κάνουμε, είναι xor από την ρίζα προς τα κάτω. Πχ στην ερώτηση που έθεσες θα ψάχναμε κόμβο 1 ^ κόμβο 2 ^ κόμβο 3. Δηλαδή αν ο κόμβος 1 ^ κόμβος 2 έκανε xor με το κόμβο 3 και ήταν ίσον με το 0.Μόνο τότε θα το παίρναμε σωστό.bettypan έγραψε: ↑Σάβ Μάιος 15, 2021 1:23 pmΕρώτηση- απορία , στο παραπάνω τμήμα της εκφώνησης:Εμείς ψάχνουμε όλα τα ζευγάρια με πατρογονική σχέση που όταν κάνουμε XOR αυτά και όλες τις τιμές ενδιάμεσα(για να φτάσουμε από τον έναν κόμβο στον άλλο), παίρνουμε αποτέλεσμα 0.
Αν, στο δέντρο της εικόνας ίσχυε ότι πχ κόμβος 1 ^ κόμβος 3 = 0, θα πρέπει προηγουμένως, ΚΑΙ κόμβος 1^ κόμβος 2 να είναι =0 ; ( «όλες οι ενδιάμεσες τιμές»)