390 Poze

[•bogdan2412]

Aici puteţi discuta despre problema Poze.

[•unholyfrozen]

Nu credeti ca ati exagerat putin cu limita de timp?
Nu de alta, dar nici solutia oficiala nu ia 100 de p, iar solutia mea in C++ merge mai repede (pacat ca testul 1 imi iese si mie din timp).

[•devilkind]

probabil ca limita de timp a fost stransa tocmai ptr a nu se trimite sursa oficiala

[•Bluedrop_demon]

Are cineva vre-un hint pentru problema asta... daca e sa iei fiecare matrice posibila si sa o compari cu toate celelalte de aceeasi dimensiune depaseste timpu cu mult  ... Si-atunci cum s-ar putea face ? Ma ajutati putin pls ?

[•bogdan2412]

Poti face cautare binara dupa latura si apoi hash dar e cam greu de gasit un hash bun. Solutia desteapta e asemanatoare cu modul de constructie a unui Suffix Array. Incearca sa vezi cum se poate extinde in 2D.

Limita de timp nu mi se pare stransa...
http://infoarena.ro/job_detail/42264 - hash
http://infoarena.ro/job_detail/42181 - suffix array 2D cu sort din STL (radix e teoretic mai rapid)

[Later edit] Am facut si sursa cu radix si intr-adevar e cam strasa limita (sursa mea mergea asa repede ca aveam pairuri si erau optimizate bine de compilator). Am facut sursa care intra in 1.8 anyway... da' o sa pun limita la 2 secunde totusi...
http://infoarena.ro/job_detail/42578

[•Bluedrop_demon]

Am vazut mai multe probleme care aveau in topicul de pe forum ca se rezolva cu hash. Eu nu stiu la ce se refera si am cautat cu google dar nu cred ca am nimerit ce ma interesa. Pe site-ul de la Ginfo nu ma descurc sa caut (in caz ca e acolo). Am vazut ca articolul de pe pagina principala e din 2005. Stie cineva vre-un site unde as putea gasi ceva despre lucrul cu hash ?

[•astronomy]

http://infoarena.ro/Hashing

[•Bluedrop_demon]

Multumesc mult Adrian. Am citit si ma apuc de implementat. Sper ca am inteles cum trebuie 

[imhsud]

Cred ca solutia cu Suffix Array 2D nu mai intra in timp: http://infoarena.ro/job_detail/731858. Puteti sa verificati, va rog

[•danalex97]

Limita de timp nu e putin cam stransa ?

[•poptibi]

Limita de timp nu e putin cam stransa ?

+1

[•spatarel]

Și mie mi s-a părut limita de timp foarte strânsă.

Inițial am folosit baza 300001 și calculele le-am făcut modulo două numere prime mari (1 000 000 007 și 1 000 000 009). Am luat 80p.

Apoi m-am gândit puțin și am modificat sursa astfel: am folosit două baze (1 000 000 007 și 1 000 000 009) și calculele modulo 2^32 (prin overflow/underflow), eliminând astfel toate operațiile modulo. Am luat 100p cu 372ms și la statistici.

În foarte scurt timp, un elev de-al meu a trimis o sursă cu parsare care a luat 296ms, iar eu am ajuns pe la statistici.