Θέμα Β' φάσης Λυκείων

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

Θέμα Β' φάσης Λυκείων

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

Καλημέρα σας,

εφόσον το σύστημα υποβολών έχει κλείσει θα ήθελα να δω τις εντυπώσεις σας για το θέμα (fairmaze). Κατά την γνώμη μου ήταν βατό. Εσείς τι λέτε;
Python, C++
kostas1507
Δημοσιεύσεις: 33
Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm

Re: Θέμα Β' φάσης Λυκείων

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

Βατό όντος νομίζω! Μόνο που πρέπει κανείς να μην αναπαυτεί στην απλή λύση του να ακολουθεί τον δρόμο από όλα τα κελιά, με όσα optimization και να κάνει (π.χ. να μην ξανά περνάει από τον ίδιο δρόμο). Η βέλτιστη λύση (εκτός αν χάνω κάτι) είναι πολυπλοκότητας ίση με όσα κελιά οδηγούν έξω και σε μεγάλα test case είναι χιλιάδες φορές πιο γρήγορη από την απλή.
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

Re: Θέμα Β' φάσης Λυκείων

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

Ναι θέλει προσοχή να μην περνάς τα ίδια δωμάτια και μπορείς να μειώσεις δραματικά τις επαναλήψεις αν σκεφτείς λίγο. Εγώ προσωπικά δεν ξέρω αν πέτυχα την βέλτιστη πολυπλοκότητα αλλά τρέχοντας το σε linux terminal με την time οι χρόνοι ήταν κάτι παραπάνω από ικανοποιητικοί και σε μεγάλα testacases.
Καλά Αποτελέσματα!
Python, C++
kostas1507
Δημοσιεύσεις: 33
Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm

Re: Θέμα Β' φάσης Λυκείων

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

Εγώ κατέληξα να κοιτάζω μόνο τα δωμάτια που βγάζουν έξω. Δηλαδή να κοιτάζω πρώτα όλα τα δωμάτια στις άκρες και ακολουθώ ανάποδα αυτά που μπορούν να βγούν έξω. Έτσι βρίσκω τον αριθμό των δωματίων που καταλήγουν έξω και τον αφαιρώ από το σύνολο για να βρω τα υπόλοιπα που ζητάει και το πρόβλημα. Αφού υπάρχει μόνο μια μικρή πιθανότητα κάποιο δωμάτιο που δεν βρίσκεται κοντά στις άκρες να καταλήγει έξω και με βάση τις δοκιμές μου (επίσης σε linux terminal) η διαφορές σε μεγάλα test case είναι πολύ σημαντικές σε σχέση την άλλη μέθοδο.
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Θέμα Β' φάσης Λυκείων

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

Ένα βαρύ, αυτοσχέδιο, test case:
https://drive.google.com/file/d/1ecBAci ... sp=sharing
Η απάντηση είναι 980000.
kostas1507
Δημοσιεύσεις: 33
Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm

Re: Θέμα Β' φάσης Λυκείων

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

Πήρε 0.037 δευτερόλεπτα στο σύστημα μου με τον τρόπο που εξηγώ πάνω και σταμάτησα να περιμένω κάπου στο λεπτό με τον άλλο τρόπο.. Τώρα ίσος έχω κάποιο σημαντικό λάθος στον άλλο τρόπο, πάντως με εκείνο καταφέρνω το δευτερόλεπτο μόνο για περιπτώσεις πίνακα μικρότερο από ~200x200, ενώ με τoν άλλο πετυχαίνω το δευτερόλεπτο σε ακόμα και με testcase ~5000x5000 που είναι ~625 φορές μεγαλύτερο (τα testcase που χρησιμοποιώ είναι με τυχαίους αριθμούς και όχι σαν αυτό που έστειλες).
edit: η διαφορά θα ήταν πολύ μεγαλύτερη σε χρόνο αν χρησιμοποιούσα και με τα δύο πίνακα 5000x5000
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Θέμα Β' φάσης Λυκείων

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

Αυτό το test case ήταν δύσκολο για τους ερχομένους απο μέσα. Για σένα, το κατάλληλο test case είναι ένα από αυτά: https://drive.google.com/file/d/1AgQo9z ... sp=sharing :)
Οι απαντήσεις και στα δυο test case είναι 1000 (οι απαντήσεις βρίσκονται και στο test case στο τέλος του αρχείου - μετά τα δεδομένα εισόδου)

Πρέπει να έχεις λάθος στον άλλο τρόπο. Και οι δυο τρόποι έχουν ιδια πολυπλοκότητα Ο(Ν*Μ). Η δικη σου μέθοδος υπερτερεί όταν εχει πολλά που δεν βγαίνουν.
kostas1507
Δημοσιεύσεις: 33
Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm

Re: Θέμα Β' φάσης Λυκείων

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

Ναι σίγουρα θα έχω κάνει γιατί και με αυτά τα testcase δεν πέρνει περισσότερο από 50ms το δικό μου. Και φαντάζομαι οτί τα testcase που δοκιμάζουν από τον διαγωνισμό είναι και για τις 2 περιπτώσεις.
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

Re: Θέμα Β' φάσης Λυκείων

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

Κι εγώ όπως λες το έχω κάνει. 'Εχω πάει στα εξωτερικά δωμάτια έχω βρει ποια οδηγούν έξω και ακολουθούσα τα μονοπάτια μετρώντας. Στο τέλος τα αφαιρούσα από τον συνολικό αριθμό. Θα δω και αυτό το testcase αργότερα.
Python, C++
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

Re: Θέμα Β' φάσης Λυκείων

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

Βγήκαν τα αποτελέσματα. Συγχαρητήρια σε όλους περάσατε δεν περάσατε είναι πολύ σημαντική εμπειρία. Είναι κρίμα που εκτός απρόοποτου θα διαγωνιστούμε στην Γ' φάση διαδικτυακά.
Python, C++
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

Re: Θέμα Β' φάσης Λυκείων

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

Σας έχει σταλεί mail με την αναλυτική βαθμολογία; Εμένα δεν έχει έρθει ακόμα
Python, C++
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

Re: Θέμα Β' φάσης Λυκείων

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

Ενημέρωση: σε εμένα ήρθε το mail. Καλά αποτελέσματα!
Python, C++
Κωσταϛ
Δημοσιεύσεις: 7
Εγγραφή: Κυρ Οκτ 27, 2019 8:41 am

Re: Θέμα Β' φάσης Λυκείων

Δημοσίευση από Κωσταϛ »

Καλησπερα,
Ξερει κανεις αν θα ανακοινωσουν τα testcases τοσο για το γυμνασιο οσο και για το λυκειο?
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

Re: Θέμα Β' φάσης Λυκείων

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

Καλησπέρα,

Κανονικά θα έπρεπε να έχουν ανέβει αλλά αυτό δεν έχει συμβεί. Αν τα θες οπωσδήποτε θα μπορούσες ίσως να τους στείλεις ένα email.
Python, C++
Απάντηση