164 Struti

[ditzone]

Aici puteţi discuta despre problema Struti.

[cristi8]

eu la concurs am facut-o in O(P*N*M*log(N*M)) .. folosind ceva asemanator cu QuadTree.. numai ca adaptat pentru dreptunghiuri (care mi-a luat ceva timp pentru a-l implementa si depana pentru prima data).. si am luat 20 (eu ma asteptam la vreo 80 de puncte).

acum vad ca se lua 30 cu un algoritm P*N^2*N^2.

..trist, nu ?
 

[•greco]

Trist ca merge asa de prost algoritmul ala. Doar pt. ca e mai complicat nu inseamna ca e mai eficient.

[•filipb]

eu la concurs am facut-o in O(P*N*M*log(N*M))

Un astfel de algoritm este evident mai bun decat P * N^2 * M^2., care lua 30 ( intr-adevar, am conceput testele ca un brute sa ia 30% din teste ), asa k inseamna k implementarea nu este tocmai cea facuta de tine, probabil ai facut operatii in plus care determinau constanta. Si mergea mult mai simplu parerea mea cu AIBuri 2D sau cu segment trees 2D  

[•gogu]

Testele ar fi trebuit sa fie mai echilibrate un pic.
Cu arbori de intervale nu merge mult mai bine decat cu un brute.
Asta pentru ca varianta in O(P*N*M*logN*logM) se detaseaza clar de una in O(P*N^2*M^2) decat cand N si M sunt mari, iar in cazul asta oricum ia TLE. Varianta mea de arbori de intervale, destul optimizata, a luat initial 40. (La concurs 0  ).
Dupa multe, multe, multe optimizari si incercari, am reusit sa iau 100 cu solutia asta, care acum se comporta aproape ca si cum ar fi O(P*M*N).
Apropo, va rog sa nu mai propuneti asa de multe probleme de deque. Sunt deja destule.

[ditzone]

Dupa punctaje se pare ca nu sunt suficiente

[•DeadStar]

Nu ar trebui chiar un pic ridicata limita? Ma tot chinui si nu reusesc sa iau mai mult de 80. Sau recomandati ceva optimizari. 

[•filipb]

Eu nu am facut nici o optimizare in sursa mea. Incearca sa faci dequeul cam asa:

Cod:

while (prim <= ultim && st[prim].poz <= i-DX) 	    prim++;
while (ultim >= prim && st[ultim].val < M[i][j])    ultim--;
st[++ultim].val = M[i][j]; st[ultim].poz = i; 

Eu am facut de 4 ori ceva similar in programul meu si am sub 3 secunde... Si ai grija sa procesezi si perechea inversa (DY, DX) <=> DX != DY. Daca tot nu iti merge, incearca sa citesti cu stringuri...

[•DeadStar]

Stiu sa fac deque, iar daca luam nu luam in considerare dy,dx luam WA nu TLE. Am citit cu stringuri si au mai scazut un pic timpi, dar tot sunt maricei. Tu folosesti cate 2 deque pentru fiecare line/coloana(cum ti-ai ales) + alte 2 deque?

[•filipb]

DA, fac un deque pt. linii, unul pentru coloane si dupa aceea alte doua deque-uri. Singura "optimizare" care o mai vad in sursa mea este ca nu parcurg intotdeauna toata matricea, ci merg de la (1,1) la (m-DX+1, n), de exemplu, in unul din deque-uri...atata tot... si am maxim 2.74 secunde... .

[•DeadStar]

Cod:

TEST 6	...[2.14s]...	OK!
TEST 7	...[2.10s]...	OK!

I-am luat in final capul la strut!

[•filipb]

 

[•ooctav]

Ma puteti ajuta ?
Am complexitatea N * M * P.
Implementat cu STL iau 2 TLE-uri.
Implementat fara iau 1 TLE si 1 WA.
Trebuie sa fac ceva optimizari ?

[•toni2007]

Probabil unul din TLE-uri e WA, asa ca mai bine cauta bug-ul si dupa incearca sa optimizezi .

[•alexandra_sandu]

Puteti mari limita de timp va rog frumos? Am incercat sa trimit 2 surse care luau inainte 100 si acum iau 80 si 90. Sursa mea ia 70 si am complexitatea optima, nu fac niciun calcul inutil.

[•Schumi]

Puteti sa mariti limita? Fara parsare se pot lua maxim 90 de puncte.

[•wefgef]

Am modificat limita de timp la 2 secunde.

[•assa98]

iau TLE pe doua teste. poate sa ma ajute cineva? https://infoarena.ro/job_detail/913886?action=view-source

[•danalex97]

Ai putea sa faci deque de mana in loc de cel din STL.

[•assa98]

pe problema branza luam 40p cu el de mana, pe cand STL ul lua 100...

[•CosminRusu]

Eu la problema asta luam 80 de puncte cu i si j declarate global...
Dupa ce am facut asa

Cod:

for(int i=1; i<=...)

am luat 100 .
Destul de ciudat  . Cam care ar fi explicatia ?

[•assa98]

infoarena.ro/12-ponturi-pentru-programatorii-cc pontul 5 . 

[•CosminRusu]

Eu credeam ca e chiar invers   .
Merci

[•isus]

prea simpla.Cautati "tetris2";