Σημειώσεις για διαγωνισμούς προγραμματισμού

Γενικά

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

Σε γενικές γραμμές, ο διαγωνισμός διέπεται από τους εξής βασικούς κανόνες:

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

• Κάθε πανεπιστημιακό τμήμα συμμετέχει με τρεις το πολύ ομάδες.
• Ο διαγωνισμός γίνεται με βάση το internet, κατά τα πρότυπα του διαγωνισμού προγραμματισμού που διοργανώνει το Duke University, δηλαδή με τη χρήση www και e-mail.

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

• Εκτός από τον υπολογιστή (και ενδεχομένως το e-mail για την αποστολή των προγραμμάτων), κάθε ομάδα δεν πρέπει να έχει πρόσβαση σε οποιοδήποτε είδος ηλεκτρονικής πληροφορίας. Έτσι απαγορεύονται τουλάχιστον:
  • Άλλοι υπολογιστές (γραφείου, φορητοί, αριθμομηχανές κλπ.)
  • Δισκέτες, δίσκοι και άλλου είδους δεδομένα, πλροφορίες ή κώδικας σε ηλεκτρονική μορφή.
• Επιτρέπεται οποιουδήποτε είδους έντυπη μορφή πληροφοριών ή κώδικα σε έγγραφη ή έντυπη μορφή, πχ. βιβλία, λίστες, χειρόγραφες σημειώσεις κλπ. Επίσης επιτρέπεται η εκτύπωση προγραμμάτων κατά τη διάρκεια του διαγωνισμού.

Διαδικασία του διαγωνισμού

Η βαθμολογία και κατάταξη των ομάδων μετά το πέρας του διαγωνισμού γίνεται ως εξής: Οι όμαδες ταξινομούνται πρώτα με τον αριθμό των προβλημάτων που έχουν λύσει και έπειτα με το συνολικό χρόνο επίλυσης. Πιο συγκεκριμένα:

• Από την αρχή του διαγωνισμού, για κάθε λεπτό που περνά μετράται ένας βαθμός ποινής
• Για κάθε υποβολή προγράμματος που είναι σωστό, προστίθεται στους βαθμούς ποινής της ομάδας ο αριθμός των λεπτών που έχουν περάσει από την αρχή του διαγωνισμού ως την υποβολή του προγράμματος.
• Για κάθε υποβολή προγράμματος που είναι λάθος, προστίθεται στους βαθμούς ποινής της ομάδας 15 ή 20 βαθμοί ποινής (καθορίζεται).
• ΠΡΟΣΟΧΗ: Βαθμοί ποινής από προγράμματα για προβλήματα που τελικά δεν επιλύθηκαν από την ομάδα (σωστά), δεν προμετρώνται στον τελικό αριθμό βαθμών ποινής για κάθε ομάδα.

Ένα παράδειγμα για τρεις ομάδες: Η (1) λύνει τρία προβλήματα, το πρώτο στη 1 ώρα, το δεύτερο στις 2 ώρες και το τρίτο στις 3 ώρες και τριάντα λεπτά (από την αρχή του διαγωνισμού) ενώ έχει και λάθος υποβολές σε ένα τέταρτο πρόβλημα. Η (2) κάνει λάθος στο πρώτο στα 40 λεπτά, λάθος το τέταρτο στα 50 λεπτά, στέλνει σωστά το δεύτερο στη μία ωρα, στέλνει σωστά το πρώτο στη 1 ώρα και 20 λεπτά. Η (3) στέλνει σωστά το δεύτερο πρόβλημα στις 2 ώρες και το τέταρτο πρόβλημα στις 2 ώρες και 40 λεπτά. Η κατάταξη θα είναι ως εξής:

Κατάταξη	Ομάδα	Αριθμός λυμένων προβλημάτων	Βαθμοί ποινής
1η	(1)	3	60+120+210=390
2η	(2)	2	15+60+80=155
3η	(3)	2	120+160=280

Τι σημαίνει σωστό πρόγραμμα

• Λάθος απάντηση: Το πρόγραμμα που υποβάλαμε έδωσε δεδομένα εξόδου διαφορετικά από αυτά που θα έπρεπε να βγάλει ένα σωστό πρόγραμμα.
• Λάθος παρουσίασης: Το πρόγραμμα φαίνεται ότι βγάζει σωστά αποτελέσματα αλλά ο τρόπος που τα βγάζει δε συμφωνεί με τους κανόνες που περιγράφει η εκφώνηση. Θα πρέπει να δίνεται μεγάλη προσοχή στις εκφωνήσεις, ώστε να μην χάνει κάποιος βαθμούς και χρόνο από παρόμοια λάθη (που δεν είναι επί της ουσίας)
• Τέλος χρόνου: Το πρόγραμμα που υποβάλαμε δεν τελείωσε την εκτέλεσή του στον προκαθορισμένο χρόνο που του δόθηκε. Αυτό μπορεί να οφείλεται σε πολλούς λόγους, πχ. επειδή το πρόγραμμα χρησιμοποιεί πολύ αργό αλγόριθμο, ή επειδή έχει λάθος και πέφτει σε κάποια άπειρη ανακύκλωση. Σε μερικές αρχιτεκτονικές (πχ. DOS) μπορεί να σημαίνει ότι το πρόγραμμά μας έγραψε έξω από τη μνήμη του και ενδεχομένως να προκάλεσε crash στο μηχάνημα ελέγχου.
• run-time error: Το πρόγραμμα κατά την εκτέλεση παρουσίασε λάθος, πχ. έκανε crash, segmentation fault, memory full, out of bound access κλπ. Αυτό οφείλεται σε δεδομένα με μέγεθος ή κάποια χαρακτηριστικά που δεν τα έχουμε προβλέψει.
• compile-time error: Υποτίθεται ότι τα προγράμματα που στέλνουμε περνούν από το μεταγλωττιστή χωρίς λάθη. Τέτοιο λάθος δεν πρέπει να συμβεί ποτέ, εκτός αν είμαστε εντελώς απρόσεκτοι (ή απελπισμένοι).

Στους διαγωνισμούς αυτούς, δε λαμβάνεται καθόλου υπόψη η μορφή του προγράμματος που υποβάλουμε (πχ. σχόλια, identation, εύλογα ονόματα μεταβλητών κλπ.). Τα χαρακτηριστικά αυτά βοηθάνε μόνο το συγγραφέα του προγράμματος και (κυρίως) το συνεργάτη του που θα τον βοηθήσει στη διόρθωση λαθών. Θα πρέπει λοιπόν να χρησιμοποούνται με μέτρο και μόνο αν δεν επιβαρύνουν άνισα τη βαθμολογία της ομάδας.

Κύριοι σκοποί μια ομάδας που θέλει να συμμετάσχει με αξιώσεις είναι να αντιμετωπίσει κάθε πρόβλημα με τα ακόλουθα κατά νου:

• Να βρει έναν ικανοποιητικό αλγόριθμο για την επίλυση του προβλήματος
• Να λάβει υπόψη της όλα τα στοιχεία της εκφώνησης, ώστε να προβλέψει για κάθε δυνατή είσοδο, το σωστό αποτέλεσμα. ΠΡΟΣΟΧΗ στις ακραίες περιπτώσεις, τις περίεργες και πονηρές εισόδους κλπ.

Στρατηγικές για καλή απόδοση στο διαγωνισμό

Οι εκφωνήσεις των θεμάτων

Πολύ σημαντικό είναι επίσης ότι η εκφώνιση αλλά ίσως και οι κανόνες του διαγωνισμού προκαθορίζουν τη μορφή των δεδομένων της εισόδου και της εξόδου που θα πρέπει να υποστηρίζει το πρόγραμμά μας. Πχ. μπορεί να ζητείται η είσοδος και η έξοδος να είναι συγκεκριμένα αρχεία ή αντίθετα οι προκαθορισμένες (standard input, standard output). Μπορεί να καθορίζεται ότι η είσοδος θα είναι αριθμοί σε μία μόνο γραμμή ενώ η έξοδος ένας αριθμός σε κάθε σειρά, χωρίς άλλα σχόλια, παραπάνω κενά, παραπάνω αλλαγές γραμμής, λέξεις, επεξηγήσεις, σχόλια για debugging κλπ.

Εν ολίγοις: ΜΕΓΑΛΗ ΠΡΟΣΟΧΗ ΣΤΙΣ ΕΚΦΩΝΗΣΕΙΣ ΓΙΑΤΙ ΟΔΗΓΟΥΝ ΣΕ (ΑΔΙΚΑ) ΛΑΘΗ

Συγγραφή των προγραμμάτων

Στην αρχή του διαγωνισμού που γίνονται γνωστά τα θέματα, καλό είναι να γίνει μια αρχική φάση "αναγνώρισης", διάρκειας 5 λεπτών. Όλα τα θέματα μοιράζονται στα μέλη της ομάδας για μια γρήγορη επισκόπηση. Με το πέρας των 5 λεπτών, θα πρέπει να έχουν εντοπιστεί τα τρία θέματα που φαίνονται πιο εύκολα και με τα οποία θα αρχίσει η ενασχόληση. Επίσης θα πρέπει να καθοριστεί και ποιό μέλος θα ασχοληθεί με ποιο πρόβλημα αρχικά. Η ιδέα είναι μόλις κάποιο μέλος στείλει αποστείλει ένα πρόγραμμα, περιμένοντας την απάντηση, να αρχίσει να ασχολείται με κάποιο άλλο. Προς το τέλος του διαγωνισμού, όπου ενδεχομένως θα υπάρχουν λιγότερα από 3 άλυτα προβλήματα, μπορεί να γίνει και συνεργασία μεταξύ της ομάδας για τη λύση τους. Απο την εμπειρία πάντως προκύπτει ότι τα άτομα δουλεύοντας ξεχωριστά είναι πιο αποδοτικά.

Εφόσον δεν είναι δυνατό ο καθένας να είναι μπροστά σε υπολογιστή συνέχεια, ο καλύτερος τρόπος να φτιαχτεί ένα πρόγραμμα, είναι η σχεδίαση στο χαρτί. Τα στάδια ετοιμασίας της λύσης ενός προγράμματος μπορούν να δοθούν ως εξής:

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

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

Θέματα αλγορίθμων

Σε συνδιασμό με το παραπάνω κρίνεται απαραίτητο κάθε ομάδα να που συμμετέχει στο διαγωνισμό, να είναι εφοδιασμένη με έτοιμες ρουτίνες που χρησιμοποιούνται συχνά σε προβλήματα. Οι ρουτίνες θα πρέπει βέβαια να είναι σε έντυπη μορφή και να διακατέχονται από κάποια χαρακτηριστικά:

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

• Γράφους: δημιουργία, αναζήτηση, δομές, γνωστοί αλγόριθμοι κλπ.
• Δέντρα: αντίστοιχα
• Συνδιασμούς, μεταθέσεις, με ή χωρίς επανάληψη, αναδρομική απαρίθμησή τους με δυνατότητα "κλαδέματος" κλπ.
• Αντιστοίχιση strings σε αριθμούς