Online Διαγωνισμός Εξάσκησης Δεκεμβρίου 2015

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

Online Διαγωνισμός Εξάσκησης Δεκεμβρίου 2015

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

O διαγωνισμός θα ανοίξει την Πέμπτη 24 Δεκεμβρίου 2015 στις 07:00 και θα διαρκέσει μέχρι την Τρίτη 5 Ιανουαρίου 2016 στις 22:00. Οι διαγωνιζόμενοι θα μπορούν να συμμετάσχουν οποιαδήποτε στιγμή επιθυμούν μέσα σε αυτό το διάστημα και θα έχουν τρεις ώρες στην διάθεση τους από τη στιγμή που θα ανοίξουν τα προβλήματα. Θα δοθούν τέσσερα (4) νέα προβλήματα κλιμακούμενης δυσκολίας τα οποία έχουν ετοιμαστεί από τους διοργανωτές ειδικά για αυτό τον διαγωνισμό. Δεν υπάρχει περιορισμός στην ηλικία και μπορεί να συμμετάσχει οποιοσδήποτε.

Για οποιαδήποτε απορία μην διστάσετε να επικοινωνήσετε μαζί μας στην ηλ. διεύθυνση hellenico.contests@gmail.com.

Οι διοργανωτές,
Κυριάκος Αξιώτης, Βαγγέλης Κηπουρίδης, Παναγιώτης Κωστοπαναγιώτης, Δημήτρης Λως, Γιώργος Χρίστογλου
Λύσεις θεμάτων ΠΔΠ: 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/
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Online Διαγωνισμός Εξάσκησης Δεκεμβρίου 2015

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

Καλή χρονιά σε όλους, στο intervals αναφέρει ότι οι
Περιορισμοί


Subtask 1 (10 pts)
- 0 < i, j <= 10^2 και 0 < Μ <= 10^5

Subtask 2 (10 pts)
- 0 < i, j <= 10^5 και 0 < Μ <= 5*10^3

Subtask 3 (40 pts)
- 0 < i, j <= 10^5 και 0 < Μ <= 3*10^5
- Δεν υπάρχουν removals

Subtask 4 (40 pts)
- 0 < i, j < 10^5 και 0 < Μ <= 3*10^5

Όριο χρόνου εκτέλεσης: 3 sec.
Στο δέντρο που θα πρέπει να γίνει, αν δεν γίνει balanced και έρθουν ταξινομημένα τα δεδομένα, θα έχουμε καταλήξει σε linked list και σειρική αναζήτηση. Θεωρείται ικανοποιητική λύση το unbalanced δένδρο για τέτοιο πρόβλημα;
infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: Online Διαγωνισμός Εξάσκησης Δεκεμβρίου 2015

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

switch έγραψε:Καλή χρονιά σε όλους, στο intervals αναφέρει ότι οι
Περιορισμοί


Subtask 1 (10 pts)
- 0 < i, j <= 10^2 και 0 < Μ <= 10^5

Subtask 2 (10 pts)
- 0 < i, j <= 10^5 και 0 < Μ <= 5*10^3

Subtask 3 (40 pts)
- 0 < i, j <= 10^5 και 0 < Μ <= 3*10^5
- Δεν υπάρχουν removals

Subtask 4 (40 pts)
- 0 < i, j < 10^5 και 0 < Μ <= 3*10^5

Όριο χρόνου εκτέλεσης: 3 sec.
Στο δέντρο που θα πρέπει να γίνει, αν δεν γίνει balanced και έρθουν ταξινομημένα τα δεδομένα, θα έχουμε καταλήξει σε linked list και σειρική αναζήτηση. Θεωρείται ικανοποιητική λύση το unbalanced δένδρο για τέτοιο πρόβλημα;
Εξαρτάται απ' το τι πολυπλοκότητα θα έχουμε σε κάθε query, αν είναι O( n ), μάλλον δεν είναι επαρκής η λύση. Ωστόσο δεν έχω καταλάβει ακριβώς για ποιά λύση μιλάμε.
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Online Διαγωνισμός Εξάσκησης Δεκεμβρίου 2015

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

infinity έγραψε:...
Εξαρτάται απ' το τι πολυπλοκότητα θα έχουμε σε κάθε query, αν είναι O( n ), μάλλον δεν είναι επαρκής η λύση. Ωστόσο δεν έχω καταλάβει ακριβώς για ποιά λύση μιλάμε.
Για το πέταγμα της ... Πηνελόπης
http://hellenico.gr/contest/?page=problem&id=227

Θα περιμένω να ανακοινωθούν και τα αρχεία ελέγχου για να δω πως θα πάμε (στυλ reverse engineering) καθότι δεν υπάρχει ξεκάθαρα ύλη ανά κατηγορία απ'ότι κατάλαβα.
infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: Online Διαγωνισμός Εξάσκησης Δεκεμβρίου 2015

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

switch έγραψε:
infinity έγραψε:...
Εξαρτάται απ' το τι πολυπλοκότητα θα έχουμε σε κάθε query, αν είναι O( n ), μάλλον δεν είναι επαρκής η λύση. Ωστόσο δεν έχω καταλάβει ακριβώς για ποιά λύση μιλάμε.
Για το πέταγμα της ... Πηνελόπης
http://hellenico.gr/contest/?page=problem&id=227

Θα περιμένω να ανακοινωθούν και τα αρχεία ελέγχου για να δω πως θα πάμε (στυλ reverse engineering) καθότι δεν υπάρχει ξεκάθαρα ύλη ανά κατηγορία απ'ότι κατάλαβα.
Εννοούσα βασικά για ποιά λύση συγκεκριμένα λέμε, με ποιό τρόπο θα χρησιμοποιηθεί το δέντρο κτλ. :P
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Online Διαγωνισμός Εξάσκησης Δεκεμβρίου 2015

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

infinity έγραψε: Εννοούσα βασικά για ποιά λύση συγκεκριμένα λέμε, με ποιό τρόπο θα χρησιμοποιηθεί το δέντρο κτλ. :P
Ούπς... :P

Μια παραλλαγή της τυπικής:
https://en.wikipedia.org/wiki/Interval_tree
Απάντηση