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

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Marilenatsiop
Δημοσιεύσεις: 26
Εγγραφή: Παρ Ιουν 12, 2020 10:04 am

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

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

Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Μάρτιο.

Κάθε αρχή του μήνα θα ανεβαίνει στο 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, θυμίστε το μας αν το ξεχάσουμε.

Καλή επιτυχία!
Aristotelis
Δημοσιεύσεις: 2
Εγγραφή: Τρί Μαρ 09, 2021 11:22 pm

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

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

Αν υπάρχουν Ν κόμβοι θα είναι αριθμημένοι από το 1 μέχρι το ν;
Aristotelis
Δημοσιεύσεις: 2
Εγγραφή: Τρί Μαρ 09, 2021 11:22 pm

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

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

Και οι κόμβοι θα δίνονται από την ρίζα προς τα φύλλα ή με τυχαία σειρά;
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 385
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

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

Δημοσίευση από Κηπουρίδης »

Καλησπέρα Αριστοτέλη. Πολύ καλές ερωτήσεις. Οι απαντήσεις μου είναι:

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/
Aris
Δημοσιεύσεις: 6
Εγγραφή: Πέμ Μάιος 07, 2020 4:54 pm

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

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

Καλημέρα,

Μήπως υπάρχει κανένας online judge που να έχει αυτό το πρόβλημα? γιατί θέλω να ελέγξω αν μια λύση που έχω βρεί είναι σωστή.
Άβαταρ μέλους
switch
Δημοσιεύσεις: 83
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

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

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

Υπάρχει εδώ: https://www.hackerearth.com/practice/da ... r-image-2/
και ορίστε και ένα 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
Aris
Δημοσιεύσεις: 6
Εγγραφή: Πέμ Μάιος 07, 2020 4:54 pm

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

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

Ευχαριστώ!!
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

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

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

Καλησπέρα σας,

έλυσα το θέμα απλά έχω την εντύπωση ότι η πολυπλοκότητα είναι Ο(3ΜΝ) περίπου. Μπορώ σίγουρα να την μειώσω σε Ο(2ΜΝ) και ακόμα περισσότερο. Απλώς μία πολυπλοκότητα της τάξης του Ο(3ΜΝ) είναι αποδεκτή;

Καλή Συνέχεια!
Python, C++
Άβαταρ μέλους
switch
Δημοσιεύσεις: 83
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

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

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

είναι νομιζω αποδεκτη στο συγκεκριμένο προβλημα του hackerearth που δεν εχει πολλές απαιτησεις. Δεν εκανα υποβολη για να σου πω σιγουρα.
To καλύτερο που μπορει να γινει ειναι o(m+n).
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

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

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

Ένταξει ευχαριστώ πολύ.
Python, C++
Άβαταρ μέλους
switch
Δημοσιεύσεις: 83
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

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

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

Τα testcase του προβλήματος στο hackerearth είναι πολύ χαλαρά και γίνονται αποδεκτές λύσεις με πολυπλοκότητα της τάξηςΟ(Μ*Ν).

Η καλύτερη λύση στο πρόβλημα αυτό είναι της τάξης Ο(Μ+Ν). Δεν μπορούμε να καταφέρουμε κάτι καλύτερο από Ο(Μ+Ν), εφόσον πρέπει τουλάχιστο να διαβάσουμε τα Ν στοιχεία και πρέπει να τυπώσουμε τα Μ αποτελέσματα).

Αν θέλετε να δοκιμάσετε τον αλγόριθμο σας σε πιο βαρια 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, υπάρχει και ο συμβολισμός Ω (κάτω όριο) και Θ (περιορισμός με άνω και κάτω όριο της συμπεριφοράς του αλγορίθμου)
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

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

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

Τα testcases του hackerearth είναι λίγο διαφορετικά από τα δικά μας. Εμείς έχουμε 0 και 1 ενώ αυτό έχει L και R. Οπότε προειδοποιώ όσους θέλουν να τα χρησιμοποιήσουν ότι χρειάζονται μία μικρή τροποποίηση. Αυτό μπορεί να επιτευχθεί φτιάχνοντας ένα απλό προγραμματάκι ή αν έχετε text editor με αναζήτηση και αντικατάσταση χαρακτήρων.
Ευχαριστώ όπως και να έχει γιατί είναι πολύ χρήσιμα τα testcases για να έχω μία εικόνα του χρόνου του κώδικα!
Python, C++
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

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

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

Και όταν λέω text editor δεν λέω κάτι εξεζητημένο. Το σημειωματάριο των windows πχ έχει την λειτουργία και τον έχετε όλοι όσοι είστε με Windows
Python, C++
Marilenatsiop
Δημοσιεύσεις: 26
Εγγραφή: Παρ Ιουν 12, 2020 10:04 am

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

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

Ηint για Ο(Ν*Μ) λύση ::
Ας ξεκινήσουμε από τη ρίζα (root) του δέντρου μας και ας το διασχίσουμε, αναδρομικά, καταγράφοντας την διαδρομή που ακολουθούμε μέχρι να βρούμε το αναγνωριστικό του κόμβου του οποίου τον κατοπτρικό κόμβο ψάχνουμε. Ποια διαδρομή θα πρέπει να ακολουθήσουμε για να βρούμε τον αντικατοπτρικό κόμβο;

Hint για Ο(Ν) λύση ::

Σκεφτείτε ότι διασχίζουμε το δέντρο μας ταυτόχρονα προς δύο αντικατοπτρικές κατευθύνσεις.
Marilenatsiop
Δημοσιεύσεις: 26
Εγγραφή: Παρ Ιουν 12, 2020 10:04 am

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

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

Προγραμματίστηκε η μηνιαία συνάντηση στο 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
Marilenatsiop
Δημοσιεύσεις: 26
Εγγραφή: Παρ Ιουν 12, 2020 10:04 am

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

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

Εάν υπάρξει πρόβλημα με το link, δοκιμάστε αυτό : https://ucph-ku.zoom.us/j/62298579631?p ... RQZitYZz09
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

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

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

Εμένα και τα δύο μου τα βγάζει invalid
Python, C++
Άβαταρ μέλους
switch
Δημοσιεύσεις: 83
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

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

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

giorgosk έγραψε: Σάβ Απρ 03, 2021 3:05 pm Εμένα και τα δύο μου τα βγάζει invalid
Κανε copy paste σε σημειωματαριο το νεο συνδεσμο κ θα βρεις ιδ και παςς
Άβαταρ μέλους
switch
Δημοσιεύσεις: 83
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

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

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

id=62298579631
pass = ZzNRbXVZK05kb1pYUVhMYlRQZitYZz09
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

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

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

πάλι το ίδιο μου βγάζει
Python, C++
Απάντηση