B' Φάση 23ου ΠΔΠ
Re: B' Φάση 23ου ΠΔΠ
Πως και δεν άνοιξε τοπικ για λύσεις αυτήν την φορά!
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Re: B' Φάση 23ου ΠΔΠ
Nα ρωτησω το αυτονοητο? Ο χρονος παραμενει 1 sec?
-
- Δημοσιεύσεις: 170
- Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm
Re: B' Φάση 23ου ΠΔΠ
Seems we've got a problem here:mr.muffin έγραψε:Nα ρωτησω το αυτονοητο? Ο χρονος παραμενει 1 sec?
Για N = 100.000 κάνω χρόνο 45 δευτερόλεπτα.
Σίγουρα υπάρχει λύση που περνάει τα 400.000 σε λιγότερο απο 1 second?
DFS Hole:
- Spoiler: show
-
- Δημοσιεύσεις: 170
- Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm
Re: B' Φάση 23ου ΠΔΠ
real 0m0.358s
user 0m0.208s
sys 0m0.016s
Εντάξει τελικά το βρήκα....
user 0m0.208s
sys 0m0.016s
Εντάξει τελικά το βρήκα....
DFS Hole:
- Spoiler: show
Re: B' Φάση 23ου ΠΔΠ
Μαλον οχι...Virus•Hacker•Kontos έγραψε:Seems we've got a problem here:mr.muffin έγραψε:Nα ρωτησω το αυτονοητο? Ο χρονος παραμενει 1 sec?
Για N = 100.000 κάνω χρόνο 45 δευτερόλεπτα.
Σίγουρα υπάρχει λύση που περνάει τα 400.000 σε λιγότερο απο 1 second?
Κανεις 3 λεπτα για testcase n=400.000 ? (Ισως ο χρονος να αυξανετε εκθετικα... αναλογα με τον αλγοριθμο) Μαλον εγω κανω κατι λαθος γιατι μου περνει 10 λεπτα να το τρεξω (2.13 GHZ Intel)
Aυτα για ν=400k? Eπισεις μ κανει 30 δευτερολεπτα με τεστ case n=100.000Virus•Hacker•Kontos έγραψε:real 0m0.358s
user 0m0.208s
sys 0m0.016s
Εντάξει τελικά το βρήκα....
-
- Δημοσιεύσεις: 11
- Εγγραφή: Τετ Μαρ 17, 2010 7:20 pm
Re: B' Φάση 23ου ΠΔΠ
Το testcase έχει αποτέλεσμα 0;userresu έγραψε:πάρε
Re: B' Φάση 23ου ΠΔΠ
Και όριο μνήμης πάλι 64 mb? Αν είναι έτσι ο χρόνος εκτέλεσης θα εκτοξευθεί στα ύψη...
- Spoiler: show
-
- Δημοσιεύσεις: 170
- Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm
Re: B' Φάση 23ου ΠΔΠ
Ναι είναι για το testcase που δώσατε στο φόρουμ, και βγάζει αποτέλεσμα 0.mr.muffin έγραψε:
Aυτα για ν=400k? Eπισεις μ κανει 30 δευτερολεπτα με τεστ case n=100.000Virus•Hacker•Kontos έγραψε: real 0m0.358s
user 0m0.208s
sys 0m0.016s
Εντάξει τελικά το βρήκα....
Παρόλα αυτά μένει ο αλγόριθμος να γίνει ακόμα πιο γρήγορος. Έχω ήδη άλλες 2 ιδέες για υλοποίηση...
- Spoiler: show
DFS Hole:
- Spoiler: show
Re: B' Φάση 23ου ΠΔΠ
Έλεγα πως είχε δημιουργηθεί ατέρμων επανάληψη τώρα που το εκτέλεσα χαχαχαχ δυστυχώς όμως όχι είναι full αργό... Ισως φτάει το γεγονός ότι μάλλον έχει πολυπλοκότητα Ο(Ν^3)...χααχαχαχαχ
- Spoiler: show
Re: B' Φάση 23ου ΠΔΠ
ελεος θα βαρεσω το κεφαλι μου στον τοιχο!!! Πως κανεις 0.4 δευτερα για 400κ Ν??????????!!Virus•Hacker•Kontos έγραψε:Ναι είναι για το testcase που δώσατε στο φόρουμ, και βγάζει αποτέλεσμα 0.mr.muffin έγραψε:
Aυτα για ν=400k? Eπισεις μ κανει 30 δευτερολεπτα με τεστ case n=100.000Virus•Hacker•Kontos έγραψε: real 0m0.358s
user 0m0.208s
sys 0m0.016s
Εντάξει τελικά το βρήκα....
Παρόλα αυτά μένει ο αλγόριθμος να γίνει ακόμα πιο γρήγορος. Έχω ήδη άλλες 2 ιδέες για υλοποίηση...
Υ.Γ: Θα μπορούσε κανείς να κάνει ένα πιο πολύπλοκο testcase κοντα στα 400,000 Ν? Στο μεταξύ θα δοκιμάσω μήπως φτιάξω κανέναν test generator...
- Spoiler: show
Re: B' Φάση 23ου ΠΔΠ
ΑφιερωμένοVirus•Hacker•Kontos έγραψε:Υ.Γ: Θα μπορούσε κανείς να κάνει ένα πιο πολύπλοκο testcase κοντα στα 400,000 Ν? Στο μεταξύ θα δοκιμάσω μήπως φτιάξω κανέναν test generator...
- Spoiler: show
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: B' Φάση 23ου ΠΔΠ
Μισό δεύτερο run time, αποτέλεσμα 0, όμορφα.
Κάποιος να συμπιέσει το test case, ή ακόμη καλύτερα να δώσει ο userresu το seed, έχει ψιλο-ψοφήσει ο server απ'τα κατεβάσματα
Κάποιος να συμπιέσει το test case, ή ακόμη καλύτερα να δώσει ο userresu το seed, έχει ψιλο-ψοφήσει ο server απ'τα κατεβάσματα
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
Re: B' Φάση 23ου ΠΔΠ
Κώδικας: Επιλογή όλων
#include <stdio.h>
int main ()
{
freopen("company.in","w",stdout);
printf("400000\n");
printf("0 m\n");
for (int i=1;i<=399998;++i)
printf("%d f\n",i);
printf("399999 m\n");
return 0;
}
-
- Δημοσιεύσεις: 170
- Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm
Re: B' Φάση 23ου ΠΔΠ
+10userresu έγραψε: Αφιερωμένο
Βάλε ένα printf() πριν το scanf() γιατι μόλις το έτρεξα λέω, τι γίνεται, περισσότερη ώρα κάνει να φτιάξει το testcase παρά να το λύσει?
Μεχρι που κοίταξα τον κώδικα.
Πολλά ευχαριστώ anyway!...
EDIT: Μπορεί κάποιος να επαληθεύσει με αυτόν τον test generator, N = 400.000 και με seed = 1000 ( αντι για time(0) ) αν το αποτελεσμά του είναι 413913 ?
- Spoiler: show
DFS Hole:
- Spoiler: show
Re: B' Φάση 23ου ΠΔΠ
Ohh MY GOD! Why the heck does this happen?
Οκ επομενο βημα ειναι ο χαρδαβελας... οταν ειναι με την σειρα το testcase απο το 1 μεχρι το 400k κανει 10 λεπτα οταν ειναι στην τυχη κανει 0.40 δευτερα.....
Οκ επομενο βημα ειναι ο χαρδαβελας... οταν ειναι με την σειρα το testcase απο το 1 μεχρι το 400k κανει 10 λεπτα οταν ειναι στην τυχη κανει 0.40 δευτερα.....
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: B' Φάση 23ου ΠΔΠ
Όταν η ιεραρχία δεν έχει δομή δέντρου αλλά σειριακή(1:arrow:2:arrow:3 κ.ο.κ.), πολλοί γνωστοί αλγόριθμοι πάνε για βρούβες χρονικά.mr.muffin έγραψε:Ohh MY GOD! Why the heck does this happen?
Οκ επομενο βημα ειναι ο χαρδαβελας... οταν ειναι με την σειρα το testcase απο το 1 μεχρι το 400k κανει 10 λεπτα οταν ειναι στην τυχη κανει 0.40 δευτερα.....
Που να δεις bubble sort ή αφελή υλοποίηση quick sort με εντελώς αναποδο-ταξινομημένο αρχικό πίνακα...
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: B' Φάση 23ου ΠΔΠ
εμένα μου βγαίνει 1 (πάω να ξαναδώ τον κώδικά μου)Virus•Hacker•Kontos έγραψε: EDIT: Μπορεί κάποιος να επαληθεύσει με αυτόν τον test generator, N = 400.000 και με seed = 1000 ( αντι για time(0) ) αν το αποτελεσμά του είναι 413913 ?
- Spoiler: show
[edit] sorry λάθος .in . Ναι, τόσο μου βγαίνει.
μόνο με τον 2ο test case generator του userresu (αν τον έχω κάνει copy-paste σωστά στο Vim) μου βγάζει segmentation fault για οσοδήποτε Ν.
edit2: μάλλον πρέπει να τροποποιήσω τον κυρίως αλγόριθμό μου
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
-
- Δημοσιεύσεις: 170
- Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm
Re: B' Φάση 23ου ΠΔΠ
F**k.thetrojan01 έγραψε:[edit] sorry λάθος .in . Ναι, τόσο μου βγαίνει.Virus•Hacker•Kontos έγραψε: EDIT: Μπορεί κάποιος να επαληθεύσει με αυτόν τον test generator, N = 400.000 και με seed = 1000 ( αντι για time(0) ) αν το αποτελεσμά του είναι 413913 ?
- Spoiler: show
μόνο με τον 2ο test case generator του userresu (αν τον έχω κάνει copy-paste σωστά στο Vim) μου βγάζει segmentation fault για οσοδήποτε Ν.
Η ακόμα γρηγορότερη λύση μου κάπου χάνει ενώ τελικά δεν είναι και τόσο πιο γρήγορη όσο περίμενα.
Θα το τσεκάρω, αν και τελικά νομίζω πως την χθεσινή θα αφήσω, γιατι δεν είδα περισσότερο χρόνο απο 0,550 σε κανένα test case με Ν = 400.000...
DFS Hole:
- Spoiler: show
Re: B' Φάση 23ου ΠΔΠ
ποσο πρεπει να σκοραρω για να περασω την δευτερη φαση?