Μηνιαία Πρόκληση: Ιούνιος 2020

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 360
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Μηνιαία Πρόκληση: Ιούνιος 2020

Δημοσίευση από Κηπουρίδης »

Συνεχίζουμε το Solving Room Μαϊου 2020. Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση. Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς. Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου 5 μέρες πριν τελειώσει ο μήνας, θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.

Το παρακάτω πρόβλημα είναι από το Hellenico (Ενότητα 2.3), με όνομα "Αγώνας Δρόμου". Τα όρια που δίνονται στο Hellenico είναι πολύ ήπια. Εδώ θέλουμε να συζητήσουμε μια πιο δύσκολη εκδοχή του προβλήματος, όπου ζητείται γραμμικός(!) αλγόριθμος (Ν κόμβοι, Μ ακμές, Ν<=50.000, Μ<=200.000). Ευχαριστήρια στον Μανώλη Μιχάλαινα του οποίου ιδέα ήταν αυτή η βελτιωμένη λύση.

Ας προδώσουμε ευθής εξαρχής ότι οι γνώσεις που χρειάζονται είναι ελάχιστες. Θέλουμε αναπαράσταση γράφων με adjacency lists, και DFS. Σε αυτά τα links μπορείτε να κατανοήσετε πώς αναπαριστούμε ένα γράφο στον υπολογιστή και πώς λειτουργεί η DFS, χωρίς να σας απασχολεί η υλοποίησή τους σε κώδικα. Αφού τα κατανοήσετε, μπορείτε να δείτε εδώ έναν σχετικό κώδικα.

Πρόβλημα: Αγώνας Δρόμου

Η εικόνα δίνει ένα παράδειγμα μιας διαδρομής για έναν αγώνα δρόμου. Βλέπετε μερικά σημειά, σημειωμένα από 0 ως Ν (εδώ Ν=9), και μερικά βέλη που τα ενώνουν. Το σημείο 0 είναι η αφετηρία του αγώνα; το σημείο Ν είναι ο τερματισμός.
Τα βέλη συμβολίζουν δρόμους μιας κατεύθυνσης. Οι συμμετέχοντες του αγώνα μετακινούνται από το ένα σημείο στο άλλο μέσω των δρόμων, στην κατεύθυνση των βελών μόνο. Σε κάθε σημείο, ο διαγωνιζόμενος μπορεί να επιλέξει οποιοδήποτε εξερχόμενο βέλος.
race.gif
race.gif (1.05 KiB) Προβλήθηκε 806 φορές
Μία καλώς-σχηματισμένη διαδρομή έχει τις παρακάτω ιδιότητες:

1. Μπορούμε να φτάσουμε σε κάθε σημείο της διαδρομής από την αφετηρία.
2. Μπορούμε να φτάσουμε στον τερματισμό από κάθε σημείο της διαδρομής.
3. Ο τερματισμός δεν έχει εξερχόμενα βέλη.

Ένας διαγωνιζόμενος δεν υποχρεούται να επισκευτεί κάθε σημείο της διαδρομής για να φτάσει στον τερματισμό. Μερικά σημεία, ωστόσο, είναι αναπόφευκτα. Στο παράδειγμα, αυτά είναι τα σημεία 0, 3, 6, και 9. Δοθείσας μιας καλως-σχηματισμένης διαδρομής, το πρόγραμμα σας πρέπει να προσδιορίσει το σύνολο των αναπόφευκτων σημείων που όλοι οι συμμετέχοντες πρέπει να επισκεφτούν, εκτός της αφετηρίας και του τερματισμού (Υποπρόβλημα Α).

Υποθέστε οτί ο αγώνας πρέπει να λάβει μέρος δύο συνεχόμενες μέρες. Γι' αυτό το σκοπό η διαδρομή πρέπει να χωριστεί σε δύο διαδρομές, μία την κάθε μέρα. Την πρώτη μέρα, η αφετηρία είναι στο σημείο 0 και ο τερματισμός σε κάποιο `διαχωριστικό σημείο'. Την δεύτερη μέρα, η αφετηρία είναι σε αυτό το διαχωριστικό σημείο και ο τερματισμός στο σημείο Ν. Δοθείσας μιας καλώς-σχηματισμένης διαδρομής, το πρόγραμμα σας πρέπει να υπολογίσει το σύνολο των διαχωριστικών σημείων (Υποπρόβλημα Β). Ένα σημείο S είναι ένα διαχωριστικό σημείο για την καλως-σχηματισμένη διαδρομή C αν το S διαφέρει από την αφετηρία και τον τερματισμό της C, και η διαδρομή μπορεί να χωριστεί σε δύο καλως-σχηματισμένες διαδρομές που δεν έχουν κοινά βέλη και έχουν μόνο το S ως κοινό σημείο. Στο παράδειγμα, μόνο το σημείο 3 είναι ένα διαχωριστικό σημείο.

Δεδομένα Εισόδου (race.in)

Το αρχείο εισόδου περιγράφει μια καλώς-σχηματισμένη διαδρομή με το πολύ 50.000 σημεία και το πολύ 200.000 βέλη. Υπάρχουν Ν+1 γραμμές στο αρχείο. Οι πρώτες Ν γραμμές περιέχουν τα τελικά σημεία των βελών που φεύγουν από τα σημεία 0 ως Ν-1 αντίστοιχα. Κάθε μία από τις γραμμές τελειώνει με τον αριθμό -2. Η τελευταία γραμμή περιέχει τον αριθμό -1.

Δεδομένα Εξόδου (race.out)

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

Παράδειγμα εισόδου (αρχείο "race.in")

1 2 -2
3 -2
3 -2
5 4 -2
6 4 -2
6 -2
7 8 -2
9 -2
5 9 -2
-2
-1


Παράδειγμα εξόδου (αρχείο "race.out")

2 3 6
1 3
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/

Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 360
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Μηνιαία Πρόκληση: Ιούνιος 2020

Δημοσίευση από Κηπουρίδης »

Στις 12.00 το μεσημέρι του Σαββάτου 27/6/2020 θα κάνουμε μία σύσκεψη στο zoom όπου θα συζητήσουμε σχετικά με τη μηνιαία πρόκληση.
Δεν πρόκειται να γίνει διάλεξη σχετικά με το πρόβλημα, αλλά ένα μοίρασμα σκέψεων. Επομένως απαιτείται όποιος συμμετέχει να έχει ανοιχτή κάμερα/μικρόφωνο.

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

Ξεκινώ εγώ καταθέτοντας δύο ερωτήσεις που με απασχολούν, ώστε να συζητηθούν το Σάββατο:
1) Επίλυση προβλημάτων: Σας βολεύει το Hellenico για προπόνηση για το διαγωνισμό; Ανεξάρτητα από την απάντησή σας, μπορείτε να αναφέρετε ένα-δυο πράγματα που βοηθάνε κι ένα-δυο που θα προτιμούσατε να βελτιωθούν;
2) Θεωρία: Σας είναι πάντα σαφές τι θεωρία χρειάζεται να διαβάζετε για το διαγωνισμό; Αν ναι, σας είναι σαφές και από πού θα την διαβάσετε;

Τα λέμε το Σάββατο!
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/

Απάντηση