Σελίδα 1 από 1

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

Δημοσιεύτηκε: Πέμ Απρ 15, 2021 6:30 pm
από _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
Έξοδος
1

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

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

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


Υ.Γ : Συγγνώμη για την καθυστέρηση, θεωρήσαμε ότι ήταν καλύτερο να ανέβει μετά την Γ φάση :D

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

Δημοσιεύτηκε: Τρί Μάιος 04, 2021 3:55 pm
από _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!

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

Δημοσιεύτηκε: Τετ Μάιος 12, 2021 11:42 pm
από _kountardas
Hint 2:
Spoiler: show
Στο συγκεκριμένο πρόβλημα μπορεί να φανεί χρήσιμη η τεχνική Prefix Sums (πχ από εδώ: https://pdp-archive.github.io/31-PDP/bg ... a-solution ) αν αντί για Sums κάνουμε XOR!
Υ.Γ :
  • Χίλια συγγνώμη για την καθυστέρηση ελπίζω να φανεί χρήσιμο
  • Η ώρα και τα στοιχεία του meeting θα ανέβουν λογικά Σάββατο ή Παρασκευή

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

Δημοσιεύτηκε: Παρ Μάιος 14, 2021 8:46 pm
από _kountardas
Καλησπέρα, προγραμματίστηκε το meeting για αύριο στις 17:00.
Kατά προτίμηση να κατεβάσετε την εφαρμογή του zoom σε περίπτωση που χρειαστεί να δείξετε κάτι στον πίνακα, μιας που δεν μπορείτε από την browser εφαρμογή.

Στοιχεία σύνδεσης στο zoom meeting:

https://ucph-ku.zoom.us/j/68657651872?p ... ZKenM5Zz09

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

Δημοσιεύτηκε: Σάβ Μάιος 15, 2021 1:23 pm
από bettypan
Εμείς ψάχνουμε όλα τα ζευγάρια με πατρογονική σχέση που όταν κάνουμε XOR αυτά και όλες τις τιμές ενδιάμεσα(για να φτάσουμε από τον έναν κόμβο στον άλλο), παίρνουμε αποτέλεσμα 0.
Ερώτηση- απορία , στο παραπάνω τμήμα της εκφώνησης:
Αν, στο δέντρο της εικόνας ίσχυε ότι πχ κόμβος 1 ^ κόμβος 3 = 0, θα πρέπει προηγουμένως, ΚΑΙ κόμβος 1^ κόμβος 2 να είναι =0 ; ( «όλες οι ενδιάμεσες τιμές»)

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

Δημοσιεύτηκε: Σάβ Μάιος 15, 2021 2:55 pm
από _kountardas
bettypan έγραψε: Σάβ Μάιος 15, 2021 1:23 pm
Εμείς ψάχνουμε όλα τα ζευγάρια με πατρογονική σχέση που όταν κάνουμε XOR αυτά και όλες τις τιμές ενδιάμεσα(για να φτάσουμε από τον έναν κόμβο στον άλλο), παίρνουμε αποτέλεσμα 0.
Ερώτηση- απορία , στο παραπάνω τμήμα της εκφώνησης:
Αν, στο δέντρο της εικόνας ίσχυε ότι πχ κόμβος 1 ^ κόμβος 3 = 0, θα πρέπει προηγουμένως, ΚΑΙ κόμβος 1^ κόμβος 2 να είναι =0 ; ( «όλες οι ενδιάμεσες τιμές»)
Εμείς, αυτό που θέλουμε να κάνουμε, είναι xor από την ρίζα προς τα κάτω. Πχ στην ερώτηση που έθεσες θα ψάχναμε κόμβο 1 ^ κόμβο 2 ^ κόμβο 3. Δηλαδή αν ο κόμβος 1 ^ κόμβος 2 έκανε xor με το κόμβο 3 και ήταν ίσον με το 0.Μόνο τότε θα το παίρναμε σωστό.