B' Φάση 23ου ΠΔΠ

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: B' Φάση 23ου ΠΔΠ

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

Πως και δεν άνοιξε τοπικ για λύσεις αυτήν την φορά! :lol:
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
mr.muffin
Δημοσιεύσεις: 43
Εγγραφή: Σάβ Νοέμ 20, 2010 11:32 am

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από mr.muffin »

Nα ρωτησω το αυτονοητο? Ο χρονος παραμενει 1 sec?
Virus•Hacker•Kontos
Δημοσιεύσεις: 170
Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από Virus•Hacker•Kontos »

mr.muffin έγραψε:Nα ρωτησω το αυτονοητο? Ο χρονος παραμενει 1 sec?
Seems we've got a problem here:

Για N = 100.000 κάνω χρόνο 45 δευτερόλεπτα.

Σίγουρα υπάρχει λύση που περνάει τα 400.000 σε λιγότερο απο 1 second?
DFS Hole:
Spoiler: show
http://virushackerwhizkid.blogspot.com/ ... ze-it.html
DFS = Deep Freeze System
Είμαι σίγουρος ότι το πιστέψατε.
Virus•Hacker•Kontos
Δημοσιεύσεις: 170
Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από Virus•Hacker•Kontos »

real 0m0.358s
user 0m0.208s
sys 0m0.016s

Εντάξει τελικά το βρήκα.... :D
DFS Hole:
Spoiler: show
http://virushackerwhizkid.blogspot.com/ ... ze-it.html
DFS = Deep Freeze System
Είμαι σίγουρος ότι το πιστέψατε.
mr.muffin
Δημοσιεύσεις: 43
Εγγραφή: Σάβ Νοέμ 20, 2010 11:32 am

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από mr.muffin »

Virus•Hacker•Kontos έγραψε:
mr.muffin έγραψε:Nα ρωτησω το αυτονοητο? Ο χρονος παραμενει 1 sec?
Seems we've got a problem here:

Για N = 100.000 κάνω χρόνο 45 δευτερόλεπτα.

Σίγουρα υπάρχει λύση που περνάει τα 400.000 σε λιγότερο απο 1 second?
Μαλον οχι...
Κανεις 3 λεπτα για testcase n=400.000 ? (Ισως ο χρονος να αυξανετε εκθετικα... αναλογα με τον αλγοριθμο) Μαλον εγω κανω κατι λαθος γιατι μου περνει 10 λεπτα να το τρεξω (2.13 GHZ Intel)

Virus•Hacker•Kontos έγραψε:real 0m0.358s
user 0m0.208s
sys 0m0.016s

Εντάξει τελικά το βρήκα.... :D
Aυτα για ν=400k? Eπισεις μ κανει 30 δευτερολεπτα με τεστ case n=100.000
alexandros
Δημοσιεύσεις: 11
Εγγραφή: Τετ Μαρ 17, 2010 7:20 pm

Re: B' Φάση 23ου ΠΔΠ

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

userresu έγραψε:πάρε
company.txt
Το testcase έχει αποτέλεσμα 0;
Memas
Δημοσιεύσεις: 87
Εγγραφή: Παρ Δεκ 31, 2010 4:13 pm
Επικοινωνία:

Re: B' Φάση 23ου ΠΔΠ

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

Και όριο μνήμης πάλι 64 mb? Αν είναι έτσι ο χρόνος εκτέλεσης θα εκτοξευθεί στα ύψη... :lol:
Virus•Hacker•Kontos
Δημοσιεύσεις: 170
Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από Virus•Hacker•Kontos »

mr.muffin έγραψε:
Virus•Hacker•Kontos έγραψε: real 0m0.358s
user 0m0.208s
sys 0m0.016s

Εντάξει τελικά το βρήκα.... :D
Aυτα για ν=400k? Eπισεις μ κανει 30 δευτερολεπτα με τεστ case n=100.000
Ναι είναι για το testcase που δώσατε στο φόρουμ, και βγάζει αποτέλεσμα 0. :P

Παρόλα αυτά μένει ο αλγόριθμος να γίνει ακόμα πιο γρήγορος. Έχω ήδη άλλες 2 ιδέες για υλοποίηση...
Spoiler: show
Θα μπορούσα να δώσω μια πληροφορία, αλλά θα θεωρηθεί υπονοούμενο για την λύση μου...
Υ.Γ: Θα μπορούσε κανείς να κάνει ένα πιο πολύπλοκο testcase κοντα στα 400,000 Ν? Στο μεταξύ θα δοκιμάσω μήπως φτιάξω κανέναν test generator...
DFS Hole:
Spoiler: show
http://virushackerwhizkid.blogspot.com/ ... ze-it.html
DFS = Deep Freeze System
Είμαι σίγουρος ότι το πιστέψατε.
Memas
Δημοσιεύσεις: 87
Εγγραφή: Παρ Δεκ 31, 2010 4:13 pm
Επικοινωνία:

Re: B' Φάση 23ου ΠΔΠ

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

Έχει κανείς τα παλιά test cases να τα ποστάρει..? :D
Memas
Δημοσιεύσεις: 87
Εγγραφή: Παρ Δεκ 31, 2010 4:13 pm
Επικοινωνία:

Re: B' Φάση 23ου ΠΔΠ

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

Έλεγα πως είχε δημιουργηθεί ατέρμων επανάληψη τώρα που το εκτέλεσα χαχαχαχ δυστυχώς όμως όχι είναι full αργό... :lol: Ισως φτάει το γεγονός ότι μάλλον έχει πολυπλοκότητα Ο(Ν^3)...χααχαχαχαχ :lol:
mr.muffin
Δημοσιεύσεις: 43
Εγγραφή: Σάβ Νοέμ 20, 2010 11:32 am

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από mr.muffin »

Virus•Hacker•Kontos έγραψε:
mr.muffin έγραψε:
Virus•Hacker•Kontos έγραψε: real 0m0.358s
user 0m0.208s
sys 0m0.016s

Εντάξει τελικά το βρήκα.... :D
Aυτα για ν=400k? Eπισεις μ κανει 30 δευτερολεπτα με τεστ case n=100.000
Ναι είναι για το testcase που δώσατε στο φόρουμ, και βγάζει αποτέλεσμα 0. :P

Παρόλα αυτά μένει ο αλγόριθμος να γίνει ακόμα πιο γρήγορος. Έχω ήδη άλλες 2 ιδέες για υλοποίηση...
Spoiler: show
Θα μπορούσα να δώσω μια πληροφορία, αλλά θα θεωρηθεί υπονοούμενο για την λύση μου...
Υ.Γ: Θα μπορούσε κανείς να κάνει ένα πιο πολύπλοκο testcase κοντα στα 400,000 Ν? Στο μεταξύ θα δοκιμάσω μήπως φτιάξω κανέναν test generator...
ελεος θα βαρεσω το κεφαλι μου στον τοιχο!!! Πως κανεις 0.4 δευτερα για 400κ Ν??????????!!
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: B' Φάση 23ου ΠΔΠ

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

Virus•Hacker•Kontos έγραψε:Υ.Γ: Θα μπορούσε κανείς να κάνει ένα πιο πολύπλοκο testcase κοντα στα 400,000 Ν? Στο μεταξύ θα δοκιμάσω μήπως φτιάξω κανέναν test generator...
Αφιερωμένο
Spoiler: show

Κώδικας: Επιλογή όλων

#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

int N;
char gender[400001],g2[400001];
int par[400001],p2[400001];
int perm[400001];
int main ()
{
    freopen("company.in","w",stdout);
    scanf("%d",&N);
    printf("%d\n",N);
    srand(time(0));
    par[1]=0;
    gender[1]=(rand()%2==0)?'m':'f';
    for (int i=2;i<=N;++i)
    {
        par[i]=rand()%(i-1)+1;
        gender[i]=(rand()%2==0)?'m':'f';
    }
    int x,tmp;
    for (int i=1;i<=N;++i) perm[i]=i;
    for (int i=N;i>=2;--i)
    {
        x=rand()%i+1;
        tmp=perm[x];
        perm[x]=perm[i];
        perm[i]=tmp;
    }
    for (int i=1;i<=N;++i)
    {
        p2[perm[i]]=perm[par[i]];
        g2[perm[i]]=gender[i];
    }
    for (int i=1;i<=N;++i)
    printf("%d %c\n",p2[i],g2[i]);
    return 0;
}

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

Re: B' Φάση 23ου ΠΔΠ

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

Μισό δεύτερο run time, αποτέλεσμα 0, όμορφα. :)
Κάποιος να συμπιέσει το 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.
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: B' Φάση 23ου ΠΔΠ

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

Κώδικας: Επιλογή όλων

#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;
}
Virus•Hacker•Kontos
Δημοσιεύσεις: 170
Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από Virus•Hacker•Kontos »

userresu έγραψε: Αφιερωμένο
+10

Βάλε ένα printf() πριν το scanf() γιατι μόλις το έτρεξα λέω, τι γίνεται, περισσότερη ώρα κάνει να φτιάξει το testcase παρά να το λύσει?

Μεχρι που κοίταξα τον κώδικα.

Πολλά ευχαριστώ anyway!...


EDIT: Μπορεί κάποιος να επαληθεύσει με αυτόν τον test generator, N = 400.000 και με seed = 1000 ( αντι για time(0) ) αν το αποτελεσμά του είναι 413913 ?
Spoiler: show
Αν ναι, μάλλον η λύση μου είναι σωστή και γρήγορη...
DFS Hole:
Spoiler: show
http://virushackerwhizkid.blogspot.com/ ... ze-it.html
DFS = Deep Freeze System
Είμαι σίγουρος ότι το πιστέψατε.
mr.muffin
Δημοσιεύσεις: 43
Εγγραφή: Σάβ Νοέμ 20, 2010 11:32 am

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από mr.muffin »

Ohh MY GOD! Why the heck does this happen?

Οκ επομενο βημα ειναι ο χαρδαβελας... οταν ειναι με την σειρα το testcase απο το 1 μεχρι το 400k κανει 10 λεπτα οταν ειναι στην τυχη κανει 0.40 δευτερα.....
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: B' Φάση 23ου ΠΔΠ

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

mr.muffin έγραψε:Ohh MY GOD! Why the heck does this happen?

Οκ επομενο βημα ειναι ο χαρδαβελας... οταν ειναι με την σειρα το testcase απο το 1 μεχρι το 400k κανει 10 λεπτα οταν ειναι στην τυχη κανει 0.40 δευτερα.....
Όταν η ιεραρχία δεν έχει δομή δέντρου αλλά σειριακή(1:arrow:2:arrow:3 κ.ο.κ.), πολλοί γνωστοί αλγόριθμοι πάνε για βρούβες χρονικά.

Που να δεις 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.
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: B' Φάση 23ου ΠΔΠ

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

Virus•Hacker•Kontos έγραψε: EDIT: Μπορεί κάποιος να επαληθεύσει με αυτόν τον test generator, N = 400.000 και με seed = 1000 ( αντι για time(0) ) αν το αποτελεσμά του είναι 413913 ?
Spoiler: show
Αν ναι, μάλλον η λύση μου είναι σωστή και γρήγορη...
εμένα μου βγαίνει 1 :shock: (πάω να ξαναδώ τον κώδικά μου)

[edit] sorry λάθος .in :D . Ναι, τόσο μου βγαίνει.

μόνο με τον 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.
Virus•Hacker•Kontos
Δημοσιεύσεις: 170
Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από Virus•Hacker•Kontos »

thetrojan01 έγραψε:
Virus•Hacker•Kontos έγραψε: EDIT: Μπορεί κάποιος να επαληθεύσει με αυτόν τον test generator, N = 400.000 και με seed = 1000 ( αντι για time(0) ) αν το αποτελεσμά του είναι 413913 ?
Spoiler: show
Αν ναι, μάλλον η λύση μου είναι σωστή και γρήγορη...
[edit] sorry λάθος .in :D . Ναι, τόσο μου βγαίνει.

μόνο με τον 2ο test case generator του userresu (αν τον έχω κάνει copy-paste σωστά στο Vim) μου βγάζει segmentation fault για οσοδήποτε Ν.
F**k.
Η ακόμα γρηγορότερη λύση μου κάπου χάνει ενώ τελικά δεν είναι και τόσο πιο γρήγορη όσο περίμενα.
Θα το τσεκάρω, αν και τελικά νομίζω πως την χθεσινή θα αφήσω, γιατι δεν είδα περισσότερο χρόνο απο 0,550 σε κανένα test case με Ν = 400.000...
DFS Hole:
Spoiler: show
http://virushackerwhizkid.blogspot.com/ ... ze-it.html
DFS = Deep Freeze System
Είμαι σίγουρος ότι το πιστέψατε.
mr.muffin
Δημοσιεύσεις: 43
Εγγραφή: Σάβ Νοέμ 20, 2010 11:32 am

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από mr.muffin »

ποσο πρεπει να σκοραρω για να περασω την δευτερη φαση?
Απάντηση