Υλη για PDP

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
Kawaii_Penguin
Δημοσιεύσεις: 1
Εγγραφή: Παρ Μαρ 06, 2015 5:09 pm

Υλη για PDP

Δημοσίευση από Kawaii_Penguin » Παρ Μαρ 06, 2015 5:19 pm

Θελω να ξερω ποιά πραγματα πρεπει να ξερω για να μπορω να τα παω καλά στο ΠΔΠ . Απο πλευρας αλγορυθμων , Data structures , etc . Υπαρχει πουθενα η επισημη υλη η τιποτα τετοιό ?

Άβαταρ μέλους
switch
Δημοσιεύσεις: 31
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am

Re: Υλη για PDP

Δημοσίευση από switch » Σάβ Δεκ 05, 2015 12:14 pm

Καλημέρα, έχω και εγώ απορία σε σχέση με την ύλη. Δεν είμαι διαγωνιζόμενος, αλλά γονιός μαθητή γυμνασίου.

Σε όλα σχεδόν τα προβλήματα, υπάρχουν διάφορες λύσεις.
Π.χ. κοίταγα το sumx, που η απλή λύση είναι με 2πλό loop και πρέπει να βρεθεί ο αριθμός των ζευγών από μια τυχαία σειρά Ν αριθμών που έχει συγκεκριμένο άθροισμα.

Η εύκολη λύση είναι με ενφωλευμένα loop:

Κώδικας: Επιλογή όλων

for(i=0;i<n;i++)
         for(j=i+1;j<n;j++)
                 ....
Αν γίνει με απλά ενφωλευμένα loop τότε, όσο αυξάνεται το Ν (άνω όριο για το Ν είναι το 1.000.000), τότε μπορεί να φτάσουμε και στο μισό λεπτό. Αν όμως χρησιμοποιηθεί qsort/bsearch, πέφτουμε στα 2,5 δευτερόλεπτα και αν χρησιμοποιηθούν m-trees, τότε πάμε στα 1,5 sec.

Σε τι επίπεδο πρέπει να βασίζεται η προετοιμασία των υποψηφίων για το διαγωνισμό;
Στην εκφώνηση αναφέρει μέγιστο Ν το 1.000.000 και δίνει και μέγιστο χρόνο εκτέλεσης.
Ο χρόνος αυτός ισχύει για το μέγιστο Ν;
Τα όρια του Ν δίνονται μόνο για να επιλεχθεί ο σωστός τύπος ακεραίου ή θα γίνει δοκιμή με αυτά τα όρια;

kostantinaras
Δημοσιεύσεις: 14
Εγγραφή: Πέμ Μαρ 08, 2012 3:40 pm

Re: Υλη για PDP

Δημοσίευση από kostantinaras » Σάβ Δεκ 05, 2015 11:32 pm

Γενικά για το διαγωνισμό δεν υπάρχει συγκεκριμένη ύλη αλλά βρίσκεται στα πλαίσια αυτής της ΙΟΙ.
http://people.ksp.sk/~misof/ioi-syllabu ... s-2013.pdf

Το sumx λύνεται πολύ πιο απλά από m-trees (που νομίζω δεν είναι καν στην ύλη της IOI).Εκμεταλλευόμαστε το γεγονός ότι οι αριθμοί είναι μικρότεροι ή ίσοι του 1000000 και έτσι αποθηκεύουμε σε έναν πίνακα στην i-στη θέση το πλήθος των αριθμών που βρήκαμε που είναι ίσοι με i.Έτσι για κάθε αριθμό α βρίσκουμε το πλήθος των αριθμών πριν από το α που είναι ίσοι με Χ-α σε Ο(1) με συνολική πολυπλοκότητα αλγορίθμου Ο(n).Μία λύση είναι εδώ http://git.softlab.ntua.gr/public/pdp-c ... 5/sumx.cpp
In a world without walls and fenches who needs Windows and Gates?

Άβαταρ μέλους
switch
Δημοσιεύσεις: 31
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am

Re: Υλη για PDP

Δημοσίευση από switch » Πέμ Δεκ 31, 2015 1:57 am

Ευχαριστώ για την ενημέρωση. Είχα (αυθαίρετα) υποθέσει ότι θα έπρεπε να χρησιμοποιηθεί ansi c k&r και είχα διάφορους προβληματισμούς π.χ. αν πρέπει να θεωρήσουμε ως βασικό τύπο τον ακέραιο ή αν μπορούμε να έχουμε static πίνακες, αν πρέπει να κάνουμε έλεγχο λαθών στα inputs κλπ και άλλες τέτοιες λεπτομέρειες.
Αφού είδα αρκετά από τα προβλήματα, νόμιζα ότι είχα καταλάβει γενικά πως πρέπει να δουλέψουμε, μέχρι που ... διάβασα το πρόβλημα με τη σοκολάτα στον τρέχοντα διαγωνισμό Δεκεμβρίου 2015 (το οποίο λύνεται ή με μαθηματικά ή προγραμματιστικά), όμως εδώ πρέπει να ξέρουμε κάποιες λεπτομέρειες για τον υπολογιστή, πχ αν έχουμε περιορισμό στο stack ή τα μεγέθη των ακεραίων.

Θα κοιτάξω και στο http://people.ksp.sk/~misof/ioi-syllabu ... s-2013.pdf και θα επανέλθω μετά τις 5/1/2016 που τελειώνει ο διαγωνισμός.

Χρόνια πολλά και Καλή χρονιά σε όλους.

infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: Υλη για PDP

Δημοσίευση από infinity » Παρ Ιαν 01, 2016 11:10 pm

switch έγραψε:Ευχαριστώ για την ενημέρωση. Είχα (αυθαίρετα) υποθέσει ότι θα έπρεπε να χρησιμοποιηθεί ansi c k&r και είχα διάφορους προβληματισμούς π.χ. αν πρέπει να θεωρήσουμε ως βασικό τύπο τον ακέραιο ή αν μπορούμε να έχουμε static πίνακες, αν πρέπει να κάνουμε έλεγχο λαθών στα inputs κλπ και άλλες τέτοιες λεπτομέρειες.
Αφού είδα αρκετά από τα προβλήματα, νόμιζα ότι είχα καταλάβει γενικά πως πρέπει να δουλέψουμε, μέχρι που ... διάβασα το πρόβλημα με τη σοκολάτα στον τρέχοντα διαγωνισμό Δεκεμβρίου 2015 (το οποίο λύνεται ή με μαθηματικά ή προγραμματιστικά), όμως εδώ πρέπει να ξέρουμε κάποιες λεπτομέρειες για τον υπολογιστή, πχ αν έχουμε περιορισμό στο stack ή τα μεγέθη των ακεραίων.

Θα κοιτάξω και στο http://people.ksp.sk/~misof/ioi-syllabu ... s-2013.pdf και θα επανέλθω μετά τις 5/1/2016 που τελειώνει ο διαγωνισμός.

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

Όσον αφορά το πρόβλημα με την σοκολάτα, στην εκφώνηση περιγράφει τους περιορισμούς για κάθε ομάδα testcases και ακριβώς επειδή η απάντηση μπορεί να είναι μεγάλη πρέπει να εκτυπωθεί το υπόλοιπό της απάντησης με το 1000000007.

Χρόνια πολλά και καλή χρονιά.

Απάντηση