Μηνιαία Πρόκληση: Δεκέμβριος 2020
Δημοσιεύτηκε: Κυρ Δεκ 06, 2020 8:35 pm
Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Δεκέμβριο. Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση. Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς. Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου στο τέλος του μήνα θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Σημείωση: Ένας από τους συμμετέχοντες της σύσκεψης θα επιλέγεται ώστε να με βοηθήσει με την επόμενη μηνιαία πρόκληση, αυτή του Ιανουαρίου εν προκειμένω. Οι αρμοδιότητές του θα είναι να λύσει το επόμενο πρόβλημα εντός του μήνα (εννοείται με συνεννόηση/βοήθεια από εμένα) ώστε να είναι σε θέση να λύνει απορίες στην επόμενη σύσκεψη και στο forum (και πάλι, εννοείται θα είμαι κι εγώ στη σύσκεψη, οπότε δεν αγχωνόμαστε "Τι θα γίνει αν δε μπορώ να απαντήσω σε κάποια ερώτηση;").
Από τη σύσκεψη Νοεμβρίου έχει επιλεγεί ήδη ο Μάρκος ως βοηθός Δεκεμβρίου.
Στο πρόβλημα μας δίνεται ένας πίνακας με N<=50.000.000 ταξινομημένους αριθμούς (κάθε αριθμός είναι θετικός και χωράει σε long long).
Το πρόβλημα μας εγγυάται ότι οι διαδοχικές διαφορές των αριθμών είναι σε αύξουσα σειρά.
Έτσι για παράδειγμα ένα πιθανό input θα ήταν το
[1, 3, 10, 17, 50, 1000], καθώς οι διαδοχικές διαφορές (2,7,7,33,950) πράγματι είναι σε αύξουσα σειρά.
Ένα άκυρο παράδειγμα εισόδου θα ήταν το
[2, 1, 4], καθώς δεν είναι ταξινομημένο.
Ένα ακόμα άκυρο παράδειγμα εισόδου είναι το
[1, 3, 4, 10, 18] καθώς οι διαδοχικές διαφορές (2,1,6,8) δεν είναι σε αύξουσα σειρά.
Κατόπιν μας δίνονται Q<=Ν ερωτήματα. Το κάθε ερώτημα μας δίνει έναν αριθμό Χ, και ζητείται να βρούμε τον predecessor του Χ, τον μέγιστο αριθμό είναι μικρότερος του Χ.
Για παράδειγμα στον πίνακα
[1, 3, 7]
έχουμε predecessor(2) = predecessor(3) = 1, predecessor(6) = 3, predecessor(999) = 7.
Στόχος είναι να ξοδέψουμε λιγότερο από Ο(logN) χρόνο ανά ερώτημα, και μόνο γραμμικό χώρο.
Bonus πληροφορία: Το παραπάνω πρόβλημα λύνεται βέλτιστα σε Ο(1) χρόνο, αλλά η λύση αυτή ξεπερνάει κατά πολύ τις γνώσεις που απαιτούνται για τους διαγωνισμούς.
Στις 15 του μηνός θα δώσουμε ένα hint, θυμίστε το αν το ξεχάσουμε.
Καλή επιτυχία!
Περίπου στο τέλος του μήνα θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Σημείωση: Ένας από τους συμμετέχοντες της σύσκεψης θα επιλέγεται ώστε να με βοηθήσει με την επόμενη μηνιαία πρόκληση, αυτή του Ιανουαρίου εν προκειμένω. Οι αρμοδιότητές του θα είναι να λύσει το επόμενο πρόβλημα εντός του μήνα (εννοείται με συνεννόηση/βοήθεια από εμένα) ώστε να είναι σε θέση να λύνει απορίες στην επόμενη σύσκεψη και στο forum (και πάλι, εννοείται θα είμαι κι εγώ στη σύσκεψη, οπότε δεν αγχωνόμαστε "Τι θα γίνει αν δε μπορώ να απαντήσω σε κάποια ερώτηση;").
Από τη σύσκεψη Νοεμβρίου έχει επιλεγεί ήδη ο Μάρκος ως βοηθός Δεκεμβρίου.
Στο πρόβλημα μας δίνεται ένας πίνακας με N<=50.000.000 ταξινομημένους αριθμούς (κάθε αριθμός είναι θετικός και χωράει σε long long).
Το πρόβλημα μας εγγυάται ότι οι διαδοχικές διαφορές των αριθμών είναι σε αύξουσα σειρά.
Έτσι για παράδειγμα ένα πιθανό input θα ήταν το
[1, 3, 10, 17, 50, 1000], καθώς οι διαδοχικές διαφορές (2,7,7,33,950) πράγματι είναι σε αύξουσα σειρά.
Ένα άκυρο παράδειγμα εισόδου θα ήταν το
[2, 1, 4], καθώς δεν είναι ταξινομημένο.
Ένα ακόμα άκυρο παράδειγμα εισόδου είναι το
[1, 3, 4, 10, 18] καθώς οι διαδοχικές διαφορές (2,1,6,8) δεν είναι σε αύξουσα σειρά.
Κατόπιν μας δίνονται Q<=Ν ερωτήματα. Το κάθε ερώτημα μας δίνει έναν αριθμό Χ, και ζητείται να βρούμε τον predecessor του Χ, τον μέγιστο αριθμό είναι μικρότερος του Χ.
Για παράδειγμα στον πίνακα
[1, 3, 7]
έχουμε predecessor(2) = predecessor(3) = 1, predecessor(6) = 3, predecessor(999) = 7.
Στόχος είναι να ξοδέψουμε λιγότερο από Ο(logN) χρόνο ανά ερώτημα, και μόνο γραμμικό χώρο.
Bonus πληροφορία: Το παραπάνω πρόβλημα λύνεται βέλτιστα σε Ο(1) χρόνο, αλλά η λύση αυτή ξεπερνάει κατά πολύ τις γνώσεις που απαιτούνται για τους διαγωνισμούς.
Στις 15 του μηνός θα δώσουμε ένα hint, θυμίστε το αν το ξεχάσουμε.
Καλή επιτυχία!