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

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
chpipis
Δημοσιεύσεις: 3
Εγγραφή: Σάβ Νοέμ 30, 2019 9:36 pm

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

Δημοσίευση από chpipis »

Καλησπέρα,

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

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

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

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

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

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

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

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

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

chpipis
Δημοσιεύσεις: 3
Εγγραφή: Σάβ Νοέμ 30, 2019 9:36 pm

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

Δημοσίευση από 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.

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

Απάντηση