Μηνιαία Πρόκληση: Μάρτιος 2021
-
- Δημοσιεύσεις: 27
- Εγγραφή: Παρ Ιουν 12, 2020 10:04 am
Μηνιαία Πρόκληση: Μάρτιος 2021
Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Μάρτιο.
Κάθε αρχή του μήνα θα ανεβαίνει στο 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, θυμίστε το μας αν το ξεχάσουμε.
Καλή επιτυχία!
-
- Δημοσιεύσεις: 2
- Εγγραφή: Τρί Μαρ 09, 2021 11:22 pm
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Αν υπάρχουν Ν κόμβοι θα είναι αριθμημένοι από το 1 μέχρι το ν;
-
- Δημοσιεύσεις: 2
- Εγγραφή: Τρί Μαρ 09, 2021 11:22 pm
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Και οι κόμβοι θα δίνονται από την ρίζα προς τα φύλλα ή με τυχαία σειρά;
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Καλησπέρα Αριστοτέλη. Πολύ καλές ερωτήσεις. Οι απαντήσεις μου είναι:
1) Σκέψου το πρόβλημα απλοποιημένα, με κόμβους από 1 μέχρι Ν και με input που να δίνεται από την ρίζα προς τα φύλλα.
2) Μόνο αν βρεις την βέλτιστη λύση για το απλοποιημένο πρόβλημα, σκέψου την πιο γενική εκδοχή και πώς θα την αντιμετώπιζες. Δηλαδή αν οι κόμβοι δεν είναι αναγκαστικά από 1 ως Ν, αλλά 32-bit integers, και αν το input δίνεται με τυχαία σειρά.
Γενικά το προτείνω σαν γενική προσέγγιση αυτό. Δηλαδή να διευκολύνεις όσο μπορείς τον εαυτό σου από τέτοιες λεπτομέρειες για να δεις καθαρά την λύση, και μετά απλά κάνεις τις μικρές τροποποιήσεις που χρειάζονται.
1) Σκέψου το πρόβλημα απλοποιημένα, με κόμβους από 1 μέχρι Ν και με input που να δίνεται από την ρίζα προς τα φύλλα.
2) Μόνο αν βρεις την βέλτιστη λύση για το απλοποιημένο πρόβλημα, σκέψου την πιο γενική εκδοχή και πώς θα την αντιμετώπιζες. Δηλαδή αν οι κόμβοι δεν είναι αναγκαστικά από 1 ως Ν, αλλά 32-bit integers, και αν το input δίνεται με τυχαία σειρά.
Γενικά το προτείνω σαν γενική προσέγγιση αυτό. Δηλαδή να διευκολύνεις όσο μπορείς τον εαυτό σου από τέτοιες λεπτομέρειες για να δεις καθαρά την λύση, και μετά απλά κάνεις τις μικρές τροποποιήσεις που χρειάζονται.
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Καλημέρα,
Μήπως υπάρχει κανένας online judge που να έχει αυτό το πρόβλημα? γιατί θέλω να ελέγξω αν μια λύση που έχω βρεί είναι σωστή.
Μήπως υπάρχει κανένας online judge που να έχει αυτό το πρόβλημα? γιατί θέλω να ελέγξω αν μια λύση που έχω βρεί είναι σωστή.
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Υπάρχει εδώ: https://www.hackerearth.com/practice/da ... r-image-2/
και ορίστε και ένα test case (με root=1)
απαντήσεις:
και ορίστε και ένα test case (με root=1)
Κώδικας: Επιλογή όλων
9 9
1 2 0
1 7 1
2 4 0
2 5 1
7 8 0
8 3 1
5 6 0
5 9 1
1
2
3
4
5
6
7
8
9
Κώδικας: Επιλογή όλων
1
7
6
-1
8
3
2
5
-1
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Ευχαριστώ!!
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Καλησπέρα σας,
έλυσα το θέμα απλά έχω την εντύπωση ότι η πολυπλοκότητα είναι Ο(3ΜΝ) περίπου. Μπορώ σίγουρα να την μειώσω σε Ο(2ΜΝ) και ακόμα περισσότερο. Απλώς μία πολυπλοκότητα της τάξης του Ο(3ΜΝ) είναι αποδεκτή;
Καλή Συνέχεια!
έλυσα το θέμα απλά έχω την εντύπωση ότι η πολυπλοκότητα είναι Ο(3ΜΝ) περίπου. Μπορώ σίγουρα να την μειώσω σε Ο(2ΜΝ) και ακόμα περισσότερο. Απλώς μία πολυπλοκότητα της τάξης του Ο(3ΜΝ) είναι αποδεκτή;
Καλή Συνέχεια!
Python, C++
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
είναι νομιζω αποδεκτη στο συγκεκριμένο προβλημα του hackerearth που δεν εχει πολλές απαιτησεις. Δεν εκανα υποβολη για να σου πω σιγουρα.
To καλύτερο που μπορει να γινει ειναι o(m+n).
To καλύτερο που μπορει να γινει ειναι o(m+n).
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Τα testcase του προβλήματος στο hackerearth είναι πολύ χαλαρά και γίνονται αποδεκτές λύσεις με πολυπλοκότητα της τάξηςΟ(Μ*Ν).
Η καλύτερη λύση στο πρόβλημα αυτό είναι της τάξης Ο(Μ+Ν). Δεν μπορούμε να καταφέρουμε κάτι καλύτερο από Ο(Μ+Ν), εφόσον πρέπει τουλάχιστο να διαβάσουμε τα Ν στοιχεία και πρέπει να τυπώσουμε τα Μ αποτελέσματα).
Αν θέλετε να δοκιμάσετε τον αλγόριθμο σας σε πιο βαρια test cases, ορίστε μερικά με
Δεδομένου ότι ένας υπολογιστής μπορεί (χοντρικά) να κάνει 100.000.000 απλά "βηματάκια" το δευτερόλεπτο, μπορείτε να δοκιμάσετε μέχρι ποιό test case μπορεί να φτάσει η λύση σας σε χρόνο 1 δευτερόλεπτο περίπου.
Το τελευταίο test case μπορεί να "σκάσει" (segmentation fault) τη λύση σας ανάλογα με την υλοποίηση που έχετε κάνει. Αν συμβεί αυτό μην τα βάψετε μαύρα, η διόρθωση είναι εύκολη (μόλις γίνει κατανοητό τι προκάλεσε το πρόβλημα).
test cases: https://drive.google.com/file/d/1ShLt2g ... sp=sharing
Για την πολυπλοκότητα, γενικά, χρησιμοποιείται συχνά ο συμβολισμός big O που ασχολείται με τη περιγραφή της χειρότερης συμπεριφοράς του αλγορίθμου. Γι' αυτό και αν σε έναν αλγόριθμο θέλουμε N*Μ+Ν+Μ βήματα, λέμε ότι έχουμε πολυπλοκότητα της τάξης Ο(Ν*Μ),
Μπορείτε να δείτε μια ενδεικτική χρονική κατάταξη αλγορίθμων με διαφορετικές πολυπλοκότητες ανα αριθμό στοιχείων εισόδου εδώ: http://www0.dmst.aueb.gr/louridas/lectu ... 01s03.html.
Εκτός από το big O notation, υπάρχει και ο συμβολισμός Ω (κάτω όριο) και Θ (περιορισμός με άνω και κάτω όριο της συμπεριφοράς του αλγορίθμου)
Η καλύτερη λύση στο πρόβλημα αυτό είναι της τάξης Ο(Μ+Ν). Δεν μπορούμε να καταφέρουμε κάτι καλύτερο από Ο(Μ+Ν), εφόσον πρέπει τουλάχιστο να διαβάσουμε τα Ν στοιχεία και πρέπει να τυπώσουμε τα Μ αποτελέσματα).
Αν θέλετε να δοκιμάσετε τον αλγόριθμο σας σε πιο βαρια test cases, ορίστε μερικά με
- Ν=Μ=1000
- Ν=Μ=10.000
- Ν=Μ=40.000
- Ν=Μ=1.000.000
Δεδομένου ότι ένας υπολογιστής μπορεί (χοντρικά) να κάνει 100.000.000 απλά "βηματάκια" το δευτερόλεπτο, μπορείτε να δοκιμάσετε μέχρι ποιό test case μπορεί να φτάσει η λύση σας σε χρόνο 1 δευτερόλεπτο περίπου.
Το τελευταίο test case μπορεί να "σκάσει" (segmentation fault) τη λύση σας ανάλογα με την υλοποίηση που έχετε κάνει. Αν συμβεί αυτό μην τα βάψετε μαύρα, η διόρθωση είναι εύκολη (μόλις γίνει κατανοητό τι προκάλεσε το πρόβλημα).
test cases: https://drive.google.com/file/d/1ShLt2g ... sp=sharing
Για την πολυπλοκότητα, γενικά, χρησιμοποιείται συχνά ο συμβολισμός big O που ασχολείται με τη περιγραφή της χειρότερης συμπεριφοράς του αλγορίθμου. Γι' αυτό και αν σε έναν αλγόριθμο θέλουμε N*Μ+Ν+Μ βήματα, λέμε ότι έχουμε πολυπλοκότητα της τάξης Ο(Ν*Μ),
Μπορείτε να δείτε μια ενδεικτική χρονική κατάταξη αλγορίθμων με διαφορετικές πολυπλοκότητες ανα αριθμό στοιχείων εισόδου εδώ: http://www0.dmst.aueb.gr/louridas/lectu ... 01s03.html.
Εκτός από το big O notation, υπάρχει και ο συμβολισμός Ω (κάτω όριο) και Θ (περιορισμός με άνω και κάτω όριο της συμπεριφοράς του αλγορίθμου)
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Τα testcases του hackerearth είναι λίγο διαφορετικά από τα δικά μας. Εμείς έχουμε 0 και 1 ενώ αυτό έχει L και R. Οπότε προειδοποιώ όσους θέλουν να τα χρησιμοποιήσουν ότι χρειάζονται μία μικρή τροποποίηση. Αυτό μπορεί να επιτευχθεί φτιάχνοντας ένα απλό προγραμματάκι ή αν έχετε text editor με αναζήτηση και αντικατάσταση χαρακτήρων.
Ευχαριστώ όπως και να έχει γιατί είναι πολύ χρήσιμα τα testcases για να έχω μία εικόνα του χρόνου του κώδικα!
Ευχαριστώ όπως και να έχει γιατί είναι πολύ χρήσιμα τα testcases για να έχω μία εικόνα του χρόνου του κώδικα!
Python, C++
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Και όταν λέω text editor δεν λέω κάτι εξεζητημένο. Το σημειωματάριο των windows πχ έχει την λειτουργία και τον έχετε όλοι όσοι είστε με Windows
Python, C++
-
- Δημοσιεύσεις: 27
- Εγγραφή: Παρ Ιουν 12, 2020 10:04 am
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Ηint για Ο(Ν*Μ) λύση ::
Ας ξεκινήσουμε από τη ρίζα (root) του δέντρου μας και ας το διασχίσουμε, αναδρομικά, καταγράφοντας την διαδρομή που ακολουθούμε μέχρι να βρούμε το αναγνωριστικό του κόμβου του οποίου τον κατοπτρικό κόμβο ψάχνουμε. Ποια διαδρομή θα πρέπει να ακολουθήσουμε για να βρούμε τον αντικατοπτρικό κόμβο;
Hint για Ο(Ν) λύση ::
Σκεφτείτε ότι διασχίζουμε το δέντρο μας ταυτόχρονα προς δύο αντικατοπτρικές κατευθύνσεις.
Ας ξεκινήσουμε από τη ρίζα (root) του δέντρου μας και ας το διασχίσουμε, αναδρομικά, καταγράφοντας την διαδρομή που ακολουθούμε μέχρι να βρούμε το αναγνωριστικό του κόμβου του οποίου τον κατοπτρικό κόμβο ψάχνουμε. Ποια διαδρομή θα πρέπει να ακολουθήσουμε για να βρούμε τον αντικατοπτρικό κόμβο;
Hint για Ο(Ν) λύση ::
Σκεφτείτε ότι διασχίζουμε το δέντρο μας ταυτόχρονα προς δύο αντικατοπτρικές κατευθύνσεις.
-
- Δημοσιεύσεις: 27
- Εγγραφή: Παρ Ιουν 12, 2020 10:04 am
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Προγραμματίστηκε η μηνιαία συνάντηση στο zoom για το Σάββατο 3 Απριλίου και 15:00 ώρα Ελλάδος!
Kατά προτίμηση να κατεβάσετε την εφαρμογή του zoom σε περίπτωση που χρειαστεί να δείξετε κάτι στον πίνακα, μιας που δεν μπορείτε από την browser εφαρμογή.
Στοιχεία σύνδεσης στο zoom meeting:
Meeting ID: 675 8682 5824
Passcode: 988982
ή
link: https://ucph-ku.zoom.us/j/67586825824?p
Kατά προτίμηση να κατεβάσετε την εφαρμογή του zoom σε περίπτωση που χρειαστεί να δείξετε κάτι στον πίνακα, μιας που δεν μπορείτε από την browser εφαρμογή.
Στοιχεία σύνδεσης στο zoom meeting:
Meeting ID: 675 8682 5824
Passcode: 988982
ή
link: https://ucph-ku.zoom.us/j/67586825824?p
-
- Δημοσιεύσεις: 27
- Εγγραφή: Παρ Ιουν 12, 2020 10:04 am
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Εάν υπάρξει πρόβλημα με το link, δοκιμάστε αυτό : https://ucph-ku.zoom.us/j/62298579631?p ... RQZitYZz09
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
id=62298579631
pass = ZzNRbXVZK05kb1pYUVhMYlRQZitYZz09
pass = ZzNRbXVZK05kb1pYUVhMYlRQZitYZz09