Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Άβαταρ μέλους
ioannidis007
Δημοσιεύσεις: 29
Εγγραφή: Τετ Δεκ 17, 2008 1:08 am
Επικοινωνία:

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Εγώ δε το έχω λύσει ακόμα :P. Σε τί χρόνο το λύνετε εσείς? Η χαζή λύση είναι σε O(n^2), αλλά βάζω στοίχημα ότι μπορεί να βγεί σε O(nlogn). Θα το προσπαθήσω...

stathis
Site Admin
Δημοσιεύσεις: 379
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

ioannidis007 έγραψε:Εγώ δε το έχω λύσει ακόμα :P. Σε τί χρόνο το λύνετε εσείς? Η χαζή λύση είναι σε O(n^2), αλλά βάζω στοίχημα ότι μπορεί να βγεί σε O(nlogn). Θα το προσπαθήσω...
L+C, σε υπολογιστή με infinite ταχύτητα δίσκου. :P
Πρακτικά, 260ms σε Core 2 Duo, 2.2GHz.

bour1992
Δημοσιεύσεις: 55
Εγγραφή: Πέμ Δεκ 18, 2008 1:50 pm

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Η λυση μου εγινε δεκτη αλλα στα testcase 1,2 και 3 μου γραφει χρονο 0.000sec.
Αυτο σημαινει πως υπαρχει καποιο προβλημα ή οχι?

stathis
Site Admin
Δημοσιεύσεις: 379
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

bour1992 έγραψε:Η λυση μου εγινε δεκτη αλλα στα testcase 1,2 και 3 μου γραφει χρονο 0.000sec.
Αυτο σημαινει πως υπαρχει καποιο προβλημα ή οχι?
Όχι, δεν υπάρχει πρόβλημα.
Τα test cases 1, 2, 3 είναι τα μικρότερα.

Ειδικότερα, συνήθως το 1ο που δίνουν στην εκφώνηση είναι το 1ο και στο grader, και το 2ο επίσης το 2ο αντίστοιχα. Για το 3ο είναι φαντάζομαι λίγο έως αρκετά πιο μεγάλο απ' το 2ο.

georgeha98
Δημοσιεύσεις: 48
Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Μήπως ξέρει κανείς αν επιτρέπεται η χρήση ansistring(Pascal) για τον διαγωνισμό, ή που μπορώ να το μάθω???

stathis
Site Admin
Δημοσιεύσεις: 379
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

georgeha98 έγραψε:Μήπως ξέρει κανείς αν επιτρέπεται η χρήση ansistring(Pascal) για τον διαγωνισμό, ή που μπορώ να το μάθω???
Λογικά θα επιτρέπεται.
Αν θέλεις στείλε στο info@pdp.gr

feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Η λύση όλων σας είναι Θ(L*C). Εφόσον το output είναι της τάξης L*C, τόσο θα κάνει και στην καλύτερη περίπτωση το πρόγραμμα σας. Τα low-level optimizations δεν έχουν θέση στην πολυπλοκότητα του αλγορίθμου.

Λευτέρη, το έχασες το στοίχημα... Αύριο θα έρθω από το σπίτι σου να παραλάβω τις μπύρες που μου χρωστάς :D

stathis
Site Admin
Δημοσιεύσεις: 379
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

feedWARd, υπάρχουν κι άλλοι τρόποι να το λύσεις. Η λύση στη καλύτερη περίπτωση μπορεί να είναι O((L/2)+C), διότι το output μπορεί να γίνει τόσο, κάνοντας L/2 φορές κλήση σε συναρτήσεις output.

feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Για να τυπώσεις Ν χαρακτήρες, θες Ο(Ν)... Το οτί καλείς μια συνάρτηση δεν σημαίνει οτί έχεις Ο(1).

stathis
Site Admin
Δημοσιεύσεις: 379
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Σωστό, αλλά όταν κάνει μια συνάρτηση initialize και free, χάνεις ΠΟΛΥ χρόνο.

Συμφωνώ ότι αλγοριθμικά ισχύει το δικό σου, αλλά μόνο στη θεωρία όπως δε παρατήρησα ότι είπες. :P
Η θεωρία των αλγορίθμων είναι σαν τη μηχανή Carnot.

feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Σου είπα, τα low-level optimizations δεν έχουν σχεση με τον αλγόριθμο (άρα το Ο((L/2) + C) είναι άκυρο).

Αυτά :lol:

Λεύτερη, τελικά δεν μπορώ αύριο. Θα ρθω μεθαύριο :P

Άβαταρ μέλους
ioannidis007
Δημοσιεύσεις: 29
Εγγραφή: Τετ Δεκ 17, 2008 1:08 am
Επικοινωνία:

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Γιάννη έχεις δίκιο, ή μάλλον εγώ είπα βλακεία :D
Οι μπύρες μου είναι όλες δικές σου!

georgeha98
Δημοσιεύσεις: 48
Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Παιδιά, μήπως γνωρίζει κανείς αν επιτρέπεται η χρήση ansistring(pascal) για τον διαγωνισμό?

stathis
Site Admin
Δημοσιεύσεις: 379
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

georgeha98 έγραψε:Παιδιά, μήπως γνωρίζει κανείς αν επιτρέπεται η χρήση ansistring(pascal) για τον διαγωνισμό?
Λογικά επιτρέπεται, δε βρίσκω λόγο για να μην επιτραπεί.

Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Αύριο Δευτέρα 9/2/2009 όποιος θέλει δίνει ένα hint για τη λύση... ;)

bour1992
Δημοσιεύσεις: 55
Εγγραφή: Πέμ Δεκ 18, 2008 1:50 pm

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Τα αποτελεσματα της Α' φασης ποτε βγενουν?

Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Απ'άυριο. ;)
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.

stathis
Site Admin
Δημοσιεύσεις: 379
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Αφού κλείσει το σύστημα αξιολόγησης προτείνω να ποστάρουμε όλοι τις λύσεις μας (θα ρωτήσω και την ΟΕ αν επιτρέπεται αυτό για σιγουριά).

chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

Άντε πότε θα βγούν τα αποτελέσματα! Είναι 12:02!

Σύμφωνα με την δικιά μου ώρα...
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.

Άβαταρ μέλους
eparon
Δημοσιεύσεις: 62
Εγγραφή: Πέμ Δεκ 18, 2008 8:04 pm
Τοποθεσία: Patra
Επικοινωνία:

Re: Α' φάση 21ου ΠΔΠ - "Το ψηφιδωτό του Μεγάλου Αλεξάνδρου"

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

ε κάτσε να ελέγξει όλες τις υποβολές από όλα τα testcases.... ;)
πάντως εμένα όταν έδινα να τι ώρα μου ήρθε η απάντηση για την Α Φάση
from: <info@pdp.gr>
to: -----
date: Sun, Feb 4, 2007 at 3:44 AM
subject: Αναφορά Βαθμολογίας για τον ΠΔΠ19-Α
mailed-by: gmail.com
:)
Εικόνα
Εικόνα

Απάντηση