Γ' Φάση-Λύσεις+Ἐπιδόσεις
- Κηπουρίδης
- Δημοσιεύσεις: 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. )
ΣΕΙΡΑ ΣΑΣ!
Ἀρχίζω :
Ἔλυσα τὸ πρῶτο παίρνοντας ἀρχικὰ ὡς 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/
Μπούσουλας διαβάσματος ΠΔΠ: 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: Γ' Φάση-Λύσεις+Ἐπιδόσεις
Συμφωνω με το 1ο...
στο 2ο εκανα ντ-π ( ) ή απλειστο αλγοριθμο οπως υποστηριζει ο κηπου...
στο 3ο πηρα ως δεδομενο πως δεν μπορεις να πας 2 φορες στην ιδια πλευρα (αρνητικα -θετικα)
πραγμα το οποιο αποδείχτηκε λαθος...
καλη επιτυχια σε ολους ( ποτε θα βγουν επιτελους τα αποτελεσματα;;)
στο 2ο εκανα ντ-π ( ) ή απλειστο αλγοριθμο οπως υποστηριζει ο κηπου...
στο 3ο πηρα ως δεδομενο πως δεν μπορεις να πας 2 φορες στην ιδια πλευρα (αρνητικα -θετικα)
πραγμα το οποιο αποδείχτηκε λαθος...
καλη επιτυχια σε ολους ( ποτε θα βγουν επιτελους τα αποτελεσματα;;)
Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις
Περίπου το ίδιο.Κηπουρίδης έγραψε: Ἔλυσα τὸ πρῶτο παίρνοντας ἀρχικὰ ὡς maximum τὸν πρῶτο ἀριθμό, κὶ ἐλάχιστο κοινὸ πολλαπλάσιο μέχρι στιγμῆς, τὸν πρῶτο ἀριθμό. Γιὰ κάθε ἐπόμενο ἀριθμό, ἔβρισκα τὸ ἐλάχιστο κοινὸ πολλαπλάσιο μεταξὺ αὐτοῦ καὶ τοῦ προηγούμενου Ε.Κ.Π. κὶ ἂν ὁ ἀριθμὸς ἤταν μεγαλύτερος τοῦ maximum καὶ ἴσος μὲ τὸ Ε.Κ.Π. , τότε ἤταν ὁ νέος maximum.
Αν και δεν κατάλαβα την βελτιστοποίηση, μάλλον το ίδιο. Στην ουσία bruteforce και εγώ:Κηπουρίδης έγραψε:Θέμα δεύτερο : Brute Force κάθε πιθανὴ κατάσταση, μὲ μόνη βελτίωση ὅτι ἂν εἴχα ὡς πιθανὴ κατάσταση (Θερμοκρασία : 5 , Ἀπαιτούμενη Ἐνέργεια : 10 ) καὶ ( Θ : 10, Ἀ.Ἐ : 10 ) ἔπαιρνα μόνο τὴν δεύτερη κατάσταση ( ἐξίσου γιὰ τὴν ἐνέργεια ). Ἴσα ἴσα νὰ πιάσω τοὺς πόντους τῶν ἐνδεικτικῶν testcases δηλαδή.
Για κάθε φουρνο υπάρχουν 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 δημοσιεύσεις, έβαλα και υπογραφή.
Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις
Βγήκαν! Είμαι 4ος, και πολύ ευχαριστημένος!
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις
Εγώ είμαι 7ος
- karaggeorge
- Δημοσιεύσεις: 37
- Εγγραφή: Σάβ Οκτ 31, 2009 2:25 pm
Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις
Εγω ειμαι 9ος και καθολου ευχαριστημενος...
κυριως απο το 2ο θεμα...
τελικα αμα κανεις μια απλη και εμπιστη brute-force καταληγεις ψηλα
κυριως απο το 2ο θεμα...
τελικα αμα κανεις μια απλη και εμπιστη brute-force καταληγεις ψηλα
-
- Δημοσιεύσεις: 170
- Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm
Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις
μμμ, βασικά ήμουν πολύ απογοητευμένος μετά την έξοδό μου απο την αίθουσα...
Στην ουσία έκανα brute force στο πρώτο πρόβλημα και στα άλλα δύο βασικά τιποτα...
Βασικά ήταν ενα sort και μετά brute force, έτσι ώστε να βρώ τα μεγαλύτερα πρώτα...
Δούλεψε αρκετά καλύτερα απο όσο περίμενα τελικά...
Μεγάλη αποτυχία έλεγα, μέχρι που βγήκαν τα αποτελέσματα.
Ε δεν μπορώ να πω πως είμαι ευχαριστιμένος με την απόδοσή μου, απλά δεν περίμενα να έχω τόσο καλή θέση, (17η) σύμφωνα με αυτά που έλυσα...
Ε γενικά, για του χρόνου στρώνομαι απο τώρα θα διαβάσω πολλά βιβλία, θα λύσω πολλά προβλήματα, ελπίζω να τα καταφέρω...
Καλή επιτύχια στους επιτύχοντες, να γυρίσετε απο ολυμπιάδες βαλκανιάδες με μετάλλια!
Στην ουσία έκανα brute force στο πρώτο πρόβλημα και στα άλλα δύο βασικά τιποτα...
Βασικά ήταν ενα sort και μετά brute force, έτσι ώστε να βρώ τα μεγαλύτερα πρώτα...
Δούλεψε αρκετά καλύτερα απο όσο περίμενα τελικά...
Μεγάλη αποτυχία έλεγα, μέχρι που βγήκαν τα αποτελέσματα.
Ε δεν μπορώ να πω πως είμαι ευχαριστιμένος με την απόδοσή μου, απλά δεν περίμενα να έχω τόσο καλή θέση, (17η) σύμφωνα με αυτά που έλυσα...
Ε γενικά, για του χρόνου στρώνομαι απο τώρα θα διαβάσω πολλά βιβλία, θα λύσω πολλά προβλήματα, ελπίζω να τα καταφέρω...
Καλή επιτύχια στους επιτύχοντες, να γυρίσετε απο ολυμπιάδες βαλκανιάδες με μετάλλια!
DFS Hole:
- Spoiler: show
- compileGuy
- Δημοσιεύσεις: 218
- Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm
Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις
Για όσους ενδιαφέρονται , το hellenico/contest έχει την 3η φάση στην κατηγορία των προηγούμενων διαγωνισμών , κάτι που σημαίνει πως μπορείτε να δείτε την λύση σας και την επίδοση του προγράμματος σας στα testcases .
ΥΓ: Καλό μήνα σε όλους μας και συγχαρητήρια σε όσους προκρίθηκαν στο Camp .
ΥΓ: Καλό μήνα σε όλους μας και συγχαρητήρια σε όσους προκρίθηκαν στο Camp .
Re: Γ' Φάση-Λύσεις+Ἐπιδόσεις
Εμένα δεν είναι έγκυρος ο κωδικός μου...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/
Μπούσουλας διαβάσματος ΠΔΠ: 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/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/