Mηνιαία Πρόκληση: Φεβρουάριος 2021

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
kostas1507
Δημοσιεύσεις: 33
Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm

Mηνιαία Πρόκληση: Φεβρουάριος 2021

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

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

Κάθε αρχή του μήνα θα ανεβαίνει στο 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 του μηνός, μέχρι τότε προσποιηθείτε ότι γνωρίζετε πώς λύνεται!
_kountardas
Δημοσιεύσεις: 9
Εγγραφή: Δευ Φεβ 01, 2021 6:25 pm

Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021

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

Καλησπέρα και συγγνώμη για την λογικά ηλίθια ερώτηση αλλά τι εννοείται με το
Ζητείται αλγόριθμος είτε Ο(ΝlogN) είτε Ο(Ν).
Έψαχνα σε αγγλικά φόρουμς αλλά δεν μπορούσα να καταλάβω. Θα μπορούσε κάποιος να το εξηγήσει :) ?
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021

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

Μπορείς να ψάξεις γενικά για πολυπλοκότητα αλγορίθμων.

Γραμμικό ή 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 δεν τελειώνει σε καλό χρόνο για διαγωνισμό.
kostas1507
Δημοσιεύσεις: 33
Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm

Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021

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

Το hint που υποσχεθήκαμε!
1: Για να υπολογίσετε πόσο θα μεγαλώσει ένα μπαλόνι για να ακουμπήσει το προηγούμενο, μπορείτε να χρησιμοποιήσετε το πυθαγόρειο θεώρημα σε ένα ορθογώνιο τρίγωνο με υποτείνουσα μία πλευρά που ξεκινάει και τελειώνει στα κέντρα των κύκλων, όπως και στην παρακάτω εικόνα.
Εικόνα

Με τι είναι ίση η υποτείνουσα του τριγώνου;
---------------------------------------------------------------------------------------


Εικόνα

2: Υπάρχει περίπτωση, στην παραπάνω εικόνα, το κόκκινο μπαλόνι να ακουμπήσει το πράσινο πριν ακουμπήσει το καφέ;
kostas1507
Δημοσιεύσεις: 33
Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm

Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021

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

Προγραμματίστηκε η μηνιαία συνάντηση στο 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
bettypan
Δημοσιεύσεις: 14
Εγγραφή: Σάβ Ιούλ 25, 2020 12:44 pm

Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021

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

Καλησπέρα!
Υπάρχει μήπως κάποιο πρόβλημα με το link και το meeting id?
Ή μόνο εμείς έχουμε πρόβλημα;
kostas1507
Δημοσιεύσεις: 33
Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm

Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021

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

Καλησπέρα, και εγώ βλέπω ότι δεν μπορώ να μπω. Θα μιλήσω τώρα με τον Βαγγέλη.
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021

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

Το κοιτάω κι εγώ τώρα παιδιά, με συγχωρείτε. Ελπίζω ότι σε δέκα λεπτά θα μπορούμε να μπούμε όλοι :)
Λύσεις θεμάτων ΠΔΠ: 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/
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 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/
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Mηνιαία Πρόκληση: Φεβρουάριος 2021

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

Ορίστε ψευδοκώδικας για το πρόβλημα!
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/
Απάντηση