Σελίδα 1 από 2

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

Δημοσιεύτηκε: Τρί Μαρ 09, 2021 9:05 am
από 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, θυμίστε το μας αν το ξεχάσουμε.

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

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

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

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

Δημοσιεύτηκε: Τρί Μαρ 09, 2021 11:38 pm
από Aristotelis
Και οι κόμβοι θα δίνονται από την ρίζα προς τα φύλλα ή με τυχαία σειρά;

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

Δημοσιεύτηκε: Τετ Μαρ 10, 2021 2:53 am
από Κηπουρίδης
Καλησπέρα Αριστοτέλη. Πολύ καλές ερωτήσεις. Οι απαντήσεις μου είναι:

1) Σκέψου το πρόβλημα απλοποιημένα, με κόμβους από 1 μέχρι Ν και με input που να δίνεται από την ρίζα προς τα φύλλα.
2) Μόνο αν βρεις την βέλτιστη λύση για το απλοποιημένο πρόβλημα, σκέψου την πιο γενική εκδοχή και πώς θα την αντιμετώπιζες. Δηλαδή αν οι κόμβοι δεν είναι αναγκαστικά από 1 ως Ν, αλλά 32-bit integers, και αν το input δίνεται με τυχαία σειρά.

Γενικά το προτείνω σαν γενική προσέγγιση αυτό. Δηλαδή να διευκολύνεις όσο μπορείς τον εαυτό σου από τέτοιες λεπτομέρειες για να δεις καθαρά την λύση, και μετά απλά κάνεις τις μικρές τροποποιήσεις που χρειάζονται.

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

Δημοσιεύτηκε: Τετ Μαρ 10, 2021 1:37 pm
από Aris
Καλημέρα,

Μήπως υπάρχει κανένας online judge που να έχει αυτό το πρόβλημα? γιατί θέλω να ελέγξω αν μια λύση που έχω βρεί είναι σωστή.

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

Δημοσιεύτηκε: Τετ Μαρ 10, 2021 7:36 pm
από 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

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

Δημοσιεύτηκε: Τετ Μαρ 10, 2021 9:39 pm
από Aris
Ευχαριστώ!!

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

Δημοσιεύτηκε: Τρί Μαρ 16, 2021 4:50 pm
από giorgosk
Καλησπέρα σας,

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

Καλή Συνέχεια!

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

Δημοσιεύτηκε: Τρί Μαρ 16, 2021 5:03 pm
από switch
είναι νομιζω αποδεκτη στο συγκεκριμένο προβλημα του hackerearth που δεν εχει πολλές απαιτησεις. Δεν εκανα υποβολη για να σου πω σιγουρα.
To καλύτερο που μπορει να γινει ειναι o(m+n).

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

Δημοσιεύτηκε: Τρί Μαρ 16, 2021 5:18 pm
από giorgosk
Ένταξει ευχαριστώ πολύ.

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

Δημοσιεύτηκε: Παρ Μαρ 19, 2021 2:24 am
από 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, υπάρχει και ο συμβολισμός Ω (κάτω όριο) και Θ (περιορισμός με άνω και κάτω όριο της συμπεριφοράς του αλγορίθμου)

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

Δημοσιεύτηκε: Παρ Μαρ 19, 2021 10:21 am
από giorgosk
Τα testcases του hackerearth είναι λίγο διαφορετικά από τα δικά μας. Εμείς έχουμε 0 και 1 ενώ αυτό έχει L και R. Οπότε προειδοποιώ όσους θέλουν να τα χρησιμοποιήσουν ότι χρειάζονται μία μικρή τροποποίηση. Αυτό μπορεί να επιτευχθεί φτιάχνοντας ένα απλό προγραμματάκι ή αν έχετε text editor με αναζήτηση και αντικατάσταση χαρακτήρων.
Ευχαριστώ όπως και να έχει γιατί είναι πολύ χρήσιμα τα testcases για να έχω μία εικόνα του χρόνου του κώδικα!

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

Δημοσιεύτηκε: Παρ Μαρ 19, 2021 10:38 am
από giorgosk
Και όταν λέω text editor δεν λέω κάτι εξεζητημένο. Το σημειωματάριο των windows πχ έχει την λειτουργία και τον έχετε όλοι όσοι είστε με Windows

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

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

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

Σκεφτείτε ότι διασχίζουμε το δέντρο μας ταυτόχρονα προς δύο αντικατοπτρικές κατευθύνσεις.

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

Δημοσιεύτηκε: Τρί Μαρ 30, 2021 12:40 pm
από 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

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

Δημοσιεύτηκε: Σάβ Απρ 03, 2021 2:54 pm
από Marilenatsiop
Εάν υπάρξει πρόβλημα με το link, δοκιμάστε αυτό : https://ucph-ku.zoom.us/j/62298579631?p ... RQZitYZz09

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

Δημοσιεύτηκε: Σάβ Απρ 03, 2021 3:05 pm
από giorgosk
Εμένα και τα δύο μου τα βγάζει invalid

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

Δημοσιεύτηκε: Σάβ Απρ 03, 2021 3:07 pm
από switch
giorgosk έγραψε: Σάβ Απρ 03, 2021 3:05 pm Εμένα και τα δύο μου τα βγάζει invalid
Κανε copy paste σε σημειωματαριο το νεο συνδεσμο κ θα βρεις ιδ και παςς

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

Δημοσιεύτηκε: Σάβ Απρ 03, 2021 3:08 pm
από switch
id=62298579631
pass = ZzNRbXVZK05kb1pYUVhMYlRQZitYZz09

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

Δημοσιεύτηκε: Σάβ Απρ 03, 2021 3:10 pm
από giorgosk
πάλι το ίδιο μου βγάζει