Μηνιαία Πρόκληση: Δεκέμβριος 2020
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Μηνιαία Πρόκληση: Δεκέμβριος 2020
Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Δεκέμβριο. Κάθε αρχή του μήνα θα ανεβαίνει στο 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, θυμίστε το αν το ξεχάσουμε.
Καλή επιτυχία!
Λύσεις θεμάτων ΠΔΠ: 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/
Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020
Καλησπέρα σε όλους!
Το hint είναι το εξής:
Α) Αν σου εγγυόμουν ότι οι διαδοχικές διαφορές είναι πάντα μεταξύ 100 και 200, θα μπορούσες να λύσεις πολύ γρήγορα το πρόβλημα;
Β) Αξιοποίησε αυτή την παρατήρηση για να λύσεις το γενικό πρόβλημα
Καλή συνέχεια!
Το hint είναι το εξής:
Α) Αν σου εγγυόμουν ότι οι διαδοχικές διαφορές είναι πάντα μεταξύ 100 και 200, θα μπορούσες να λύσεις πολύ γρήγορα το πρόβλημα;
Β) Αξιοποίησε αυτή την παρατήρηση για να λύσεις το γενικό πρόβλημα
Καλή συνέχεια!
Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020
Καλησπέρα και πάλι!
Είπαμε τελικά να σας δώσουμε άλλα δύο μικρά hints:
Α) Το πρώτο hint που δώσαμε (με τις μικρές διαφορές) λύνεται σε Ο(1).
Β) Το γενικό πρόβλημα λύνεται σε O(loglog(MAX_VALUE)).
Είπαμε τελικά να σας δώσουμε άλλα δύο μικρά hints:
Α) Το πρώτο hint που δώσαμε (με τις μικρές διαφορές) λύνεται σε Ο(1).
Β) Το γενικό πρόβλημα λύνεται σε O(loglog(MAX_VALUE)).
-
- Δημοσιεύσεις: 6
- Εγγραφή: Τρί Δεκ 22, 2020 3:46 pm
Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020
Γινεται να χρησημοποιησουμε treaps σε segment tree η οτιδηποτε μπορουμε , και τα queries πρεπει να ειναι online η μπορει και offline με καποι προυοπολογισμο πιο πριν και μετα offline να τα απανταμε σε O(1).
- Spoiler: show
-
- Δημοσιεύσεις: 6
- Εγγραφή: Τρί Δεκ 22, 2020 3:46 pm
Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020
Και γινεται ακομα η κληση γιατι εχω να μπω απο πριν παω στην ejoi σας εχασα μετα βλεπω βγαζετε και βοηθους τωρα!!!
-
- Δημοσιεύσεις: 6
- Εγγραφή: Τρί Δεκ 22, 2020 3:46 pm
Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020
Και εννοειτε καθε query σε O(loglog(MAX))? γιατι ειναι ουσιαστικα περρισοτερο προς το Ο(1) αυτο
Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020
Καλησπέρα Αντρέα!
Ναι, επιτρέπεται να χρησιμοποιήσεις ό,τι θέλεις, απλώς υπάρχει απλούστατη λύση χωρίς ψαγμένες δομές δεδομένων.AndreasRasvanis έγραψε: ↑Τρί Δεκ 22, 2020 3:53 pm Γινεται να χρησημοποιησουμε treaps σε segment tree η οτιδηποτε μπορουμε ,
Στην εκδοχή που συζητάμε, τα ερωτήματα πρέπει να τα απαντάς online. Παρόλα αυτά, αν έχεις κάποια ενδιαφέρουσα ιδέα για offline, καλύτερη από O(logN) ανά ερώτημα, θα χαρούμε να τη μοιραστείς στην προσεχή κλήση.AndreasRasvanis έγραψε: ↑Τρί Δεκ 22, 2020 3:53 pm τα queries πρεπει να ειναι online η μπορει και offline με καποι προυοπολογισμο πιο πριν και μετα offline να τα απανταμε σε O(1).
Ακριβώς, κάθε query σε O(loglog(MAX_VALUE)). Εφόσον καταλαβαίνω τι εννοείς, πράγματι το Ο(loglog(MAX_VALUE)) είναι κοντά στο Ο(1) αλλά και το O(logN) θα μπορούσε να πει κανείς ότι είναι κοντά στο Ο(1), αλλά δεν είναι Ο(1). Επίσης, μη ξεχνάς ότι εξαρτώνται από διαφορετική μεταβλητή, το ένα από το Ν και το άλλο από το MAX_VALUE.AndreasRasvanis έγραψε: ↑Τρί Δεκ 22, 2020 4:47 pm Και εννοειτε καθε query σε O(loglog(MAX))? γιατι ειναι ουσιαστικα περρισοτερο προς το Ο(1) αυτο
Γίνεται ακόμα η κλήση και θα χαρούμε να σε δούμε την επόμενη φορά (διάβασε το πρώτο ποστ, του Βαγγέλη, για λεπτομέρειες). Αυτό με τους βοηθούς γίνεται για πρώτη φορά, αυτόν τον μήνα.AndreasRasvanis έγραψε: ↑Τρί Δεκ 22, 2020 3:54 pmΚαι γινεται ακομα η κληση γιατι εχω να μπω απο πριν παω στην ejoi σας εχασα μετα βλεπω βγαζετε και βοηθους τωρα!!!
Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020
Να ρωτήσω και εγώ κάτι : έχει σημασία να γνωρίζουμε πώς "κατανέμονται" τα στοιχεία του πίνακα;
Οι διαφορές τους αυξάνονται, οκ, αλλά αυτή η αύξηση είναι "ομαλή¨, γραμμική;
Βρήκα κάτι, αλλα , νομίζω, προΰποθέτει ομαλή κατανομή των στοιχείων του πίνακα....
Οι διαφορές τους αυξάνονται, οκ, αλλά αυτή η αύξηση είναι "ομαλή¨, γραμμική;
Βρήκα κάτι, αλλα , νομίζω, προΰποθέτει ομαλή κατανομή των στοιχείων του πίνακα....
Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020
συγγνώμη , *ομαλή= ομοιόμορφη
Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020
Καλησπέρα και καλή χρονιά σε όλους!
Η συνάντηση θα γίνει το επόμενο Σάββατο, 9 Ιανουαρίου, 15:00 ώρα Ελλάδος.
Το link για το zoom είναι: https://ucph-ku.zoom.us/j/67586825824?p ... sveG9qZz09
Meeting ID: 675 8682 5824
Passcode: 988982
Μην ξεχάσετε να κατεβάσετε την εφαρμογή του zoom για να έχετε πρόσβαση στον ασπροπίνακα, καθώς η online έκδοση δε δίνει τέτοια δυνατότητα.
Τα λέμε τότε!
Η συνάντηση θα γίνει το επόμενο Σάββατο, 9 Ιανουαρίου, 15:00 ώρα Ελλάδος.
Το link για το zoom είναι: https://ucph-ku.zoom.us/j/67586825824?p ... sveG9qZz09
Meeting ID: 675 8682 5824
Passcode: 988982
Μην ξεχάσετε να κατεβάσετε την εφαρμογή του zoom για να έχετε πρόσβαση στον ασπροπίνακα, καθώς η online έκδοση δε δίνει τέτοια δυνατότητα.
Τα λέμε τότε!
Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020
Καλή Χρονιά σε όλους...!!!
Σήμερα δεν είναι η κλήση;
Σήμερα δεν είναι η κλήση;
Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020
Καλησπέρα, σήμερα είναι αλλά υποθέτω ότι ο Βαγγέλης έχει κάποιο θέμα με τη σύνδεση, οπότε περιμένουμε.
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020
Παιδιά χίλια συγγνώμη, δικό μου λάθος, νόμιζα αρχίζαμε μία ώρα μετά. Η κλήση ξεκινάει τώρα για όποιον θέλει να συμμετέχει, και θα γίνει record ώστε να την πάρει όποιος δεν μπόρεσε να βρεθεί λόγω του λάθους μου.
Και πάλι συγγνώμη.
Και πάλι συγγνώμη.
Λύσεις θεμάτων ΠΔΠ: 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/