|
Titlul: APM2 Scris de: Andrei Grigorean din Februarie 20, 2012, 10:32:04 Aici se pot pune întrebări legate de problema APM2 (http://infoarena.ro/problema/apm2) de la Runda 1 (http://infoarena.ro/monthly-2012/runda-1) a concursului Infoarena Monthly 2012.
Timpul alocat întrebărilor este de 1 ora. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII. Titlul: Răspuns: APM2 Scris de: Andrei Alexandrescu din Februarie 20, 2012, 19:16:18 In exemplu, daca muchiei de la query-ul 2 (muchia 3, 4) i-ar fi data valoarea 1 atunci nu s-ar putea gasi un apm care sa nu o contina? Adica (1,2); (1,3); (1,4).
Edit: Scuze, I'm blond... Titlul: Răspuns: APM2 Scris de: Mihai Calancea din Februarie 20, 2012, 19:18:25 FARA COMENTARII
Titlul: Răspuns: APM2 Scris de: abcd efgh din Februarie 20, 2012, 19:19:59 Muchiile date pe cele M linii reprezinta (strict) muchiile din APM, sau mai bine zis APM-ul in sine?
Titlul: Răspuns: APM2 Scris de: Mihai Calancea din Februarie 20, 2012, 19:21:26 FARA COMENTARII
Titlul: restictii Scris de: UAIC-Padurariu-Cristian din Februarie 20, 2012, 19:55:41 Nu ar trebuie precizate si restrictiile pentru taxele asociate muchiilor?
Titlul: Răspuns: APM2 Scris de: Mihai Calancea din Februarie 20, 2012, 19:59:11 Taxele sunt pana in 10 000.
Titlul: Răspuns: APM2 Scris de: FMI Ciprian Olariu din Februarie 20, 2012, 20:01:26 Daca am o intrebare A B,atunci in graful initial nu aveam muchie intre A si B?
Titlul: Răspuns: APM2 Scris de: Excelsior din Februarie 20, 2012, 20:14:07 Taxele sunt numere naturale?
Titlul: Răspuns: APM2 Scris de: Mihai Calancea din Februarie 20, 2012, 20:15:53 DA. Scrie si in enunt.
Titlul: Răspuns: APM2 Scris de: Excelsior din Februarie 20, 2012, 20:22:20 De ce ati modificat enuntul?
Initial am crezut ca se cere afisat maximul global. Acum se cere maximul pentru fiecare din cele Q intrebari? Titlul: Răspuns: APM2 Scris de: Andrei Grigorean din Februarie 20, 2012, 20:23:56 Ultima modificare a enuntului a avut loc in data de 18 februarie 2012, ora 12:18:12.
Titlul: Răspuns: APM2 Scris de: Horia Cretescu din Februarie 20, 2012, 21:37:42 Ce complexitate are solutia ofiiciala ?
Titlul: Răspuns: APM2 Scris de: Mihai Calancea din Februarie 20, 2012, 21:38:57 E data la O(N * Q).
Exista mai multe solutii mult mai bune, dar sunt complicate si nu mergeau pentru un concurs de genul asta :) Titlul: Răspuns: APM2 Scris de: Duta Vlad din Februarie 20, 2012, 21:40:59 cam stransa limita aia de timp pt N*Q :annoyed:
Titlul: Răspuns: APM2 Scris de: Horia Cretescu din Februarie 20, 2012, 21:42:43 (N * log(N) * Q) a iesit din timp :sad:
Titlul: Răspuns: APM2 Scris de: Mihai Calancea din Februarie 20, 2012, 21:43:52 Mie imi intra in 0.3 O(N * Q)-ul. Si mai am unul pe idee diferita care intra in 0.5.
Titlul: Răspuns: APM2 Scris de: Duta Vlad din Februarie 20, 2012, 21:47:25 eu am in medie O(Q * log*N) cu disjoint data set, dar m-a batut ultimul test :)
Titlul: Răspuns: APM2 Scris de: Cazacu Alexandru din Februarie 20, 2012, 21:52:09 Mie mi-a intrat in 0.1 cu APM + Q * log N. Pentru fiecare query faci dinamica cu al 2^k-lea stramos sa aflii muchia maxima.
Titlul: Răspuns: APM2 Scris de: Mihai Calancea din Februarie 20, 2012, 21:53:41 Da pai asta e una din solutiile ca lumea :) dar nu era necesara.
@ Vlad Esti sigur? Cred ca estimezi ceva gresit. E cam SF. Eu am 0.3 cu O(NQlog*N) ( uitasem de log*N). Titlul: Răspuns: APM2 Scris de: Duta Vlad din Februarie 20, 2012, 22:00:32 nu aveam nevoie de al 2^k-lea stramos sau rmq, pt ca iti iese un arbore destul de echilibrat cand faci APM-u cu multimi disjuncte, doar daca nu cumva graful e linie :-' probabil am implementat prea din topor
Titlul: Răspuns: APM2 Scris de: Mihai Calancea din Februarie 20, 2012, 22:07:43 Mm ce relevanta are pentru structura arborelui daca faci cu multimi disjuncte sau nu?
Titlul: Răspuns: APM2 Scris de: Duta Vlad din Februarie 20, 2012, 22:13:13 daca nu faci comprimarea drumului, prin modul in care unesti padurile de multimi obtii pe cazul general un arbore destul de echilibrat
Titlul: Răspuns: APM2 Scris de: Mihai Calancea din Februarie 20, 2012, 22:21:54 Inafara de primele 2, testele sunt complet random.. muchii, muchii de query, costuri, tot. Nu stiu ce sa zic. Te-au tradat probabilitatile putin :)).
Btw, daca folosesti doar reuniune dupa rang drumul average e O(log n) nu log*. Probabil ai implementat mai neingrijit, da :). |