Υλη για PDP
-
- Δημοσιεύσεις: 1
- Εγγραφή: Παρ Μαρ 06, 2015 5:09 pm
Υλη για PDP
Θελω να ξερω ποιά πραγματα πρεπει να ξερω για να μπορω να τα παω καλά στο ΠΔΠ . Απο πλευρας αλγορυθμων , Data structures , etc . Υπαρχει πουθενα η επισημη υλη η τιποτα τετοιό ?
Re: Υλη για PDP
Καλημέρα, έχω και εγώ απορία σε σχέση με την ύλη. Δεν είμαι διαγωνιζόμενος, αλλά γονιός μαθητή γυμνασίου.
Σε όλα σχεδόν τα προβλήματα, υπάρχουν διάφορες λύσεις.
Π.χ. κοίταγα το sumx, που η απλή λύση είναι με 2πλό loop και πρέπει να βρεθεί ο αριθμός των ζευγών από μια τυχαία σειρά Ν αριθμών που έχει συγκεκριμένο άθροισμα.
Η εύκολη λύση είναι με ενφωλευμένα loop:
Αν γίνει με απλά ενφωλευμένα loop τότε, όσο αυξάνεται το Ν (άνω όριο για το Ν είναι το 1.000.000), τότε μπορεί να φτάσουμε και στο μισό λεπτό. Αν όμως χρησιμοποιηθεί qsort/bsearch, πέφτουμε στα 2,5 δευτερόλεπτα και αν χρησιμοποιηθούν m-trees, τότε πάμε στα 1,5 sec.
Σε τι επίπεδο πρέπει να βασίζεται η προετοιμασία των υποψηφίων για το διαγωνισμό;
Στην εκφώνηση αναφέρει μέγιστο Ν το 1.000.000 και δίνει και μέγιστο χρόνο εκτέλεσης.
Ο χρόνος αυτός ισχύει για το μέγιστο Ν;
Τα όρια του Ν δίνονται μόνο για να επιλεχθεί ο σωστός τύπος ακεραίου ή θα γίνει δοκιμή με αυτά τα όρια;
Σε όλα σχεδόν τα προβλήματα, υπάρχουν διάφορες λύσεις.
Π.χ. κοίταγα το sumx, που η απλή λύση είναι με 2πλό loop και πρέπει να βρεθεί ο αριθμός των ζευγών από μια τυχαία σειρά Ν αριθμών που έχει συγκεκριμένο άθροισμα.
Η εύκολη λύση είναι με ενφωλευμένα loop:
Κώδικας: Επιλογή όλων
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
....
Σε τι επίπεδο πρέπει να βασίζεται η προετοιμασία των υποψηφίων για το διαγωνισμό;
Στην εκφώνηση αναφέρει μέγιστο Ν το 1.000.000 και δίνει και μέγιστο χρόνο εκτέλεσης.
Ο χρόνος αυτός ισχύει για το μέγιστο Ν;
Τα όρια του Ν δίνονται μόνο για να επιλεχθεί ο σωστός τύπος ακεραίου ή θα γίνει δοκιμή με αυτά τα όρια;
-
- Δημοσιεύσεις: 14
- Εγγραφή: Πέμ Μαρ 08, 2012 3:40 pm
Re: Υλη για PDP
Γενικά για το διαγωνισμό δεν υπάρχει συγκεκριμένη ύλη αλλά βρίσκεται στα πλαίσια αυτής της ΙΟΙ.
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
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
Re: Υλη για PDP
Ευχαριστώ για την ενημέρωση. Είχα (αυθαίρετα) υποθέσει ότι θα έπρεπε να χρησιμοποιηθεί ansi c k&r και είχα διάφορους προβληματισμούς π.χ. αν πρέπει να θεωρήσουμε ως βασικό τύπο τον ακέραιο ή αν μπορούμε να έχουμε static πίνακες, αν πρέπει να κάνουμε έλεγχο λαθών στα inputs κλπ και άλλες τέτοιες λεπτομέρειες.
Αφού είδα αρκετά από τα προβλήματα, νόμιζα ότι είχα καταλάβει γενικά πως πρέπει να δουλέψουμε, μέχρι που ... διάβασα το πρόβλημα με τη σοκολάτα στον τρέχοντα διαγωνισμό Δεκεμβρίου 2015 (το οποίο λύνεται ή με μαθηματικά ή προγραμματιστικά), όμως εδώ πρέπει να ξέρουμε κάποιες λεπτομέρειες για τον υπολογιστή, πχ αν έχουμε περιορισμό στο stack ή τα μεγέθη των ακεραίων.
Θα κοιτάξω και στο http://people.ksp.sk/~misof/ioi-syllabu ... s-2013.pdf και θα επανέλθω μετά τις 5/1/2016 που τελειώνει ο διαγωνισμός.
Χρόνια πολλά και Καλή χρονιά σε όλους.
Αφού είδα αρκετά από τα προβλήματα, νόμιζα ότι είχα καταλάβει γενικά πως πρέπει να δουλέψουμε, μέχρι που ... διάβασα το πρόβλημα με τη σοκολάτα στον τρέχοντα διαγωνισμό Δεκεμβρίου 2015 (το οποίο λύνεται ή με μαθηματικά ή προγραμματιστικά), όμως εδώ πρέπει να ξέρουμε κάποιες λεπτομέρειες για τον υπολογιστή, πχ αν έχουμε περιορισμό στο stack ή τα μεγέθη των ακεραίων.
Θα κοιτάξω και στο http://people.ksp.sk/~misof/ioi-syllabu ... s-2013.pdf και θα επανέλθω μετά τις 5/1/2016 που τελειώνει ο διαγωνισμός.
Χρόνια πολλά και Καλή χρονιά σε όλους.
Re: Υλη για PDP
Γενικά το πνεύμα του διαγωνισμού δεν είναι τέτοιο, το θέμα είναι η επίλυση των προβλημάτων, δεν θα υπάρχουν γενικά λεπτομέρειες οι οποίες θα απασχολούν τους διαγωνιζόμενους, τα δεδομένα πάντα θα είναι σωστά και σχετικές τεχνικές λεπτομέρειες θα περιγράφονται στην εκφώνηση του προβλήματος.switch έγραψε:Ευχαριστώ για την ενημέρωση. Είχα (αυθαίρετα) υποθέσει ότι θα έπρεπε να χρησιμοποιηθεί ansi c k&r και είχα διάφορους προβληματισμούς π.χ. αν πρέπει να θεωρήσουμε ως βασικό τύπο τον ακέραιο ή αν μπορούμε να έχουμε static πίνακες, αν πρέπει να κάνουμε έλεγχο λαθών στα inputs κλπ και άλλες τέτοιες λεπτομέρειες.
Αφού είδα αρκετά από τα προβλήματα, νόμιζα ότι είχα καταλάβει γενικά πως πρέπει να δουλέψουμε, μέχρι που ... διάβασα το πρόβλημα με τη σοκολάτα στον τρέχοντα διαγωνισμό Δεκεμβρίου 2015 (το οποίο λύνεται ή με μαθηματικά ή προγραμματιστικά), όμως εδώ πρέπει να ξέρουμε κάποιες λεπτομέρειες για τον υπολογιστή, πχ αν έχουμε περιορισμό στο stack ή τα μεγέθη των ακεραίων.
Θα κοιτάξω και στο http://people.ksp.sk/~misof/ioi-syllabu ... s-2013.pdf και θα επανέλθω μετά τις 5/1/2016 που τελειώνει ο διαγωνισμός.
Χρόνια πολλά και Καλή χρονιά σε όλους.
Όσον αφορά το πρόβλημα με την σοκολάτα, στην εκφώνηση περιγράφει τους περιορισμούς για κάθε ομάδα testcases και ακριβώς επειδή η απάντηση μπορεί να είναι μεγάλη πρέπει να εκτυπωθεί το υπόλοιπό της απάντησης με το 1000000007.
Χρόνια πολλά και καλή χρονιά.