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

[giorgosk]

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

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

[kostas1507]

Βατό όντος νομίζω! Μόνο που πρέπει κανείς να μην αναπαυτεί στην απλή λύση του να ακολουθεί τον δρόμο από όλα τα κελιά, με όσα optimization και να κάνει (π.χ. να μην ξανά περνάει από τον ίδιο δρόμο). Η βέλτιστη λύση (εκτός αν χάνω κάτι) είναι πολυπλοκότητας ίση με όσα κελιά οδηγούν έξω και σε μεγάλα test case είναι χιλιάδες φορές πιο γρήγορη από την απλή.

[giorgosk]

Ναι θέλει προσοχή να μην περνάς τα ίδια δωμάτια και μπορείς να μειώσεις δραματικά τις επαναλήψεις αν σκεφτείς λίγο. Εγώ προσωπικά δεν ξέρω αν πέτυχα την βέλτιστη πολυπλοκότητα αλλά τρέχοντας το σε linux terminal με την time οι χρόνοι ήταν κάτι παραπάνω από ικανοποιητικοί και σε μεγάλα testacases.
Καλά Αποτελέσματα!

[kostas1507]

Εγώ κατέληξα να κοιτάζω μόνο τα δωμάτια που βγάζουν έξω. Δηλαδή να κοιτάζω πρώτα όλα τα δωμάτια στις άκρες και ακολουθώ ανάποδα αυτά που μπορούν να βγούν έξω. Έτσι βρίσκω τον αριθμό των δωματίων που καταλήγουν έξω και τον αφαιρώ από το σύνολο για να βρω τα υπόλοιπα που ζητάει και το πρόβλημα. Αφού υπάρχει μόνο μια μικρή πιθανότητα κάποιο δωμάτιο που δεν βρίσκεται κοντά στις άκρες να καταλήγει έξω και με βάση τις δοκιμές μου (επίσης σε linux terminal) η διαφορές σε μεγάλα test case είναι πολύ σημαντικές σε σχέση την άλλη μέθοδο.

[switch]

Ένα βαρύ, αυτοσχέδιο, test case:
https://drive.google.com/file/d/1ecBAci ... sp=sharing
Η απάντηση είναι 980000.

[kostas1507]

Πήρε 0.037 δευτερόλεπτα στο σύστημα μου με τον τρόπο που εξηγώ πάνω και σταμάτησα να περιμένω κάπου στο λεπτό με τον άλλο τρόπο.. Τώρα ίσος έχω κάποιο σημαντικό λάθος στον άλλο τρόπο, πάντως με εκείνο καταφέρνω το δευτερόλεπτο μόνο για περιπτώσεις πίνακα μικρότερο από ~200x200, ενώ με τoν άλλο πετυχαίνω το δευτερόλεπτο σε ακόμα και με testcase ~5000x5000 που είναι ~625 φορές μεγαλύτερο (τα testcase που χρησιμοποιώ είναι με τυχαίους αριθμούς και όχι σαν αυτό που έστειλες).
edit: η διαφορά θα ήταν πολύ μεγαλύτερη σε χρόνο αν χρησιμοποιούσα και με τα δύο πίνακα 5000x5000

[switch]

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

Πρέπει να έχεις λάθος στον άλλο τρόπο. Και οι δυο τρόποι έχουν ιδια πολυπλοκότητα Ο(Ν*Μ). Η δικη σου μέθοδος υπερτερεί όταν εχει πολλά που δεν βγαίνουν.

[kostas1507]

Ναι σίγουρα θα έχω κάνει γιατί και με αυτά τα testcase δεν πέρνει περισσότερο από 50ms το δικό μου. Και φαντάζομαι οτί τα testcase που δοκιμάζουν από τον διαγωνισμό είναι και για τις 2 περιπτώσεις.

[giorgosk]

Κι εγώ όπως λες το έχω κάνει. 'Εχω πάει στα εξωτερικά δωμάτια έχω βρει ποια οδηγούν έξω και ακολουθούσα τα μονοπάτια μετρώντας. Στο τέλος τα αφαιρούσα από τον συνολικό αριθμό. Θα δω και αυτό το testcase αργότερα.

[giorgosk]

Βγήκαν τα αποτελέσματα. Συγχαρητήρια σε όλους περάσατε δεν περάσατε είναι πολύ σημαντική εμπειρία. Είναι κρίμα που εκτός απρόοποτου θα διαγωνιστούμε στην Γ' φάση διαδικτυακά.

[giorgosk]

Σας έχει σταλεί mail με την αναλυτική βαθμολογία; Εμένα δεν έχει έρθει ακόμα

[giorgosk]

Ενημέρωση: σε εμένα ήρθε το mail. Καλά αποτελέσματα!

[Κωσταϛ]

Καλησπερα,
Ξερει κανεις αν θα ανακοινωσουν τα testcases τοσο για το γυμνασιο οσο και για το λυκειο?

[giorgosk]

Καλησπέρα,

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