pdp forum

Δημοσιεύτηκε: **Τρί Φεβ 22, 2011 10:27 pm**

Πως και δεν άνοιξε τοπικ για λύσεις αυτήν την φορά!

Δημοσιεύτηκε: **Τρί Φεβ 22, 2011 10:37 pm**

Nα ρωτησω το αυτονοητο? Ο χρονος παραμενει 1 sec?

Δημοσιεύτηκε: **Τρί Φεβ 22, 2011 11:53 pm**

mr.muffin έγραψε:Nα ρωτησω το αυτονοητο? Ο χρονος παραμενει 1 sec?

Seems we've got a problem here:

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

Σίγουρα υπάρχει λύση που περνάει τα 400.000 σε λιγότερο απο 1 second?

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 12:42 am**

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

Εντάξει τελικά το βρήκα....

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 2:03 am**

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

Εντάξει τελικά το βρήκα....

Aυτα για ν=400k? Eπισεις μ κανει 30 δευτερολεπτα με τεστ case n=100.000

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 2:46 am**

userresu έγραψε:πάρε
company.txt

Το testcase έχει αποτέλεσμα 0;

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 9:51 am**

Και όριο μνήμης πάλι 64 mb? Αν είναι έτσι ο χρόνος εκτέλεσης θα εκτοξευθεί στα ύψη...

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 2:56 pm**

mr.muffin έγραψε:

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

Εντάξει τελικά το βρήκα....
Aυτα για ν=400k? Eπισεις μ κανει 30 δευτερολεπτα με τεστ case n=100.000

Ναι είναι για το testcase που δώσατε στο φόρουμ, και βγάζει αποτέλεσμα 0.

Παρόλα αυτά μένει ο αλγόριθμος να γίνει ακόμα πιο γρήγορος. Έχω ήδη άλλες 2 ιδέες για υλοποίηση...

Spoiler: show: Θα μπορούσα να δώσω μια πληροφορία, αλλά θα θεωρηθεί υπονοούμενο για την λύση μου...

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

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 4:07 pm**

Έχει κανείς τα παλιά test cases να τα ποστάρει..?

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 4:55 pm**

Έλεγα πως είχε δημιουργηθεί ατέρμων επανάληψη τώρα που το εκτέλεσα χαχαχαχ δυστυχώς όμως όχι είναι full αργό...

Ισως φτάει το γεγονός ότι μάλλον έχει πολυπλοκότητα Ο(Ν^3)...χααχαχαχαχ

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 5:06 pm**

Virus•Hacker•Kontos έγραψε:
mr.muffin έγραψε:

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

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

Παρόλα αυτά μένει ο αλγόριθμος να γίνει ακόμα πιο γρήγορος. Έχω ήδη άλλες 2 ιδέες για υλοποίηση...

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

ελεος θα βαρεσω το κεφαλι μου στον τοιχο!!! Πως κανεις 0.4 δευτερα για 400κ Ν??????????!!

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 5:31 pm**

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;
}

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 6:55 pm**

Μισό δεύτερο run time, αποτέλεσμα 0, όμορφα.

Κάποιος να συμπιέσει το test case, ή ακόμη καλύτερα να δώσει ο userresu το seed, έχει ψιλο-ψοφήσει ο server απ'τα κατεβάσματα

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 7:03 pm**

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

#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;
}

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 7:32 pm**

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

+10

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

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

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

EDIT: Μπορεί κάποιος να επαληθεύσει με αυτόν τον test generator, N = 400.000 και με seed = 1000 ( αντι για time(0) ) αν το αποτελεσμά του είναι 413913 ?

Spoiler: show: Αν ναι, μάλλον η λύση μου είναι σωστή και γρήγορη...

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 8:45 pm**

Ohh MY GOD! Why the heck does this happen?

Οκ επομενο βημα ειναι ο χαρδαβελας... οταν ειναι με την σειρα το testcase απο το 1 μεχρι το 400k κανει 10 λεπτα οταν ειναι στην τυχη κανει 0.40 δευτερα.....

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 10:01 pm**

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 με εντελώς αναποδο-ταξινομημένο αρχικό πίνακα...

Δημοσιεύτηκε: **Τετ Φεβ 23, 2011 11:53 pm**

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

εμένα μου βγαίνει 1

(πάω να ξαναδώ τον κώδικά μου)

[edit] sorry λάθος .in

. Ναι, τόσο μου βγαίνει.

μόνο με τον 2ο test case generator του userresu (αν τον έχω κάνει copy-paste σωστά στο Vim) μου βγάζει segmentation fault για οσοδήποτε Ν.

edit2: μάλλον πρέπει να τροποποιήσω τον κυρίως αλγόριθμό μου

Δημοσιεύτηκε: **Πέμ Φεβ 24, 2011 12:24 am**

thetrojan01 έγραψε:
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 για οσοδήποτε Ν.

F**k.
Η ακόμα γρηγορότερη λύση μου κάπου χάνει ενώ τελικά δεν είναι και τόσο πιο γρήγορη όσο περίμενα.
Θα το τσεκάρω, αν και τελικά νομίζω πως την χθεσινή θα αφήσω, γιατι δεν είδα περισσότερο χρόνο απο 0,550 σε κανένα test case με Ν = 400.000...

Δημοσιεύτηκε: **Πέμ Φεβ 24, 2011 1:19 am**

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

pdp forum

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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