Υλικό για τα μαθήματα του 32ου ΠΔΠ

[chpipis]

Καλησπέρα,

Αν και καθυστερημένα, ανεβάζω το υλικό του πρώτου μαθήματος στην Αθήνα (14/12/2019) για τον 32o ΠΔΠ, όπως υποσχέθηκα. Στο πρώτο μάθημα καλύψαμε επιφανειακά τις βασικές έννοιες της γλώσσας C++, λύσαμε το πρόβλημα Α' φάσης του 27ου ΠΔΠ και είδαμε εισαγωγικά πράγματα για πολυπλοκότητες αλγορίθμων.

Αρχικά, σας παροτρύνω να διαβάσετε την πρόσφατη απάντηση στο forum του Βαγγέλη Κηπουρίδη στο ερώτημα για το τι γνώσεις γλωσσών προγραμματισμού χρειάζεται κανείς για να συμμετάσχει στον διαγωνισμό. Το link που έχει δώσει είναι πολύ χρήσιμο και έχει περαιτέρω πηγές για διάβασμα σχετικά με την C++. Παραθέτω επιπλέον ένα youtube playlist για εκμάθηση C++ από το κανάλι thenewboston που μου είχε φανεί πολύ χρήσιμο όταν άρχισα να μαθαίνω την γλώσσα. Εκεί τα πρώτα 37 βιντεάκια πιστεύω είναι αρκετά για να μάθει κανείς τα βασικά.

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

Αρχικά, στο pdp-archive υπάρχουν κάμποσα παλιά θέματα με εκφωνήσεις, test cases, λύσεις και κώδικες! Ακόμα δεν υπάρχουν όλα, όμως αυξάνονται σιγά σιγά.

Επίσης, ένα άλλο site που παρουσιάζει ενδιαφέρον είναι το hellenico, όπου υπάρχουν αρκετά προβλήματα τα οποία μπορείτε να υποβάλλετε, ενώ παράλληλα υπάρχουν κομμάτια θεωρίας που ξεκλειδώνονται καθώς προχωράτε. Το αντίστοιχο site της Αμερικής είναι το Usaco Training Gateway και ακολουθεί την ίδια λογική με το hellenico.

Σχετικά με την υπολογιστική πολυπλοκότητα, σας προτείνω να διαβάσετε το άρθρο "Μια Εύπεπτη Εισαγωγή στην Ανάλυση Πολυπλοκότητας Αλγορίθμων" του Διονύση Ζήνδρου.

Τέλος, προτείνω επίσης να ασχοληθείτε όσο περισσότερο μπορείτε με την σειρά μαθηματών CodeMonk του HackerEarth. Εκεί θα βρείτε μια ακολουθία από ενότητες, όπου σε κάθε μία υπάρχουν tutorials πάνω σε ένα θέμα (πχ. Basics of Programming, Sorting, Graph Theory, κλπ.). Κάθε ενότητα έχει και σχετικά με την θεωρία προβλήματα για να υποβάλλετε. Σας το προτείνω ανεπιφύλακτα!

Μέχρι το επόμενο μάθημα καλό είναι να έχετε εξοικειωθεί αρκετά με την C++ ή κάποια άλλη γλώσσα του διαγωνισμού.
Αν χρειαστείτε οποιαδήποτε βοήθεια, καθοδήγηση ή περαιτέρω υλικό μπορείτε να ρωτήσετε εδώ στο forum.

Σας εύχομαι καλά Χριστούγεννα!

[chpipis]

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

Στο δεύτερο μάθημα που έγινε στην Αθήνα (25/1/2020), δημιουργήθηκαν δύο τμήματα (αρχάριοι και προχωρημένοι). Στο τμήμα των προχωρημένων έγινε μια εισαγωγή στο square root decomposition και τα segment trees.

Πιστεύω ότι το sqrt decomposition είναι πολύ δυνατή και χρήσιμη τεχνική και σας προτρέπω να διαβάσετε περισσότερα και να λύσετε προβλήματα από αυτό το άρθρο στο cp-algorithms. Για το segment tree σας προτείνω να διαβάσετε αυτό το άρθρο του Ραφαήλ Κετσετσίδη στον Καλλίνικο και αυτό από το cp-algorithms. Στο μάθημα προλάβαμε να καλύψουμε μόνο την απλή εκδοχή του δέντρου που μας επιτρέπει να κάνουμε range queries και point updates. Γράψαμε επίσης κώδικα για το πρόβλημα GSS1 από το SPOJ, τον οποίο ανεβάζω εδώ.

Spoiler: show

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

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e4 + 5;
const int INF = 1e9;

struct node {
    int ans, sum, pref_max, suff_max;
};

int A[MAX_N];
node st[MAX_N * 4];

node combine(node left, node right) {
    node result;
    result.ans = max(max(left.ans, right.ans), left.suff_max + right.pref_max);
    result.sum = left.sum + right.sum;
    result.pref_max = max(left.pref_max, left.sum + right.pref_max);
    result.suff_max = max(right.suff_max, left.suff_max + right.sum);
    return result;
}

node query(int p, int L, int R, int i, int j) {
    if (i > R || j < L) return (node){-INF, 0, -INF, -INF};

    if (i <= L && j >= R) return st[p];

    int left = p * 2, right = p * 2 + 1;
    int mid = (L + R) / 2;

    node l_node = query(left, L, mid, i, j);
    node r_node = query(right, mid + 1, R, i, j);

    return combine(l_node, r_node);
}

void build(int p, int L, int R) {
    if (L == R) {
        st[p].ans = st[p].pref_max = st[p].suff_max = st[p].sum = A[R];
    } else {
        int left = p * 2, right = p * 2 + 1;
        int mid = (L + R) / 2;

        build(left, L, mid);
        build(right, mid + 1, R);

        st[p] = combine(st[left], st[right]);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    build(1, 1, n);
    int q;
    cin >> q;
    while (q--) {
        int i, j;
        cin >> i >> j;
        cout << query(1, 1, n, i, j).ans << '\n';
    }
    return 0;
}

Τέλος, υπενθυμίζω ότι ο καλύτερος τρόπος για να εξασκηθείτε είναι να λύσετε πολλά προβλήματα. Για αυτό μπορείτε να ακολουθήσετε τα links που είχα ανεβάσει στο προηγούμενο post. Για οτιδήποτε άλλο χρειαστείτε (απορίες, έξτρα υλικό ή προβλήματα κλπ) μην διστάσετε να ρωτήσετε στο forum.

Καλή συνέχεια!

[nikoskon]

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

[chpipis]

Γεια σου!

Το τελευταίο μάθημα ήταν στις 25/1 για το οποίο έχει ανέβει η ύλη των προχωρημένων. Αν σε ενδιαφέρει η ύλη των αρχάριων, κάναμε sorting, binary search και recursion. Λογικά θα σας σταλεί email για το επόμενο μάθημα το οποίο θα είναι σύντομα (και μάλλον όχι αυτό το ΣΚ που έρχεται).

Φυσικά δεν υπάρχει πρόβλημα που απουσιάζες στο μάθημα καθώς δεν είναι υποχρεωτική η παρακολούθηση και εννοείται δεν ενοχλείς ρωτώντας εδώ. Ίσα ίσα ζωντανεύεις και το φορουμ!

Καλή συνέχεια και καλή εξάσκηση!

[nikoskon]

Το επόμενο μάθημα δεν είναι αυτό το Σάββατο (7/3/2020);

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

Πράγματι: https://drive.google.com/file/d/1_45_re ... JTVOM/view

[chpipis]

Χθες (7/3/2020) έγινε το 3ο μάθημα προετοιμασίας για τον 32ο ΠΔΠ, στο οποίο έγινε μια εισαγωγή στον Δυναμικό Προγραμματισμό (Dynamic Programming), μια από τις σημαντικότερες τεχνικές στους διαγωνισμούς πληροφορικής.

Στο μάθημα λύσαμε τα εξής προβλήματα: Longest Increasing Subsequence, Longest Common Subsequence, Maximum Subarray Sum (Kadane's algorithm), ΠΔΠ30 Γ φάση listgame. Για το πρόβλημα του ΠΔΠ υπάρχει λύση στο link (στο pdp-archive) και για τα υπόλοιπα 3 προβλήματα μπορείτε να βρείτε τις λύσεις online αφού είναι διάσημα παραδείγματα DP.

Παραθέτω τώρα μερικές πηγές για διάβασμα και εξάσκηση. Σας προτείνω να μην αναλώσετε πολύ χρόνο στο να διαβάζετε απλά. Είναι πολύ σημαντικό να λύνετε συνεχώς προβλήματα! Στην αρχή θα σας φαίνεται δύσκολο να βρείτε το state του DP αλλά με την εξάσκηση θα αποκτήσετε μια καλύτερη διαίσθηση για το πως να το βρίσκετε. Προσπαθήστε να σκέφτεστε επαρκώς το πρόβλημα προτού δείτε την λύση του.

• Αρχικά σας προτρέπω να διαβάσετε το περιεκτικό άρθρο του Ραφαήλ Κετσετσίδη στον Καλλίνικο "Εισαγωγή στον Δυναμικό Προγραμματισμό", το οποίο έχει και μια λίστα προβλημάτων προς επίλυση στο τέλος (προσοχή! αρκετά από αυτά δεν είναι εύκολα για αρχάριους)
• Επίσης, το άρθρο Dynamic Programming: From Novice to Advanced του Topcoder και τα άρθρα του HackerEarth CodeMonk (intro, 2-d DP) είναι αρκετά καλά
• Αν σας βολεύει το διάβασμα από βιβλία και σας ενδιαφέρει να δείτε μια πιο αυστηρή προσέγγιση στον Δυναμικό Προγραμματισμό, ανατρέξτε στα βιβλία "Algorithms" του Παπαδημητρίου και Introduction to Algorithms (CLRS)
• Αν σας αρέσει να μαθαίνετε μέσα από βιντεάκια δείτε τα τρία εισαγωγικά DP tutorials του Errichto (πολύ καλός competitive programmer από την Πολωνία): DP1, DP2, DP3
• Για να βρείτε και να λύσετε πολλά προβλήματα μπορείτε να επιλέγετε κάποιο τυχαία από τα προβλήματα του codeforces με tag "dp" ή από το SPOJ, το HackerEarth, Hackerrank, κλπ. Επίσης τσεκάρετε αυτόν τον παλιό διαγωνισμό εξάσκησης του AtCoder (Ιαπωνικό site με πολύ ωραία προβλήματα) αλλά προσέξτε γιατί αρκετά από αυτά είναι πολύ δύσκολα για αρχή. Αν θέλετε μπορείτε να βλέπετε παράλληλα και αυτό το 5ώρο βίντεο του Errichto με τις λύσεις για να σας καθοδηγεί.
• Τέλος, εδώ είναι μια εκτενής λίστα στο codeforces με περαιτέρω πηγές και προβλήματα για DP: https://codeforces.com/blog/entry/67679

Αν έχετε οποιαδήποτε απορία ρωτήστε μας εδώ στο forum.

Καλή εξάσκηση!