774 Jstc

[•wefgef]

Aici puteti discuta despre problema Jstc.

[•vlad_D]

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

[•SleepyOverlord]

Eu am rezolvat-o cu o idee, care mi-a venit de la structurile de date de multimi disjuncte.

http://infoarena.ro/job_detail/232778

Nu 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.

[•CezarMocan]

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.

[•SleepyOverlord]

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).

[•wefgef]

Mersi Csabi, chiar m-am intrebat de multe ori cat e complexitatea exacta.

[•anna_bozianu]

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.

[•gcosmin]

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

[•anna_bozianu]

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.

[•gcosmin]

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

[•shnako]

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:

 ... 

Cod sters. Nu posta surse ca sa faca altii debug in locul tau. Posteaza eventual ideea, nu implementarea

[•S7012MY]

Cum ati scapat de tle pe testul 8 ?

[•vendetta]

I-au 30 de pct cu o sursa pe care luam inainte 100

[•wefgef]

I-ei TLE? Care sunt id-urile joburilor?

[•S7012MY]

Am postat si eu pe pagina cu calibrare limite de timp.

[•ms-ninja]

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?

[•S7012MY]

N-o sa poti lua 100 pt ca trebuie marita limita de timp

[•danalex97]

Trebuie marita limita de timp.