Γ' Φάση-Λύσεις+Ἐπιδόσεις

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

Γ' Φάση-Λύσεις+Ἐπιδόσεις

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

Ἀφοὺ δὲν τὸ ἄνοιγε κανεῖς τὸ θέμα, τὸ ἄνοιξα ἐγώ. Πῶς τὰ πήγατε στὴν Γ' Φάση, καὶ κυρίως πεῖτε μας τὶς λύσεις σας.

Ἀρχίζω :

Ἔλυσα τὸ πρῶτο παίρνοντας ἀρχικὰ ὡς maximum τὸν πρῶτο ἀριθμό, κὶ ἐλάχιστο κοινὸ πολλαπλάσιο μέχρι στιγμῆς, τὸν πρῶτο ἀριθμό. Γιὰ κάθε ἐπόμενο ἀριθμό, ἔβρισκα τὸ ἐλάχιστο κοινὸ πολλαπλάσιο μεταξὺ αὐτοῦ καὶ τοῦ προηγούμενου Ε.Κ.Π. κὶ ἂν ὁ ἀριθμὸς ἤταν μεγαλύτερος τοῦ maximum καὶ ἴσος μὲ τὸ Ε.Κ.Π. , τότε ἤταν ὁ νέος maximum.

Θέμα δεύτερο : Brute Force κάθε πιθανὴ κατάσταση, μὲ μόνη βελτίωση ὅτι ἂν εἴχα ὡς πιθανὴ κατάσταση (Θερμοκρασία : 5 , Ἀπαιτούμενη Ἐνέργεια : 10 ) καὶ ( Θ : 10, Ἀ.Ἐ : 10 ) ἔπαιρνα μόνο τὴν δεύτερη κατάσταση ( ἐξίσου γιὰ τὴν ἐνέργεια ). Ἴσα ἴσα νὰ πιάσω τοὺς πόντους τῶν ἐνδεικτικῶν testcases δηλαδή.

Θέμα τρίτο : Μιὰ ἀπ` τὰ ἴδια, γιὰ κάθε πιθανὴ κατάσταση, ἔπαιρνα τὴν περίπτωση νὰ πάμε στὴν ἀμέσως ἀριστερά βάρκα, ἂν ὑπάρχει, καὶ στὴν ἀμέσως δεξιά ( ἂν ὑπάρχει ). Θὰ μποροῦσε νὰ δοκιμάζει γιὰ κάθε κόμβο νὰ τὸν ἐπισκέπτεται, καὶ μετὰ νὰ προχωρήσει ὅσο πάει στὴν ἀντίθετη κατεύθυνση, ἀλλὰ ΔΕΝ ἔπιανε ὅλα τὰ testcases, γιὰ αὐτὸ προτίμησα brute-force.
( Ἐπεξήγηση : Ἔστω 20 κιλὰ ἡ βάρκα, καὶ βάρκες στὰ σημεῖα -10,-1,3,99. Με την διαδρομή -1 , 3 , -10 θα πάρουμε ( 20-1 ) + (19-4) + ( 15-13 ) = 19 + 15 + 2 = 36, ενώ ὁ μὴ σωστὸς τρόπος θὰ ἔκανε τὴ διαδρομὴ -1,3, δηλαδή (20-1)+(19-4) = 34, ἢ ἂν θέλαμε νὰ ἐπισκεφθοῦμε τὶς σωστὲς βάρκες, θὰ τὸ ἔκανε μὲ τὴν σειρά 3,-1,-10, δηλαδή (20-3) + (17-4) + (13-9) = 17+13+4 = 34. )

ΣΕΙΡΑ ΣΑΣ!
Λύσεις θεμάτων ΠΔΠ: 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/
Άβαταρ μέλους
karaggeorge
Δημοσιεύσεις: 37
Εγγραφή: Σάβ Οκτ 31, 2009 2:25 pm

Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις

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

Συμφωνω με το 1ο...
στο 2ο εκανα ντ-π ( ;) ) ή απλειστο αλγοριθμο οπως υποστηριζει ο κηπου...
στο 3ο πηρα ως δεδομενο πως δεν μπορεις να πας 2 φορες στην ιδια πλευρα (αρνητικα -θετικα)
πραγμα το οποιο αποδείχτηκε λαθος...

καλη επιτυχια σε ολους ( ποτε θα βγουν επιτελους τα αποτελεσματα;;)
Εικόνα
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις

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

Κηπουρίδης έγραψε: Ἔλυσα τὸ πρῶτο παίρνοντας ἀρχικὰ ὡς maximum τὸν πρῶτο ἀριθμό, κὶ ἐλάχιστο κοινὸ πολλαπλάσιο μέχρι στιγμῆς, τὸν πρῶτο ἀριθμό. Γιὰ κάθε ἐπόμενο ἀριθμό, ἔβρισκα τὸ ἐλάχιστο κοινὸ πολλαπλάσιο μεταξὺ αὐτοῦ καὶ τοῦ προηγούμενου Ε.Κ.Π. κὶ ἂν ὁ ἀριθμὸς ἤταν μεγαλύτερος τοῦ maximum καὶ ἴσος μὲ τὸ Ε.Κ.Π. , τότε ἤταν ὁ νέος maximum.
Περίπου το ίδιο.
Κηπουρίδης έγραψε:Θέμα δεύτερο : Brute Force κάθε πιθανὴ κατάσταση, μὲ μόνη βελτίωση ὅτι ἂν εἴχα ὡς πιθανὴ κατάσταση (Θερμοκρασία : 5 , Ἀπαιτούμενη Ἐνέργεια : 10 ) καὶ ( Θ : 10, Ἀ.Ἐ : 10 ) ἔπαιρνα μόνο τὴν δεύτερη κατάσταση ( ἐξίσου γιὰ τὴν ἐνέργεια ). Ἴσα ἴσα νὰ πιάσω τοὺς πόντους τῶν ἐνδεικτικῶν testcases δηλαδή.
Αν και δεν κατάλαβα την βελτιστοποίηση, μάλλον το ίδιο. Στην ουσία bruteforce και εγώ:

Για κάθε φουρνο υπάρχουν 3 επιλογές: Ή να μην κάνουμε τίποτα (ΔΕΝ γινεται αν σε αυτόν τον φούρνο έχουμε αύξηση θερμοκρασίας), ή να μειώσουμε την θερμοκρασία (ΔΕΝ εχεί νόημα αν σε αυτόν τον φούρνο έχουμε την μικρότερη μέχρι τώρα θερμοκρασία) ή να παρακάμψουμε τον φούρνο. Άρα σε κάθε φούρνο 2 επιλογές.
Οπότε (πολύ απλοποιημένα):
S(i, energy, min_temp) = min(
S(i+1, energy, min_temp [[ή t αν t<min_temp]] ),
S(i+1, energy+(t-min_temp),min_temp),
S(i+1, energy+2*t, min_temp)
)
ή κάτι τέτοιο τέλως πάντων.

Κηπουρίδης έγραψε:Θέμα τρίτο : Μιὰ ἀπ` τὰ ἴδια, γιὰ κάθε πιθανὴ κατάσταση, ἔπαιρνα τὴν περίπτωση νὰ πάμε στὴν ἀμέσως ἀριστερά βάρκα, ἂν ὑπάρχει, καὶ στὴν ἀμέσως δεξιά ( ἂν ὑπάρχει ).

Αυτό. Δηλαδή bruteforce με την βελτιστοποίηση του ότι σε κάθε κόμβο υπάρχουν 2 μόνο έξυπνες επιλογες που μπορεί να οδηγήσουν στην βέλτιστη λύση, αντί για Ν: Ή να πάμε στον πρώτο ψαρά προς τα αριστερά (τον οποίο δεν έχουμε επισκεφτεί) ή τον πρώτο προς τα δεξιά.
Φυσικά αν επισκεφτούμε όλες τις βάρκες ή έχουμε ήδη κάνει Μ βήματα σταματάμε (γιατί τελείωσαν τα ψάρια).

Αυτές οι λύσεις έγιναν αποδεκτές με 3/3 στα ενδεικτικά testcase.
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις

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

Βγήκαν! Είμαι 4ος, και πολύ ευχαριστημένος!
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Άβαταρ μέλους
ntziris
Δημοσιεύσεις: 10
Εγγραφή: Παρ Δεκ 31, 2010 2:08 am
Τοποθεσία: Κρήτη

Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις

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

Εγώ είμαι 7ος :D
Άβαταρ μέλους
karaggeorge
Δημοσιεύσεις: 37
Εγγραφή: Σάβ Οκτ 31, 2009 2:25 pm

Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις

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

Εγω ειμαι 9ος και καθολου ευχαριστημενος...
κυριως απο το 2ο θεμα...
τελικα αμα κανεις μια απλη και εμπιστη brute-force καταληγεις ψηλα :?
Εικόνα
Virus•Hacker•Kontos
Δημοσιεύσεις: 170
Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm

Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις

Δημοσίευση από Virus•Hacker•Kontos »

μμμ, βασικά ήμουν πολύ απογοητευμένος μετά την έξοδό μου απο την αίθουσα...
Στην ουσία έκανα brute force στο πρώτο πρόβλημα και στα άλλα δύο βασικά τιποτα... :oops:

Βασικά ήταν ενα sort και μετά brute force, έτσι ώστε να βρώ τα μεγαλύτερα πρώτα...
Δούλεψε αρκετά καλύτερα απο όσο περίμενα τελικά...

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

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

Καλή επιτύχια στους επιτύχοντες, να γυρίσετε απο ολυμπιάδες βαλκανιάδες με μετάλλια! :P :D
DFS Hole:
Spoiler: show
http://virushackerwhizkid.blogspot.com/ ... ze-it.html
DFS = Deep Freeze System
Είμαι σίγουρος ότι το πιστέψατε.
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις

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

Για όσους ενδιαφέρονται , το hellenico/contest έχει την 3η φάση στην κατηγορία των προηγούμενων διαγωνισμών , κάτι που σημαίνει πως μπορείτε να δείτε την λύση σας και την επίδοση του προγράμματος σας στα testcases . ;)

ΥΓ: Καλό μήνα σε όλους μας και συγχαρητήρια σε όσους προκρίθηκαν στο Camp .
Άβαταρ μέλους
ntziris
Δημοσιεύσεις: 10
Εγγραφή: Παρ Δεκ 31, 2010 2:08 am
Τοποθεσία: Κρήτη

Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις

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

compileGuy έγραψε:Για όσους ενδιαφέρονται , το hellenico/contest έχει την 3η φάση στην κατηγορία των προηγούμενων διαγωνισμών , κάτι που σημαίνει πως μπορείτε να δείτε την λύση σας και την επίδοση του προγράμματος σας στα testcases . ;)

ΥΓ: Καλό μήνα σε όλους μας και συγχαρητήρια σε όσους προκρίθηκαν στο Camp .
Εμένα δεν είναι έγκυρος ο κωδικός μου... :(
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις

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

ntziris έγραψε:
compileGuy έγραψε:Για όσους ενδιαφέρονται , το hellenico/contest έχει την 3η φάση στην κατηγορία των προηγούμενων διαγωνισμών , κάτι που σημαίνει πως μπορείτε να δείτε την λύση σας και την επίδοση του προγράμματος σας στα testcases . ;)

ΥΓ: Καλό μήνα σε όλους μας και συγχαρητήρια σε όσους προκρίθηκαν στο Camp .
Εμένα δεν είναι έγκυρος ο κωδικός μου... :(
Πρέπει νὰ χρησιμοποιήσεις τὸν κωδικὸ ποὺ σοὺ ἔδωσαν τὴν ὥρα τοῦ διαγωνισμοῦ.
Ἂν δὲν τὸν θυμάσαι, στεῖλε μήνυμα στὸν ΠΔΠ νὰ στὸν πεῖ.
Λύσεις θεμάτων ΠΔΠ: 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/
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις

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

Παράκληση προς όποιον γνωρίζει πώς λύνεται, να ανέβει καμμιά λύση ρε παιδιά για το τρίτο θέμα της Γ Φάσης!
Λύσεις θεμάτων ΠΔΠ: 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/
Απάντηση