Εργαστήριο Τεχνολογίας Λογισμικού
+1 vote
170 views

Στο πρόβλημα 6 της σειράς 7 το πρόγραμμα που έχω γράψει δίνει τα σωστά αποτελέσματα και περνάει όλα τα test cases του grader όμως στο τέλος εμφανίζει το παρακάτω . Τι μπορώ να κάνω ;
( έχω χρησιμοποιήσει codeblocks χωρίς pzhelp , δεν ξέρω αν έχει κάποια σημασία )

in progintro by (180 points)
retagged by | 170 views

1 Answer

+3 votes

Αν δεις την εκφώνηση του προβλήματος, λέει ότι η λύση σου θα πρέπει να τρέχει σε κάτω από 1 δευτερόλεπτο σε όλα τα testcases. Όπως λέει και το σφάλμα, στα testcases 9, 10 & 11 η λύση σου υπερέβη το χρονικό όριο (δηλαδή έτρεξε για πάνω από 1 δευτερόλεπτο). Τα τελευταία testcases είναι συνήθως και τα πιο μεγάλα οπότε είναι λογικό να περνάς τα μικρότερα και όχι αυτά.

(Υποθέτω ότι έχετε διδαχθεί την ένοια της πολυπλοκότητας στο μάθημα, μπορείς να διαβάσεις και περισσότερα σε αυτό το άρθρο.)

Η υπέρβαση του χρονικού ορίου γίνεται συνήθως επειδή το πρόγραμμά μας δεν έχει καλή πολυπλοκότητα. Υποθέτουμε ότι ένας υπολογιστής (όπως ο grader) μπορεί να εκτελέσει περίπου $10^8$ πράξεις το δευτερόλεπτο. Στην εκφώνηση δίνεται ότι το $n$ είναι $n \leq 5 \cdot 10^6$. Αυτό σημαίνει ότι:

  • Ένας αλγόριθμος με πολυπλοκότητα $O(n)$ θα κάνει στην χειρότερη, περίπου $n$ πράξεις, δηλαδή ~$5 \cdot 10^6$. Άρα θα χρειαστεί $ \frac{5 \cdot 10^6}{10^8} = 0.05 sec$, δηλαδή θα τρέξει εντός χρονικού ορίου.
  • Αντίθετα, μια λύση που έχει πολυπλοκότητα $O(n^2)$, θα χρειαστεί $ \frac{5^2 \cdot 10^{12}}{10^8} = 50000 sec$, πολύ περισσότερο από ένα δευτερόλεπτο. Προφανώς, ο grader περίπου στο 1 δευτερόλεπτο θα σταματήσει την εκτέλεση της λύσης και θα μας πει ότι υπερβήκαμε το χρονικό όριο.

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

by (2.4k points)

298 questions

287 answers

287 comments

3.2k users