pdp forum

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

Ἀρχίζω :

Ἔλυσα τὸ πρῶτο παίρνοντας ἀρχικὰ ὡς 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. )

ΣΕΙΡΑ ΣΑΣ!

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

καλη επιτυχια σε ολους ( ποτε θα βγουν επιτελους τα αποτελεσματα;;)

Κηπουρίδης έγραψε: Ἔλυσα τὸ πρῶτο παίρνοντας ἀρχικὰ ὡς 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.

Βγήκαν! Είμαι 4ος, και πολύ ευχαριστημένος!

Εγώ είμαι 7ος

Εγω ειμαι 9ος και καθολου ευχαριστημενος...
κυριως απο το 2ο θεμα...
τελικα αμα κανεις μια απλη και εμπιστη brute-force καταληγεις ψηλα

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

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

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

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

Καλή επιτύχια στους επιτύχοντες, να γυρίσετε απο ολυμπιάδες βαλκανιάδες με μετάλλια!

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

ΥΓ: Καλό μήνα σε όλους μας και συγχαρητήρια σε όσους προκρίθηκαν στο Camp .

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

ΥΓ: Καλό μήνα σε όλους μας και συγχαρητήρια σε όσους προκρίθηκαν στο Camp .

Εμένα δεν είναι έγκυρος ο κωδικός μου...

ntziris έγραψε:

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

ΥΓ: Καλό μήνα σε όλους μας και συγχαρητήρια σε όσους προκρίθηκαν στο Camp .

Εμένα δεν είναι έγκυρος ο κωδικός μου...

Πρέπει νὰ χρησιμοποιήσεις τὸν κωδικὸ ποὺ σοὺ ἔδωσαν τὴν ὥρα τοῦ διαγωνισμοῦ.
Ἂν δὲν τὸν θυμάσαι, στεῖλε μήνυμα στὸν ΠΔΠ νὰ στὸν πεῖ.

Παράκληση προς όποιον γνωρίζει πώς λύνεται, να ανέβει καμμιά λύση ρε παιδιά για το τρίτο θέμα της Γ Φάσης!