Online μάθημα 28 Μαρτίου 2020

[Κηπουρίδης]

Πρόσκληση σε #Online ΜΑΘΗΜΑ ΠΔΠ | ΣΑΒΒΑΤΟ 28 ΜΑΡΤΙΟΥ 2020 | ΏΡΑ: 11:00

Αγαπητές μαθήτριες και αγαπητοί μαθητές,
Το επόμενο μάθημα προετοιμασίας για τον ΠΔΠ στη Θεσσαλονίκη θα γίνει online.

Η πλατφόρμα που θα χρησιμοποιήσουμε είναι η Zoom. Για όσους θέλετε να συμμετέχετε απλά κάνετε κλικ στο παρακάτω URL. Έχετε υπόψη σας ότι κάποιοι browser υποστηρίζουν απευθείας την κλήση, χωρίς να χρειάζεται να κατεβάσετε την εφαρμογή, ενώ άλλοι όχι, οπότε θα χρειαστεί να την κατεβάσετε.

------------------ Πρόσκληση ------------------------------
Topic: Μάθημα Προετοιμασίας ΠΔΠ
Time: Mar 28, 2020 11:00-12:00 AM Athens

Join Zoom Meeting
https://ucph-ku.zoom.us/j/628138053

Meeting ID: 628 138 053

------------------ Περιγραφή ------------------------------
Εισηγητής: Βαγγέλης Κηπουρίδης
1) Θα δούμε τη δομή δεδομένων trie.
) Θα συζητήσουμε τα προβλήματα της Β' Φάσης.
) Θα συζητήσουμε γενικές απορίες σας.


Χωρίς να είναι απαραίτητο, θα βοηθούσε αν γράφατε εδώ πέρα τις γενικές απορίες σας που θέλετε να συζητήσουμε, ώστε να προετοιμαστώ κι εγώ κατάλληλα!

Τα λέμε το Σάββατο!

[nikoskon]

Μπορούν να συμμετάσχουν και άτομα απο Αθήνα;

[Κηπουρίδης]

Μπορούν να συμμετάσχουν και άτομα απο Αθήνα;

Αρκεί να υποσχεθούν να σκεφτούν σοβαρά τι είναι το σουβλάκι και τι το καλαμάκι.

[Κηπουρίδης]

Καλησπέρα παιδιά,

ολοκληρώθηκε σήμερα το online μάθημα για το διαγωνισμό, όπου γνωριστήκαμε με τη δομή δεδομένων trie. Η δομή αυτή στην ουσία λύνει το πρόβλημα του autocomplete: https://www.mytechlogy.com/upload/by_us ... eteAPI.jpg

Οι εξαιρετικές διαφάνειες που δίδαξαν κάθε Έλληνα διαγωνιζόμενο, τις οποίες έκανε ο Χατζημίχος και τον ευχαριστούμε, βρίσκονται εδώ: http://snf-800715.vm.okeanos.grnet.gr/P ... e/trie.pdf

Συνημμένο θα βρείτε τον κώδικα για το trie που γράψαμε μαζί.

trie.cpp

Κώδικας για trie.

(1.89 KiB) Μεταφορτώθηκε 270 φορές

Διαβάζει N κείμενα, και κατόπιν ένα καινούργιο κείμενο-ερώτημα. Στόχος μας είναι να βρούμε πόσα από τα Ν κείμενα έχουν ως πρόθεμα το κείμενο-ερώτημα (ξεκινούνε δηλαδή ακριβώς έτσι). Προφανώς βάζοντας το τελευταίο ερώτημα μέσα σε μία for, μπορούμε να απαντήσουμε σε πολλά ερωτήματα, γιατί η παρούσα εκφώνηση λύνεται εξίσου αποδοτικά και με brute force!

Ένα πρόβλημα που μπορείτε τώρα να λύσετε είναι το πρόβλημα lottery (Γ Φάση 31ου ΠΔΠ): https://pdp-archive.github.io/31-PDP/index
Στο παραπάνω link μπορείτε να βρείτε και μία κάπως αναλυτική συζήτηση για της λύσης, όμως θα σας βοηθήσει πολύ αν το προσπαθήσετε μόνοι σας για 2 μέρες.

Ως προς τις πηγές που σας προτείνουμε να έχετε υπόψιν:
Λυμένα θέματα: https://pdp-archive.github.io/
Οδηγός διαβάσματος: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials για πολλά ενδιαφέροντα θέματα: https://kallinikos.github.io/
Και φυσικά το παρόν forum (pdpforum.eu.org) καθώς οι moderators βρισκόμαστε πάντα σε ετοιμότητα να απαντήσουμε ερωτήσεις, ακόμα και τις περιόδους που κανείς δε γράφει

Επιπλέον διαγωνισμοί που μπορείτε να παίρνετε μέρος για εξάσκηση είναι (με σειρά προτίμησης μου):
Hellenico Contests (μια φορά το τρίμηνο)
COCI (κάθε μήνα)
Usaco (κάθε μήνα)
Codeforces (ακόμα συχνότερα, χωρίς συγκεκριμένο χρονοδιάγραμμα)
Codejam
Topcoder

Εάν ξέχασα να ανεβάσω κάτι που είχα υποσχεθεί στο μάθημα, παρακαλώ ενημερώστε με. Υπενθυμίζω ότι είχαμε και πέντε παλικάρια που είπαν ότι θα απαντήσουν σε αυτή την ερώτηση: viewtopic.php?f=9&p=9510#p9510