|
Titlul: 1021 Diff Scris de: Paul-Dan Baltescu din Aprilie 13, 2010, 15:35:54 Aici puteţi discuta despre problema Diff (http://infoarena.ro/problema/diff).
Titlul: Răspuns: 1021 Diff Scris de: George din Octombrie 10, 2010, 17:30:18 cat se ia pe bkt?
Titlul: Răspuns: 1021 Diff Scris de: Florian Marcu din Octombrie 11, 2010, 19:16:15 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!
Titlul: Răspuns: 1021 Diff Scris de: Vlad Eugen Dornescu din Noiembrie 13, 2010, 11:03:28 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? :)
Titlul: Răspuns: 1021 Diff Scris de: Dragos din Noiembrie 13, 2010, 22:22:27 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)? Titlul: Răspuns: 1021 Diff Scris de: Valentin Valeanu din Septembrie 10, 2014, 16:51:03 E posibil de scos 100 in pascal? :readthis:
Titlul: Răspuns: 1021 Diff Scris de: Valentin Valeanu din Septembrie 10, 2014, 16:52:48 E posibil de scos 100 in pascal? :readthis: La ONI era 0.3 secunde Titlul: Răspuns: 1021 Diff Scris de: Valeriu Motroi din Septembrie 10, 2014, 17:41:57 Sunt câteva surse în pascal cu punctaj maximal. Probabil trebuie să mai optimizezi ceva.
Titlul: Răspuns: 1021 Diff Scris de: Kapros Maria din Decembrie 31, 2015, 15:00:09 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 :fighting: ](*,) ](*,) |