pdp forum

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

Κάθε αρχή του μήνα θα ανεβαίνει στο 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 του μηνός, μέχρι τότε προσποιηθείτε ότι γνωρίζετε πώς λύνεται!

Καλησπέρα και συγγνώμη για την λογικά ηλίθια ερώτηση αλλά τι εννοείται με το

Ζητείται αλγόριθμος είτε Ο(ΝlogN) είτε Ο(Ν).

Έψαχνα σε αγγλικά φόρουμς αλλά δεν μπορούσα να καταλάβω. Θα μπορούσε κάποιος να το εξηγήσει ?

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

Γραμμικό ή 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 δεν τελειώνει σε καλό χρόνο για διαγωνισμό.

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


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




2: Υπάρχει περίπτωση, στην παραπάνω εικόνα, το κόκκινο μπαλόνι να ακουμπήσει το πράσινο πριν ακουμπήσει το καφέ;

Προγραμματίστηκε η μηνιαία συνάντηση στο 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

Καλησπέρα!
Υπάρχει μήπως κάποιο πρόβλημα με το link και το meeting id?
Ή μόνο εμείς έχουμε πρόβλημα;

Καλησπέρα, και εγώ βλέπω ότι δεν μπορώ να μπω. Θα μιλήσω τώρα με τον Βαγγέλη.

Το κοιτάω κι εγώ τώρα παιδιά, με συγχωρείτε. Ελπίζω ότι σε δέκα λεπτά θα μπορούμε να μπούμε όλοι

Δεν έβγαλα άκρη, οπότε δημιούργησα καινούργιο δωμάτιο: https://ucph-ku.zoom.us/j/62298579631?p ... RQZitYZz09

Ορίστε ψευδοκώδικας για το πρόβλημα!
https://imgur.com/2AUixgH

Προφανώς αν δεν έχετε δει την επεξήγηση και δείτε απευθείας τον κώδικα, θα φανεί εντελώς ακατανόητος. Υπενθυμίζω ότι έχουμε recording με επεξήγηση της λύσης, όποιος το χρειαστεί ας μου στείλει προσωπικό μήνυμα.