1021 Diff

[•pauldb]

Aici puteţi discuta despre problema Diff.

[•6301263]

cat se ia pe bkt?

[•Florian]

Nu inteleg de ce ai vrea sa bagi back la problema asta. Solutia triviala e destul de evidenta. Ia si rezolv-o de 100 daca doresti intr-adevar sa inveti ceva. Succes!

[•dornescuvlad]

Salut! Am un sir de numere formate din -1 si 1, si trebuie sa gasesc un interval [i, j] a.i suma elementelor A, A[i+1], ... A[j - 1], A[j] sa fie egala cu T.Imi poate explica cineva mai pe larg cum procedez?

[•APOCALYPTO]

Salut! Am un sir de numere formate din -1 si 1, si trebuie sa gasesc un interval [i, j] a.i suma elementelor A, A[i+1], ... A[j - 1], A[j] sa fie egala cu T.Imi poate explica cineva mai pe larg cum procedez?

Pai in O(N^2+M) ai putea sa calculezi sumele partiale pentru vectorul A[]  si la pasul i din cei N pasi ai putea afla toate sumele care se termina pe pozitia i si incep pe pozitia j<=i si sa retii intr-un Hash daca o suma a putut fi calculata sau nu.
Bineinteles apoi raspunzi in O(1) la fiecare query.
Idee de 100 de puncte este sa vezi anumite sume sunt calculate(de pana la N/2 ori) de mai multe ori.


Hint: gandeste-te la faptul ca daca la pasul i, suma[i ]=s, atunci la pasul i+1, suma[ i ]=s-1 sau suma[i ]=s+1(numere consecutive). Deci care din sumele partiale calculate la pasii anteriori ar putea,scazute din suma[i+1], sa genereze o suma care sa nu existe in hash(tinand cont ca si sumele deja intrate in hash sunt numere consecutive)?

[•valen.valentin]

E posibil de scos 100 in pascal?

[•valen.valentin]

E posibil de scos 100 in pascal?

La ONI era 0.3 secunde

[•Djok]

Sunt câteva surse în pascal cu punctaj maximal. Probabil trebuie să mai optimizezi ceva.

[•mariak]

Poate sa imi explice cineva, va rog, de ce aceeasi sursa ia 100p pe .campion si 0p pe infoarena
Nu inteleg ce e gresit ma induce in eroare punctajul de pe campion