Mηνιαία Πρόκληση: Φεβρουάριος 2021
-
- Δημοσιεύσεις: 33
- Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm
Mηνιαία Πρόκληση: Φεβρουάριος 2021
Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Φεβρουάριο.
Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση.
Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς.
Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου στο τέλος του μήνα θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Σημείωση: Ένας από τους συμμετέχοντες της σύσκεψης θα επιλέγεται ώστε να βοηθήσει τον Βαγγέλη με την επόμενη μηνιαία πρόκληση, αυτή του Μαρτίου εν προκειμένω.
Οι αρμοδιότητές του θα είναι να λύσει το επόμενο πρόβλημα εντός του μήνα (εννοείται με συνεννόηση/βοήθεια από τον Βαγγέλη) ώστε να είναι σε θέση να λύνει απορίες στην επόμενη σύσκεψη και στο forum.
(Και πάλι, εννοείται θα είναι κι o Βαγγέλης στη σύσκεψη, οπότε δεν αγχωνόμαστε "Τι θα γίνει αν δε μπορώ να απαντήσω σε κάποια ερώτηση;").
Από τη σύσκεψη Ιανουαρίου έχει επιλεγεί ήδη ο Κώστας (εγώ) ως βοηθός Φεβρουαρίου.
Σε αυτό το πρόβλημα θέλουμε να διακοσμήσουμε ένα πάρτι με μπαλόνια. Έχουμε μία μεγάλη ευθεία, και Ν μπαλόνια. Για κάθε μπαλόνι ξέρουμε την Χ συντεταγμένη όπου βρίσκεται, και τη μέγιστη ακτίνα που μπορεί να αποκτήσει πριν σκάσει (μπορούμε να το φουσκώσουμε και λιγότερο, προφανώς).
Ο τρόπος με τον οποία τα φουσκώνουμε είναι ο εξής. Ξεκινάμε από τα αριστερά προς τα δεξιά και φουσκώνουμε κάθε μπαλόνι όσο το δυνατόν περισσότερο γίνεται (μέχρι να φτάσει τη μέγιστη ακτίνα του, ή να ακουμπήσει κάποιο άλλο ήδη φουσκωμένο μπαλόνι).
Παρατήρηση: τα μπαλόνια δεν θα έχουν κέντρα στην ίδια ευθεία αλλά αρχές (κατώτατο σημείο) στην ίδια ευθεία και έτσι πρέπει να σκεφτείτε και για τις δύο διαστάσεις, όπως σε αυτή την εικόνα.
Ζητείται να τυπώσουμε την ακτίνα κάθε μπαλονιού μετά το τέλος της διαδικασίας μας.
Στο input θα μας δίνεται το Ν (πλήθος μπαλονιών), και θα ακολουθούν Ν δυάδες αριθμών. Ο πρώτος αριθμός της i-οστής δυάδας είναι η Χ συντεταγμένη του i-οστού μπαλονιού, και ο δεύτερος η μέγιστη ακτίνα του. Τα μπαλόνια θα δίνονται ταξινομημένα ως προς την Χ συντεταγμένη τους.
Ζητείται αλγόριθμος είτε Ο(ΝlogN) είτε Ο(Ν).
Παράδειγμα (ίδιο με την παραπάνω εικόνα) :
3
0 9
8 1
13 7
Θά έπρεπε να βρούμε:
9.000
1.000
4.694
Στις 15 του μηνός θα δώσουμε ένα hint, θυμίστε το μας αν το ξεχάσουμε.
Καλή επιτυχία!
Υ.Γ.: Μετά από λίγη ενασχόληση με το πρόβλημα, θα δείτε ότι απαραίτητη υπορουτίνα για τη λύση του είναι η εξής: Δίνεται ένα φουσκωμένο μπαλόνι Α (με αρχή χ και ακτίνα r), πόσο μπορώ να φουσκώσω ένα δεύτερο μπαλόνι Β (με αρχή x') μέχρι να ακουμπήσουν;
Το πρόβλημα αυτό μπορεί να λυθεί με μαθηματικά Β' Λυκείου, σε Ο(1) χρόνο. Αν δεν γνωρίζετε πώς, θα σας δώσουμε τον κώδικα στις 15 του μηνός, μέχρι τότε προσποιηθείτε ότι γνωρίζετε πώς λύνεται!
Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση.
Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς.
Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου στο τέλος του μήνα θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Σημείωση: Ένας από τους συμμετέχοντες της σύσκεψης θα επιλέγεται ώστε να βοηθήσει τον Βαγγέλη με την επόμενη μηνιαία πρόκληση, αυτή του Μαρτίου εν προκειμένω.
Οι αρμοδιότητές του θα είναι να λύσει το επόμενο πρόβλημα εντός του μήνα (εννοείται με συνεννόηση/βοήθεια από τον Βαγγέλη) ώστε να είναι σε θέση να λύνει απορίες στην επόμενη σύσκεψη και στο forum.
(Και πάλι, εννοείται θα είναι κι o Βαγγέλης στη σύσκεψη, οπότε δεν αγχωνόμαστε "Τι θα γίνει αν δε μπορώ να απαντήσω σε κάποια ερώτηση;").
Από τη σύσκεψη Ιανουαρίου έχει επιλεγεί ήδη ο Κώστας (εγώ) ως βοηθός Φεβρουαρίου.
Σε αυτό το πρόβλημα θέλουμε να διακοσμήσουμε ένα πάρτι με μπαλόνια. Έχουμε μία μεγάλη ευθεία, και Ν μπαλόνια. Για κάθε μπαλόνι ξέρουμε την Χ συντεταγμένη όπου βρίσκεται, και τη μέγιστη ακτίνα που μπορεί να αποκτήσει πριν σκάσει (μπορούμε να το φουσκώσουμε και λιγότερο, προφανώς).
Ο τρόπος με τον οποία τα φουσκώνουμε είναι ο εξής. Ξεκινάμε από τα αριστερά προς τα δεξιά και φουσκώνουμε κάθε μπαλόνι όσο το δυνατόν περισσότερο γίνεται (μέχρι να φτάσει τη μέγιστη ακτίνα του, ή να ακουμπήσει κάποιο άλλο ήδη φουσκωμένο μπαλόνι).
Παρατήρηση: τα μπαλόνια δεν θα έχουν κέντρα στην ίδια ευθεία αλλά αρχές (κατώτατο σημείο) στην ίδια ευθεία και έτσι πρέπει να σκεφτείτε και για τις δύο διαστάσεις, όπως σε αυτή την εικόνα.
Ζητείται να τυπώσουμε την ακτίνα κάθε μπαλονιού μετά το τέλος της διαδικασίας μας.
Στο input θα μας δίνεται το Ν (πλήθος μπαλονιών), και θα ακολουθούν Ν δυάδες αριθμών. Ο πρώτος αριθμός της i-οστής δυάδας είναι η Χ συντεταγμένη του i-οστού μπαλονιού, και ο δεύτερος η μέγιστη ακτίνα του. Τα μπαλόνια θα δίνονται ταξινομημένα ως προς την Χ συντεταγμένη τους.
Ζητείται αλγόριθμος είτε Ο(ΝlogN) είτε Ο(Ν).
Παράδειγμα (ίδιο με την παραπάνω εικόνα) :
3
0 9
8 1
13 7
Θά έπρεπε να βρούμε:
9.000
1.000
4.694
Στις 15 του μηνός θα δώσουμε ένα hint, θυμίστε το μας αν το ξεχάσουμε.
Καλή επιτυχία!
Υ.Γ.: Μετά από λίγη ενασχόληση με το πρόβλημα, θα δείτε ότι απαραίτητη υπορουτίνα για τη λύση του είναι η εξής: Δίνεται ένα φουσκωμένο μπαλόνι Α (με αρχή χ και ακτίνα r), πόσο μπορώ να φουσκώσω ένα δεύτερο μπαλόνι Β (με αρχή x') μέχρι να ακουμπήσουν;
Το πρόβλημα αυτό μπορεί να λυθεί με μαθηματικά Β' Λυκείου, σε Ο(1) χρόνο. Αν δεν γνωρίζετε πώς, θα σας δώσουμε τον κώδικα στις 15 του μηνός, μέχρι τότε προσποιηθείτε ότι γνωρίζετε πώς λύνεται!
-
- Δημοσιεύσεις: 9
- Εγγραφή: Δευ Φεβ 01, 2021 6:25 pm
Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021
Καλησπέρα και συγγνώμη για την λογικά ηλίθια ερώτηση αλλά τι εννοείται με το
?
Έψαχνα σε αγγλικά φόρουμς αλλά δεν μπορούσα να καταλάβω. Θα μπορούσε κάποιος να το εξηγήσειΖητείται αλγόριθμος είτε Ο(ΝlogN) είτε Ο(Ν).
![Smile :)](./images/smilies/icon_e_smile.gif)
Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021
Μπορείς να ψάξεις γενικά για πολυπλοκότητα αλγορίθμων.
Γραμμικό ή O(N) σημαίνει ότι αν έχεις Ν δεδομένα εισόδου θα κάνεις περίπου α*N βηματάκια για να βρεις τη λύση (όπου α κάποιος μικρός ΣΤΑΘΕΡΟΣ -ανεξάρτητος από το Ν- αριθμός)
Τετραγωνικό O(N^2) σημαίνει ότι για Ν στοιχεία εισόδου, θα κάνεις α*N*N βηματάκια
Λογαριθμικός Ο(Ν*logN) ότι για Ν θα κάνεις το α*N*logN βηματάκια
Αν είσαι μαθητής γυμνασίου και δεν καταλαβαίνεις τη συνάρτηση log: logN είναι ο αριθμός χ, οπου αν υψώσω το 2 στη χ, θα δώσει αποτέλεσμα Ν.
Παράδειγμα τριών διαφορετικών πολυπλοκοτήτων για Ν=1.000.000
O(N) περίπου 1.000.000 βηματάκια
Ο(N*logN)=1.000.000 * 20 = 20.000.000 βηματάκια
Ο(Ν^2) = 1.000.000.000.000 βηματάκια
Ο υπολογιστης μπορεί να κάνει περίπου 100.000.000 βηματάκια το δευτερόλεπτο.
Όπως καταλαβαίνεις η περίπτωση Ν^2 δεν τελειώνει σε καλό χρόνο για διαγωνισμό.
Γραμμικό ή O(N) σημαίνει ότι αν έχεις Ν δεδομένα εισόδου θα κάνεις περίπου α*N βηματάκια για να βρεις τη λύση (όπου α κάποιος μικρός ΣΤΑΘΕΡΟΣ -ανεξάρτητος από το Ν- αριθμός)
Τετραγωνικό O(N^2) σημαίνει ότι για Ν στοιχεία εισόδου, θα κάνεις α*N*N βηματάκια
Λογαριθμικός Ο(Ν*logN) ότι για Ν θα κάνεις το α*N*logN βηματάκια
Αν είσαι μαθητής γυμνασίου και δεν καταλαβαίνεις τη συνάρτηση log: logN είναι ο αριθμός χ, οπου αν υψώσω το 2 στη χ, θα δώσει αποτέλεσμα Ν.
Παράδειγμα τριών διαφορετικών πολυπλοκοτήτων για Ν=1.000.000
O(N) περίπου 1.000.000 βηματάκια
Ο(N*logN)=1.000.000 * 20 = 20.000.000 βηματάκια
Ο(Ν^2) = 1.000.000.000.000 βηματάκια
Ο υπολογιστης μπορεί να κάνει περίπου 100.000.000 βηματάκια το δευτερόλεπτο.
Όπως καταλαβαίνεις η περίπτωση Ν^2 δεν τελειώνει σε καλό χρόνο για διαγωνισμό.
-
- Δημοσιεύσεις: 33
- Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm
Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021
Το hint που υποσχεθήκαμε!
1: Για να υπολογίσετε πόσο θα μεγαλώσει ένα μπαλόνι για να ακουμπήσει το προηγούμενο, μπορείτε να χρησιμοποιήσετε το πυθαγόρειο θεώρημα σε ένα ορθογώνιο τρίγωνο με υποτείνουσα μία πλευρά που ξεκινάει και τελειώνει στα κέντρα των κύκλων, όπως και στην παρακάτω εικόνα.
![Εικόνα](https://i.imgur.com/npTxtsa.png)
Με τι είναι ίση η υποτείνουσα του τριγώνου;
---------------------------------------------------------------------------------------
![Εικόνα](https://i.imgur.com/kYT2WpV.png)
2: Υπάρχει περίπτωση, στην παραπάνω εικόνα, το κόκκινο μπαλόνι να ακουμπήσει το πράσινο πριν ακουμπήσει το καφέ;
1: Για να υπολογίσετε πόσο θα μεγαλώσει ένα μπαλόνι για να ακουμπήσει το προηγούμενο, μπορείτε να χρησιμοποιήσετε το πυθαγόρειο θεώρημα σε ένα ορθογώνιο τρίγωνο με υποτείνουσα μία πλευρά που ξεκινάει και τελειώνει στα κέντρα των κύκλων, όπως και στην παρακάτω εικόνα.
![Εικόνα](https://i.imgur.com/npTxtsa.png)
Με τι είναι ίση η υποτείνουσα του τριγώνου;
---------------------------------------------------------------------------------------
![Εικόνα](https://i.imgur.com/kYT2WpV.png)
2: Υπάρχει περίπτωση, στην παραπάνω εικόνα, το κόκκινο μπαλόνι να ακουμπήσει το πράσινο πριν ακουμπήσει το καφέ;
-
- Δημοσιεύσεις: 33
- Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm
Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021
Προγραμματίστηκε η μηνιαία συνάντηση στο zoom για το Σάββατο 6 Μαρτίου και 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
Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021
Καλησπέρα!
Υπάρχει μήπως κάποιο πρόβλημα με το link και το meeting id?
Ή μόνο εμείς έχουμε πρόβλημα;
Υπάρχει μήπως κάποιο πρόβλημα με το link και το meeting id?
Ή μόνο εμείς έχουμε πρόβλημα;
-
- Δημοσιεύσεις: 33
- Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm
Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021
Καλησπέρα, και εγώ βλέπω ότι δεν μπορώ να μπω. Θα μιλήσω τώρα με τον Βαγγέλη.
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021
Το κοιτάω κι εγώ τώρα παιδιά, με συγχωρείτε. Ελπίζω ότι σε δέκα λεπτά θα μπορούμε να μπούμε όλοι ![Smile :)](./images/smilies/icon_e_smile.gif)
![Smile :)](./images/smilies/icon_e_smile.gif)
Λύσεις θεμάτων ΠΔΠ: 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/
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021
Δεν έβγαλα άκρη, οπότε δημιούργησα καινούργιο δωμάτιο: https://ucph-ku.zoom.us/j/62298579631?p ... RQZitYZz09
Λύσεις θεμάτων ΠΔΠ: 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/
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021
Ορίστε ψευδοκώδικας για το πρόβλημα!
https://imgur.com/2AUixgH
Προφανώς αν δεν έχετε δει την επεξήγηση και δείτε απευθείας τον κώδικα, θα φανεί εντελώς ακατανόητος. Υπενθυμίζω ότι έχουμε recording με επεξήγηση της λύσης, όποιος το χρειαστεί ας μου στείλει προσωπικό μήνυμα.
https://imgur.com/2AUixgH
Προφανώς αν δεν έχετε δει την επεξήγηση και δείτε απευθείας τον κώδικα, θα φανεί εντελώς ακατανόητος. Υπενθυμίζω ότι έχουμε recording με επεξήγηση της λύσης, όποιος το χρειαστεί ας μου στείλει προσωπικό μήνυμα.
Λύσεις θεμάτων ΠΔΠ: 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/