Μηνιαία Πρόκληση: Δεκέμβριος 2020

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 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, θυμίστε το αν το ξεχάσουμε.
Καλή επιτυχία!
Λύσεις θεμάτων ΠΔΠ: 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/
radaiosm7
Δημοσιεύσεις: 18
Εγγραφή: Δευ Μαρ 23, 2020 6:31 pm

Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020

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

Καλησπέρα σε όλους!

Το hint είναι το εξής:
Α) Αν σου εγγυόμουν ότι οι διαδοχικές διαφορές είναι πάντα μεταξύ 100 και 200, θα μπορούσες να λύσεις πολύ γρήγορα το πρόβλημα;
Β) Αξιοποίησε αυτή την παρατήρηση για να λύσεις το γενικό πρόβλημα :P

Καλή συνέχεια!
radaiosm7
Δημοσιεύσεις: 18
Εγγραφή: Δευ Μαρ 23, 2020 6:31 pm

Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020

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

Καλησπέρα και πάλι!

Είπαμε τελικά να σας δώσουμε άλλα δύο μικρά hints:
Α) Το πρώτο hint που δώσαμε (με τις μικρές διαφορές) λύνεται σε Ο(1).
Β) Το γενικό πρόβλημα λύνεται σε O(loglog(MAX_VALUE)).
AndreasRasvanis
Δημοσιεύσεις: 6
Εγγραφή: Τρί Δεκ 22, 2020 3:46 pm

Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020

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

Γινεται να χρησημοποιησουμε treaps σε segment tree η οτιδηποτε μπορουμε , και τα queries πρεπει να ειναι online η μπορει και offline με καποι προυοπολογισμο πιο πριν και μετα offline να τα απανταμε σε O(1).
Spoiler: show
To μονο που εχω σκεφτει εκτος απο bs που ειναι LogN Per query ειναι ειτε κανενα merge sort tree και ξερω γω κατι με segment tree οπου αποθηκευθουμε treaps στα Nodes αλλα ειναι χειροτερο και απο logN.
AndreasRasvanis
Δημοσιεύσεις: 6
Εγγραφή: Τρί Δεκ 22, 2020 3:46 pm

Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020

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

Και γινεται ακομα η κληση γιατι εχω να μπω απο πριν παω στην ejoi σας εχασα μετα βλεπω βγαζετε και βοηθους τωρα!!!
AndreasRasvanis
Δημοσιεύσεις: 6
Εγγραφή: Τρί Δεκ 22, 2020 3:46 pm

Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020

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

Και εννοειτε καθε query σε O(loglog(MAX))? γιατι ειναι ουσιαστικα περρισοτερο προς το Ο(1) αυτο
radaiosm7
Δημοσιεύσεις: 18
Εγγραφή: Δευ Μαρ 23, 2020 6:31 pm

Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020

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

Καλησπέρα Αντρέα!
AndreasRasvanis έγραψε: Τρί Δεκ 22, 2020 3:53 pm Γινεται να χρησημοποιησουμε treaps σε segment tree η οτιδηποτε μπορουμε ,
Ναι, επιτρέπεται να χρησιμοποιήσεις ό,τι θέλεις, απλώς υπάρχει απλούστατη λύση χωρίς ψαγμένες δομές δεδομένων.
AndreasRasvanis έγραψε: Τρί Δεκ 22, 2020 3:53 pm τα queries πρεπει να ειναι online η μπορει και offline με καποι προυοπολογισμο πιο πριν και μετα offline να τα απανταμε σε O(1).
Στην εκδοχή που συζητάμε, τα ερωτήματα πρέπει να τα απαντάς online. Παρόλα αυτά, αν έχεις κάποια ενδιαφέρουσα ιδέα για offline, καλύτερη από O(logN) ανά ερώτημα, θα χαρούμε να τη μοιραστείς στην προσεχή κλήση.
AndreasRasvanis έγραψε: Τρί Δεκ 22, 2020 4:47 pm Και εννοειτε καθε query σε O(loglog(MAX))? γιατι ειναι ουσιαστικα περρισοτερο προς το Ο(1) αυτο
Ακριβώς, κάθε query σε O(loglog(MAX_VALUE)). Εφόσον καταλαβαίνω τι εννοείς, πράγματι το Ο(loglog(MAX_VALUE)) είναι κοντά στο Ο(1) αλλά και το O(logN) θα μπορούσε να πει κανείς ότι είναι κοντά στο Ο(1), αλλά δεν είναι Ο(1). Επίσης, μη ξεχνάς ότι εξαρτώνται από διαφορετική μεταβλητή, το ένα από το Ν και το άλλο από το MAX_VALUE.
AndreasRasvanis έγραψε: Τρί Δεκ 22, 2020 3:54 pmΚαι γινεται ακομα η κληση γιατι εχω να μπω απο πριν παω στην ejoi σας εχασα μετα βλεπω βγαζετε και βοηθους τωρα!!!
Γίνεται ακόμα η κλήση και θα χαρούμε να σε δούμε την επόμενη φορά (διάβασε το πρώτο ποστ, του Βαγγέλη, για λεπτομέρειες). Αυτό με τους βοηθούς γίνεται για πρώτη φορά, αυτόν τον μήνα.
bettypan
Δημοσιεύσεις: 14
Εγγραφή: Σάβ Ιούλ 25, 2020 12:44 pm

Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020

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

Να ρωτήσω και εγώ κάτι : έχει σημασία να γνωρίζουμε πώς "κατανέμονται" τα στοιχεία του πίνακα;
Οι διαφορές τους αυξάνονται, οκ, αλλά αυτή η αύξηση είναι "ομαλή¨, γραμμική;
Βρήκα κάτι, αλλα , νομίζω, προΰποθέτει ομαλή κατανομή των στοιχείων του πίνακα....
bettypan
Δημοσιεύσεις: 14
Εγγραφή: Σάβ Ιούλ 25, 2020 12:44 pm

Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020

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

συγγνώμη , *ομαλή= ομοιόμορφη
radaiosm7
Δημοσιεύσεις: 18
Εγγραφή: Δευ Μαρ 23, 2020 6:31 pm

Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020

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

Καλησπέρα Μπέττυ!
bettypan έγραψε: Τετ Δεκ 30, 2020 12:56 am αυτή η αύξηση είναι "ομαλή¨, γραμμική;
(Προσπαθώντας να μη δώσω hint :lol:)

Αν καταλαβαίνω τι ρωτάς, όχι. Για παράδειγμα ο πίνακας [1, 2, 2^32] είναι έγκυρος. Αν δε σε κάλυψα ξαναρώτα :)
radaiosm7
Δημοσιεύσεις: 18
Εγγραφή: Δευ Μαρ 23, 2020 6:31 pm

Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020

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

Καλησπέρα και καλή χρονιά σε όλους!

Η συνάντηση θα γίνει το επόμενο Σάββατο, 9 Ιανουαρίου, 15:00 ώρα Ελλάδος.
Το link για το zoom είναι: https://ucph-ku.zoom.us/j/67586825824?p ... sveG9qZz09

Meeting ID: 675 8682 5824
Passcode: 988982

Μην ξεχάσετε να κατεβάσετε την εφαρμογή του zoom για να έχετε πρόσβαση στον ασπροπίνακα, καθώς η online έκδοση δε δίνει τέτοια δυνατότητα.

Τα λέμε τότε!
bettypan
Δημοσιεύσεις: 14
Εγγραφή: Σάβ Ιούλ 25, 2020 12:44 pm

Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020

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

Καλή Χρονιά σε όλους...!!!
Σήμερα δεν είναι η κλήση;
radaiosm7
Δημοσιεύσεις: 18
Εγγραφή: Δευ Μαρ 23, 2020 6:31 pm

Re: Μηνιαία Πρόκληση: Δεκέμβριος 2020

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

Καλησπέρα, σήμερα είναι αλλά υποθέτω ότι ο Βαγγέλης έχει κάποιο θέμα με τη σύνδεση, οπότε περιμένουμε.
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 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/
Απάντηση