•wefgef
|
|
« : Decembrie 14, 2008, 14:26:30 » |
|
Aici puteti discuta despre problema Jstc.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•vlad_D
Client obisnuit
Karma: 32
Deconectat
Mesaje: 67
|
|
« Răspunde #1 : Decembrie 16, 2008, 01:41:34 » |
|
care e jmenu la asta? tot iau tle pe 7 teste deci 30 pct. e complexitate mai buna de logN pt Query?
am incercat tot felu de citiri pana si fread.. dar la fel..
sa ma lumineze careva
|
|
|
Memorat
|
|
|
|
•SleepyOverlord
Client obisnuit
Karma: 10
Deconectat
Mesaje: 59
|
|
« Răspunde #2 : Decembrie 16, 2008, 02:51:53 » |
|
Eu am rezolvat-o cu o idee, care mi-a venit de la structurile de date de multimi disjuncte. http://infoarena.ro/job_detail/232778Nu stiu daca asta e si solutia oficiala, o complexitate ar fi foarte greu sa-ti zic pentru query. Cu O(log N) e normal sa iei 30 de puncte.
|
|
|
Memorat
|
God is dead - Nietzsche Nietzsche is dead - God
|
|
|
•CezarMocan
|
|
« Răspunde #3 : Decembrie 16, 2008, 17:35:08 » |
|
Cred ca asa e si solutia oficiala... cel putin eu am luat punctaj maxim cu multimi disjunte. Complexitatea pe query cred ca e ceva de genu log* din numarul de I-uri.
|
|
|
Memorat
|
|
|
|
•SleepyOverlord
Client obisnuit
Karma: 10
Deconectat
Mesaje: 59
|
|
« Răspunde #4 : Decembrie 16, 2008, 21:06:02 » |
|
La multimi disjuncte daca se foloseste numai euristica de comprimarea drumului, complexitatea pe query este Theta(1+log_{2+f/n}(n)), unde f este numarul total al query-urilor (asa am facut eu la problema asta).
|
|
|
Memorat
|
God is dead - Nietzsche Nietzsche is dead - God
|
|
|
•wefgef
|
|
« Răspunde #5 : Decembrie 16, 2008, 22:10:07 » |
|
Mersi Csabi, chiar m-am intrebat de multe ori cat e complexitatea exacta.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•anna_bozianu
|
|
« Răspunde #6 : Decembrie 20, 2008, 11:28:28 » |
|
Am o varianta care mi-a dat 100 de puncte. Pastrez intr-un vector raspunsul imediat la query si actualizez acest raspuns la fiecare operatie insert.
|
|
|
Memorat
|
|
|
|
•gcosmin
|
|
« Răspunde #7 : Decembrie 20, 2008, 13:09:38 » |
|
Am o varianta care mi-a dat 100 de puncte. Pastrez intr-un vector raspunsul imediat la query si actualizez acest raspuns la fiecare operatie insert.
Solutia ta nu ar trebui sa ia 100 de puncte. Va trebui sa schimb niste teste, pentru ca tu ai complexitate N^2. Am mai vazut parca o solutie asa care ia 100. Din pacate nu m-am gandit inainte la solutia asta sa dau teste mai bune
|
|
|
Memorat
|
|
|
|
•anna_bozianu
|
|
« Răspunde #8 : Decembrie 20, 2008, 20:10:47 » |
|
Cred totusi ca timpul e un N^2 puternic amortizat deoarece actualizarea o fac intre penultimul si ultimul element din stiva. In conditiile astea un test "rau" ar trebui sa foloseasca multe inserturi cu distanta foarte mare intre aceste elemente. Ceva de genul IIIIII-de multe ori, EEEEEE- de multe ori apoi i sucesiune de IEIEIEIE intre care sa fie intercalate Q-urile. Banuiesc ca asa ar fi un test care sa imi scoata algoritmul din timp. Poate n-am inteles eu corect solutia oficiala dar am senzatia ca si aceasta s-ar comporta prost intr-un astfel de caz.
LE. @gcosmin ai dreptate. m-am exprimat incorect. am refacut si intradevar acum intra in timp. multumesc pentru lamuriri.
|
|
« Ultima modificare: Decembrie 20, 2008, 22:07:15 de către Bozianu Ana »
|
Memorat
|
|
|
|
•gcosmin
|
|
« Răspunde #9 : Decembrie 20, 2008, 21:17:59 » |
|
Daca te-ai gandit la testul ala puteai sa iti dai seama cate operatii faci (eu tot la testul ala ma gandeam). Sa zicem ca ai N/2 inserturi dupa aia N/2 - 1 erase-uri, si dupa aia insert si erase samd. Tu cand dai de un insert dupa primele N/2 o sa faci N / 2 pasi cel putin, nu? Si asta de cate ori? de N / 4 ori sa zicem: ceea ce duce la N / 2 * N / 4 = N^2 / 8 = O(N^2) calcule. Constantele nu se iau in considerare la complexitate. Solutia oficiala nu face asa. Citeste mai bine. In solutia oficiala raspunusurile se pastreaza si tocmai pentru ca raspunsurile pentru o anumita valoare cresc mereu, le schimb doar acolo unde ma duce drumul cand caut raspunsul. Amortizat nu inseamna ca ai constanta mica, ci ca in medie faci atatea operatii. Aici complexitatea nu e chiar O(1) amortizat ci functia scrisa de Patcas Csaba dar am considerat ca e suficient de mica pentru a o aproxima la 1. Am schimbat testul 8. Am dat reeval la sursele ce au luat 100 inainte. Din pacate multe surse de 100 au picat (doar cateva mai luau 100). Am schimbat limita la 3.5 secunde de la 2.5 (sursa mea intra in 2.2 pe noul test; sper ca e de ajuns acum), dar nu pot sa dau reeval la problema pentru ca am sta o groaza de timp sa termine evalu (cam 2 ore). Asa ca trebuie sa retrimite-ti sursa. Imi cer scuze pentru incurcaturile cu problema asta
|
|
« Ultima modificare: Decembrie 20, 2008, 21:30:57 de către Gheorghe Cosmin »
|
Memorat
|
|
|
|
•shnako
Client obisnuit
Karma: 3
Deconectat
Mesaje: 50
|
|
« Răspunde #10 : Februarie 19, 2010, 10:40:05 » |
|
Imi poate spune si mie cineva de ce iau incorect cu sursa asta ? Mi-am dat teste si merge bine. Stiu ca ia maxim 30 de pct. Cod sters. Nu posta surse ca sa faca altii debug in locul tau. Posteaza eventual ideea, nu implementarea
|
|
« Ultima modificare: Februarie 19, 2010, 17:14:45 de către Paul-Dan Baltescu »
|
Memorat
|
|
|
|
•S7012MY
|
|
« Răspunde #11 : Martie 10, 2011, 17:39:42 » |
|
Cum ati scapat de tle pe testul 8 ?
|
|
|
Memorat
|
|
|
|
•vendetta
|
|
« Răspunde #12 : Ianuarie 16, 2012, 07:24:22 » |
|
I-au 30 de pct cu o sursa pe care luam inainte 100
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #13 : Ianuarie 16, 2012, 15:00:10 » |
|
I-ei TLE? Care sunt id-urile joburilor?
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•S7012MY
|
|
« Răspunde #14 : Ianuarie 16, 2012, 16:18:46 » |
|
Am postat si eu pe pagina cu calibrare limite de timp.
|
|
|
Memorat
|
|
|
|
•ms-ninja
Strain
Karma: 2
Deconectat
Mesaje: 6
|
|
« Răspunde #15 : Martie 26, 2012, 12:05:46 » |
|
Consider ca timpu este prea mic! Am bagat ideea comisiei imi da ok pe 18 teste dar fiind grupate crapa si iau doar 30 pct. Puteti verifica va rog frumos?
|
|
|
Memorat
|
|
|
|
•S7012MY
|
|
« Răspunde #16 : Martie 26, 2012, 12:53:14 » |
|
N-o sa poti lua 100 pt ca trebuie marita limita de timp
|
|
|
Memorat
|
|
|
|
•danalex97
|
|
« Răspunde #17 : Aprilie 17, 2012, 12:02:10 » |
|
Trebuie marita limita de timp.
|
|
|
Memorat
|
|
|
|
|