|
•wefgef
|
 |
« : Februarie 20, 2012, 10:32:04 » |
|
Aici se pot pune întrebări legate de problema APM2 de la 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. |
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•AndrewTheGreat
Strain
Karma: 4
 Deconectat
Mesaje: 15
|
|
« Răspunde #1 : 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...
|
|
|
|
« Ultima modificare: Februarie 20, 2012, 19:25:53 de către Andrei Alexandrescu »
|
Memorat
|
|
|
|
|
•klamathix
|
|
« Răspunde #2 : Februarie 20, 2012, 19:18:25 » |
|
FARA COMENTARII
|
|
|
|
|
Memorat
|
|
|
|
•balakraz94
Strain
Karma: 0
Deconectat
Mesaje: 18
|
|
« Răspunde #3 : 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?
|
|
|
|
|
Memorat
|
|
|
|
|
•klamathix
|
|
« Răspunde #4 : Februarie 20, 2012, 19:21:26 » |
|
FARA COMENTARII
|
|
|
|
|
Memorat
|
|
|
|
•federer
Strain
Karma: -1
Deconectat
Mesaje: 10
|
|
« Răspunde #5 : Februarie 20, 2012, 19:55:41 » |
|
Nu ar trebuie precizate si restrictiile pentru taxele asociate muchiilor?
|
|
|
|
|
Memorat
|
|
|
|
|
•klamathix
|
|
« Răspunde #6 : Februarie 20, 2012, 19:59:11 » |
|
Taxele sunt pana in 10 000.
|
|
|
|
|
Memorat
|
|
|
|
|
•scipianus
|
|
« Răspunde #7 : Februarie 20, 2012, 20:01:26 » |
|
Daca am o intrebare A B,atunci in graful initial nu aveam muchie intre A si B?
|
|
|
|
|
Memorat
|
|
|
|
•excelsior
Strain
Karma: 0
Deconectat
Mesaje: 4
|
|
« Răspunde #8 : Februarie 20, 2012, 20:14:07 » |
|
Taxele sunt numere naturale?
|
|
|
|
|
Memorat
|
|
|
|
|
•klamathix
|
|
« Răspunde #9 : Februarie 20, 2012, 20:15:53 » |
|
DA. Scrie si in enunt.
|
|
|
|
|
Memorat
|
|
|
|
•excelsior
Strain
Karma: 0
Deconectat
Mesaje: 4
|
|
« Răspunde #10 : 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?
|
|
|
|
|
Memorat
|
|
|
|
|
•wefgef
|
|
« Răspunde #11 : Februarie 20, 2012, 20:23:56 » |
|
Ultima modificare a enuntului a avut loc in data de 18 februarie 2012, ora 12:18:12.
|
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•ELHoria
Strain
Karma: 3
Deconectat
Mesaje: 11
|
|
« Răspunde #12 : Februarie 20, 2012, 21:37:42 » |
|
Ce complexitate are solutia ofiiciala ?
|
|
|
|
|
Memorat
|
|
|
|
|
•klamathix
|
|
« Răspunde #13 : 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  |
|
|
|
|
Memorat
|
|
|
|
|
•Vman
|
|
« Răspunde #14 : Februarie 20, 2012, 21:40:59 » |
|
cam stransa limita aia de timp pt N*Q  |
|
|
|
|
Memorat
|
|
|
|
•ELHoria
Strain
Karma: 3
Deconectat
Mesaje: 11
|
|
« Răspunde #15 : Februarie 20, 2012, 21:42:43 » |
|
(N * log(N) * Q) a iesit din timp  |
|
|
|
|
Memorat
|
|
|
|
|
•klamathix
|
|
« Răspunde #16 : 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.
|
|
|
|
|
Memorat
|
|
|
|
|
•Vman
|
|
« Răspunde #17 : Februarie 20, 2012, 21:47:25 » |
|
eu am in medie O(Q * log*N) cu disjoint data set, dar m-a batut ultimul test |
|
|
|
|
Memorat
|
|
|
|
•katakuna
Strain
Karma: 19
Deconectat
Mesaje: 23
|
|
« Răspunde #18 : 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.
|
|
|
|
|
Memorat
|
|
|
|
|
•klamathix
|
|
« Răspunde #19 : 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). |
|
|
|
|
Memorat
|
|
|
|
|
•Vman
|
|
« Răspunde #20 : 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 |
|
|
|
|
Memorat
|
|
|
|
|
•klamathix
|
|
« Răspunde #21 : Februarie 20, 2012, 22:07:43 » |
|
Mm ce relevanta are pentru structura arborelui daca faci cu multimi disjuncte sau nu?
|
|
|
|
|
Memorat
|
|
|
|
|
•Vman
|
|
« Răspunde #22 : 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
|
|
|
|
|
Memorat
|
|
|
|
|
•klamathix
|
|
« Răspunde #23 : 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 . |
|
|
|
|
Memorat
|
|
|
|
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena