Μηνιαία Πρόκληση: Μάρτιος 2021
Δημοσιεύτηκε: Τρί Μαρ 09, 2021 9:05 am
Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Μάρτιο.
Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση.
Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς.
Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου στο τέλος του μήνα θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Σημείωση: Ένας από τους συμμετέχοντες της σύσκεψης θα επιλέγεται ώστε να βοηθήσει τον Βαγγέλη με την επόμενη μηνιαία πρόκληση, αυτή του Απριλίου εν προκειμένω.
Οι αρμοδιότητές του θα είναι να λύσει το επόμενο πρόβλημα εντός του μήνα (εννοείται με συνεννόηση/βοήθεια από τον Βαγγέλη) ώστε να είναι σε θέση να λύνει απορίες στην επόμενη σύσκεψη και στο forum.
(Και πάλι, εννοείται θα είναι κι o Βαγγέλης στη σύσκεψη, οπότε δεν αγχωνόμαστε "Τι θα γίνει αν δε μπορώ να απαντήσω σε κάποια ερώτηση;").
Από τη σύσκεψη Φεβρουαρίου έχει επιλεγεί ήδη η Μαριλένα (εγώ) ως βοηθός Μαρτίου.
Σε αυτό το πρόβλημα μας δίνεται ένα δυαδικό δέντρο όπως αυτό της εικόνας.
(https://i.imgur.com/dfwxLZ0.jpg)
Πρέπει να απαντάμε σε ερωτήματα του τύπου: "Ποιος είναι (αν υπάρχει) ο κατοπτρικός κόμβος του Ε;".
Για να εξηγήσουμε τι εννοούμε με τον όρο "κατοπτρικός", ας παρατηρήσουμε ότι ξεκινώντας από τη ρίζα (κόμβος Α), για να φτάσουμε στον κόμβο Ε θα πρέπει να πάρουμε πρώτα μια αριστερή στροφή και μετά μια δεξιά (δηλαδή να πάμε πρώτα στον Β και μετά στον Ε). Κατοπτρικός του Ε είναι ο Ζ επειδή κάνει ακριβώς τις ανάποδες κινήσεις, δηλαδή παίρνει πρώτα μια δεξιά και μετά μια αριστερή στροφή (δηλαδή πάμε πρώτα στον Γ και μετά στον Ζ).
Αντίστοιχα, κατοπτρικός του Α είναι ο εαυτός του, κατοπτρικός του Β είναι ο Γ, ενώ οι Δ και Η δεν έχουν κατοπτρικό κόμβο.
Στην είσοδο θα μας δίνεται το Ν (πλήθος κόμβων) και Μ (πλήθος ερωτημάτων). Ακολουθούν Ν-1 τριάδες αριθμών. Ο πρώτος αριθμός της i-οστής τριάδας είναι ένας κόμβος-πατέρας u, ο δεύτερος είναι ένας κόμβος-παιδί v, κι ο τρίτος είναι 0 αν ο v είναι αριστερό παιδί του u, και 1 αν είναι δεξί.
Κατόπιν ακολουθούν M γραμμές, η κάθε μία απ' τις οποίες περιγράφει ένα ερώτημα. Κάθε τέτοια γραμμή περιέχει έναν μόνο αριθμό, το αναγνωριστικό του κόμβου του οποίου τον κατοπτρικό ψάχνουμε.
Η έξοδος θα αποτελείται από Μ γραμμές. Η i-οστή από αυτές περιέχει έναν αριθμό, την απάντηση στο i-οστό ερώτημα. Πιο συγκεκριμένα, θα περιέχει το αναγνωριστικό του κατοπτρικού κόμβου του ερωτήματος, ή -1 αν δεν υπάρχει κατοπτρικός.
Ζητείται αλγόριθμος είτε O(MN), είτε Ο(N+MlogN) είτε Ο(Ν).
Παράδειγμα (ίδιο με την εικόνα) :
7 5
1 2 0
1 3 1
2 4 0
2 5 1
3 6 0
4 7 1
1
2
3
7
6
Έξοδος
1
3
2
-1
5
Στις 20 του μηνός θα δώσουμε ένα hint, θυμίστε το μας αν το ξεχάσουμε.
Καλή επιτυχία!
Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση.
Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς.
Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου στο τέλος του μήνα θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Σημείωση: Ένας από τους συμμετέχοντες της σύσκεψης θα επιλέγεται ώστε να βοηθήσει τον Βαγγέλη με την επόμενη μηνιαία πρόκληση, αυτή του Απριλίου εν προκειμένω.
Οι αρμοδιότητές του θα είναι να λύσει το επόμενο πρόβλημα εντός του μήνα (εννοείται με συνεννόηση/βοήθεια από τον Βαγγέλη) ώστε να είναι σε θέση να λύνει απορίες στην επόμενη σύσκεψη και στο forum.
(Και πάλι, εννοείται θα είναι κι o Βαγγέλης στη σύσκεψη, οπότε δεν αγχωνόμαστε "Τι θα γίνει αν δε μπορώ να απαντήσω σε κάποια ερώτηση;").
Από τη σύσκεψη Φεβρουαρίου έχει επιλεγεί ήδη η Μαριλένα (εγώ) ως βοηθός Μαρτίου.
Σε αυτό το πρόβλημα μας δίνεται ένα δυαδικό δέντρο όπως αυτό της εικόνας.
(https://i.imgur.com/dfwxLZ0.jpg)
Πρέπει να απαντάμε σε ερωτήματα του τύπου: "Ποιος είναι (αν υπάρχει) ο κατοπτρικός κόμβος του Ε;".
Για να εξηγήσουμε τι εννοούμε με τον όρο "κατοπτρικός", ας παρατηρήσουμε ότι ξεκινώντας από τη ρίζα (κόμβος Α), για να φτάσουμε στον κόμβο Ε θα πρέπει να πάρουμε πρώτα μια αριστερή στροφή και μετά μια δεξιά (δηλαδή να πάμε πρώτα στον Β και μετά στον Ε). Κατοπτρικός του Ε είναι ο Ζ επειδή κάνει ακριβώς τις ανάποδες κινήσεις, δηλαδή παίρνει πρώτα μια δεξιά και μετά μια αριστερή στροφή (δηλαδή πάμε πρώτα στον Γ και μετά στον Ζ).
Αντίστοιχα, κατοπτρικός του Α είναι ο εαυτός του, κατοπτρικός του Β είναι ο Γ, ενώ οι Δ και Η δεν έχουν κατοπτρικό κόμβο.
Στην είσοδο θα μας δίνεται το Ν (πλήθος κόμβων) και Μ (πλήθος ερωτημάτων). Ακολουθούν Ν-1 τριάδες αριθμών. Ο πρώτος αριθμός της i-οστής τριάδας είναι ένας κόμβος-πατέρας u, ο δεύτερος είναι ένας κόμβος-παιδί v, κι ο τρίτος είναι 0 αν ο v είναι αριστερό παιδί του u, και 1 αν είναι δεξί.
Κατόπιν ακολουθούν M γραμμές, η κάθε μία απ' τις οποίες περιγράφει ένα ερώτημα. Κάθε τέτοια γραμμή περιέχει έναν μόνο αριθμό, το αναγνωριστικό του κόμβου του οποίου τον κατοπτρικό ψάχνουμε.
Η έξοδος θα αποτελείται από Μ γραμμές. Η i-οστή από αυτές περιέχει έναν αριθμό, την απάντηση στο i-οστό ερώτημα. Πιο συγκεκριμένα, θα περιέχει το αναγνωριστικό του κατοπτρικού κόμβου του ερωτήματος, ή -1 αν δεν υπάρχει κατοπτρικός.
Ζητείται αλγόριθμος είτε O(MN), είτε Ο(N+MlogN) είτε Ο(Ν).
Παράδειγμα (ίδιο με την εικόνα) :
7 5
1 2 0
1 3 1
2 4 0
2 5 1
3 6 0
4 7 1
1
2
3
7
6
Έξοδος
1
3
2
-1
5
Στις 20 του μηνός θα δώσουμε ένα hint, θυμίστε το μας αν το ξεχάσουμε.
Καλή επιτυχία!