Imprimă pagina - 251 Mine

Titlul: 251 Mine
Scris de: ditzone din Iunie 06, 2006, 07:48:46

Aici puteÅ£i discuta despre problema Mine (http://infoarena.ro/problema/mine).

Titlul: Raspuns: 251 Mine
Scris de: Andrei Grigorean din Iunie 06, 2006, 18:43:54

ar fi fain daca nu ati pune limitele la unele probleme asa stranse.

in pascal citirea ia mai mult si chiar e greu de scos 100 pe ele.

un 0.1 in plus la limita nu afecteaza cu nimic, ca doar nu intra brute-ul :P

Titlul: Raspuns: 251 Mine
Scris de: andreit1 din Iunie 06, 2006, 18:57:36

Lasa ca invatam si noi sa parsam citirea... sau si mai bine sa renuntam la pascal!

Titlul: Re: 251 Mine
Scris de: Tiberiu-Lucian Florea din Iunie 06, 2006, 19:08:51

Limita a fost de 0.1 secunde initial.

Titlul: Raspuns: 251 Mine
Scris de: Andrei Grigorean din Iunie 06, 2006, 19:12:50

Citat din mesajul lui: andreit1 din Iunie 06, 2006, 18:57:36

Lasa ca invatam si noi sa parsam citirea...

asta am si facut :P.

Titlul: Raspuns: 251 Mine
Scris de: cristi8 din Iunie 18, 2006, 12:59:29

iau doar 20 pct (in rest WA si pe vreo 4-5 teste (din 25) iau TLE) si nu stiu de ce.
eu tin un min-heap cu nodurile in care se poate ajunge, ordonat dupa costul muchiei care duce in ele.
la fiecare valoare "q" citita iau din heap primul element cat timp costul e mai mic sau egal cu valoarea citita, si adaug in heap toti vecinii nodului/nodurilor extrase.
Am grija sa marchez nodurile "relaxate", si cum am marcat nodul n opresc algoritmul.

----
alta exprimare, poate mai clara:
la fiecare valoare "q" citita (intr-o anumita stare), exista:
- o submultime de noduri in care se poate ajunge (un vector u[] de 0 sau 1)
- o alta submultime de noduri: vecini ai primei submultimi (retinut ca un min-heap in functie de costul muchiei).
ca sa trec de la o stare la alta, iau din a 2a multime (din heap) elementele cu costul <= decat "q" si le adaug la prima multime. bine-nteles, reimprospatez tot-odata si heap-ul cu noile noduri si costuri.
----

ce gresesc?

PS:
daca citesc muchiile cu:

Cod:

  fgets(buf, 100, stdin);
  sscanf(buf, "%d%d%d", &v1, &v2, &c);

dureaza mai mult decat:

Cod:

  scanf("%d%d%d", &v1, &v2, &c);

e normal?

Titlul: Raspuns: 251 Mine
Scris de: Andrei Grigorean din Iunie 18, 2006, 20:15:49

ai grija sa introduci vecinii nodurilor vizitate abia dupa ce termini de scos din heap?

Titlul: Raspuns: 251 Mine
Scris de: cristi8 din Iunie 18, 2006, 22:08:24

nu, de ce ?
uite cum fac:

Cod:

void foo(int val) {
  int x;
  vnod *q;
  while(h[1].c <= val && hn) {
    x = h[1].x;
    h[1] = h[hn--];
    hdown(1);
    if(!u[x]) {
      u[x] = 1;
      for(q = lv[x]; q; q = q->nxt)
        if(!u[q->x])
          hadd(q->x, q->c);
    }
  }
}

unde lv(i) e lista de vecini a nodului i, h e heap-ul (structura cu { int x, c; } reprezentand nodul si costul). hn e dimensiunea heap-ului

Titlul: Raspuns: 251 Mine
Scris de: Paul-Dan Baltescu din August 08, 2006, 20:40:24

In ce complexitate se rezolva problema? :sad:

Titlul: Raspuns: 251 Mine
Scris de: u-92 din August 08, 2006, 23:57:53

eu am facut (M+N)*logN

Titlul: Raspuns: 251 Mine
Scris de: Paul-Dan Baltescu din August 16, 2006, 23:56:54

Eu am reusit sa scot (M+N) * log M...si iau TLE pe 6 teste. Ce inseamna sa "parsezi" citirea? ???

Titlul: Re: 251 Mine
Scris de: Tiberiu-Lucian Florea din August 19, 2006, 03:13:11

Citesti sub forma de string o linie intreaga si calculezi singur valorile din ea prin inmultiri cu 10 si adunari repetate. Cam infect, dar uneori mai e nevoie si de asa ceva. La fel se poate parsa si scrierea, insa eu unul am avut nevoie de scriere optimizata la o singura problema pana acum (de pe SGU cred).

Titlul: RÄƒspuns: 251 Mine
Scris de: Cosmin-Mihai Tutunaru din Martie 12, 2009, 17:31:31

Are ceva mai special testul 6?
Primesc 96 pct,cu WA pe testul 6 ](*,)
Ce poate fi ? :angry:

Titlul: Răspuns: 251 Mine
Scris de: Serban Andrei Stan din Septembrie 28, 2009, 16:30:08

Imi puteti da va rog o idee cum sa fac o citire mai rapida la problema asta?
Eu am incercat sa citesc cu fread tot fisierul intr-un string, si apoi sa lucrez pe acesta. Daca imi las doar citirea in program iau un TLE pe unul din ultimele 2 teste. :-' http://infoarena.ro/job_detail/351561

Titlul: Răspuns: 251 Mine
Scris de: Bogdan-Cristian Tataroiu din Septembrie 29, 2009, 12:16:04

Poti face functia read_file() inline si, de asemenea, poti folosi un pointer la pozitia curenta in sir, in loc de un int.

Un exemplu pentru toata lumea:

Cod:

char *p = s;

inline int read_value() {
    int val = 0;
    for (; '0' <= *p && *p <= '9'; p++)
        val = val * 10 + *p - '0';
    p++;
    return val;
}

a = read_value(); b = read_value();

Facand modificarile astea 2, sursa ta (fara rezolvare, doar citire) intra in timp in 190 ms :). Aparent, nu citirea dureaza cel mai mult la tine, ci ce faci cu vectorul arb in functia cit. Cred ca spargi cache-ul parcurgandu-l in ordine inversa. Incearca sa folosesti altceva decat arbori de intervale.

Titlul: RÄƒspuns: 251 Mine
Scris de: Serban Andrei Stan din Septembrie 29, 2009, 15:09:50

Merci de sfat. Am folosit citirea prezentata de tine, insa ca optimizare am tinut graful fara vectori (o lista cu muchii, si pentru fiecare nod sa tin minte de unde ii incep muchiile). :)

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: ditzone din Iunie 06, 2006, 07:48:46