Pai, tinem un aint si in fiecare nod avem un HLL care e construit din elementele de pe intervalul corespunzator nodului din AINT (in postul anterior am zis un AIB dar nu cred ca merge cu AIB pentru ca nu ai cum sa construiesti HLL-ul pe [a..b] din HLL-ul pe [1..a] si [1..b]). Cand facem query trebuie doar sa facem merge la HLL-urile astea pe intervalele care compun intervalul cerut. Merge-ul se face in O(size).

O solutie care poate aproxima numarul de elemente unice cu o precizie destul de mare si nu foloseste foarte multa memorie, este sa tii un AIB de hyperloglog-uri si atunci complexitatea pe query ar fi .. log N * size(HLL), unde size(HLL) e in jur de 2000 pentru o aproximare foarte buna in practica.

Solutia asta merge online, dar e doar o aproximare.

https://en.wikipedia.org/wiki/HyperLogLog

1) Sorted order means that they are sorted by timestamp and in case of equality, by user id ?
2) Does one need to answer the queries online or offline ?

Problema apare de la faptul ca sursa ta este automat redenumita in Main.java. Clasa ta ar trebui sa se numeasca Main nu BFS.

In loc sa calculezi P(X, K) = probabilitatea sa se aleaga X de K ori calculai !P(X) => probabilitatea sa nu se aleaga X deloc din M extrageri.
Aceasta probabilitate este C(S - vx, M) / C(S, M) , unde S = v1 + v2 ... + vn iar C(n, k) = combinari de N luate cate K. Raportul ala se simplifica intr-un produs de vx termeni pe care il calculai si aveai O(vx) pe test.

Salut,

Runda 2 se tine sambata sau duminica ?

Aparent cred ca undeva ai scris Cvector in loc de CVector sau invers.

Eroarea nu este generata de codul dat de tine ci de ceva ce faci inainte si se reflecta aici. Mai precis tu probabil pui un pointer in vectorul ala care indica spre o zona de memorie nealocata ( sau care nu este alocata programului tau de catre sistemul de operare ) .

Secventa asta de cod

Cod:

while (s % 5 == 0)
    y = y / 5, ++nr;

O sa iti intre in ciclu infinit, deoarece tu pui o conditie pentru s dar nu il modifici in niciun fel. In plus, nu imi dau seama cine e s, pentru ca aparent nu ai niciun s declarat in functie. s e o variabila globala ? In cazul in care s nu e vreo variabila globala cel mai probabil codul ala nici macar nu compileaza.
 
Poti sa te uiti pe infoarena la problema factorial [ 0 ] si cred ca gasesti acolo in comentarii rezolvarea pentru ce vrei tu.

[ 0 ] http://www.infoarena.ro/problema/fact

Salut,

Cred ca limita la problema xmoto e un pic cam stransa. Am o sursa care lua 100 inainte si acum ia 95 cu TLE pe ultimul test.

Cred ca voi cei care sustineti sistemul cu "Sa se califice primii nu stiu cati pe tara" nu sunteti constienti ce inseamna sa ti se predea informatica de catre un profesor pentru care cea mai puternica tehnica de programare este backtracking sau sa stai intr-un loc in care informatica nu e promovata absolut deloc si ajungi sa vezi ce e ala un program in clasa a 9-a.

Sa fim seriosi, nu cred ca e cineva care sa fie din nu stiu ce sat care sa fi ajuns la info in gimnaziu ca s-a apucat el in clasa a 5-a fara niciun fel de indrumare sa lucreze pe infoarena.

Sustin ce zice Mihai Calancea, e greu sa faci ceva de la 0 si oamenii care incearca trebuie motivati.

|| x - y || ^ 2 = (x - y) * (x - y), unde * = produs scalar. Daca oricare vector x e ortogonal cu oricare vector y atunci (x - y) * (x - y) = x * x + y * y, deoarece x * y = y * x = 0. Calculezi x * x si y * y pentru fiecare vector, memorezi in 2 vectori rezultatele si atunci cand generezi matricea d, va trebui doar sa aduni rezultatele din vectorii calculati mai sus.

Fisierele in / out se cheama cmlsc.in/out . Tu le-ai definit cu numele clmsc.

Cred ca "i-ei" "killsiegv 11" pe "testu 7,9,10" din cauza felului in care scrii pe forum. In general primesti semnalul ala de eroare in cazul in care intri pe o zona de memorie care nu este alocata, aka depasesti limitele unui vector. In cazul tau, coada de 200 de milioane de elemente s-ar putea sa iti faca probleme de asemenea. Pe viitor inainte sa pui o intrebare asigura-te ca e macar jumatate din ea corecta gramatical.

Nu trebuie sa dai system("PAUSE") la sfarsit, iar fisierele de intrare ar trebui sa se cheme adunare.in, adunare.out . De asemenea foloseste ifstream , ofstream in loc de fstream .

Nu m-am uitat foarte atent dar cred ca daca nu ai solutie si se ajunge la min = max in while iti cicleaza.

Sau putin mai simplu, ai putea genera un test mare pe calculatorul tau, iar daca lucrezi pe linux poti incerca folosind :
time timeout nr_secunde ./nume_executabil
Aceasta comanda o sa-ti opreasca automat rularea programului dupa nr_secunde.
Ca sa vezi daca programul tau a rulat in mai putin de nr_secunde poti folosi echo $?, care afiseaza valoarea de retur a ultimei comenzi. Daca echo $? iti afiseaza 0 atunci a rulat in mai putin de nr_secunde, daca iti afiseaza 124 programul a fost oprit fortat.

@crash

Numarul e cifre al unui numar n este [ lg (n) ] + 1 . Numarul de cifre al lui n ^ n = [ n lg (n) ] + 1 . Pt n >= 10 , lg (n) >=1 => [ n lg(n) ] >= n  => numarul de cifre al lui n ^ n >= n + 1 . Pentru numerele de la 2 la 10 este observabil foarte usor . Asta daca vrei ceva cat de cat riguros, dar se observa destul de usor ca 1 e singura solutie.

Iti poti descarca testele , atat in-urile cat si out-urile de la atasamente si poti vedea singur ce e gresit.

O prima problema ar fi ca in for-ul unde parcurgi vectorul de directii ai

Cod:

 for (k = 0; j < 4; k++) 

si ar trebui sa ai k < 4, si cred ca in functia de bordare ar trebui sa modifici k >= 1 in k >= 0.

Ceea ce spui tu se cheama produsul scalar al 2 vectori . Gasesti la acest link http://en.wikipedia.org/wiki/Dot_product detalii despre el .

Gasesti in arhiva educationala subsecventa de suma maxima, cel mai lung subsir crescator, problema rucsacului, cel mai lung subsir comun.

Sa inteleg ca nu am permisiunea sa-l vad pt ca se adreseaza doar unei anumite categorii de useri ?

Faci confuzie . Floyd Warshall e O(n ^ 3) unde n e numarul de noduri, la tine ar fi O(n ^ 6), pentru ca numarul de noduri este n ^ 2, unde n e dimensiunea matricii . Din celula i,j poti trece in oricare din cei 8 vecini ? Poti merge si prin celule complementare cu aceea de start sau doar prin cele asemenea ?

Trebuie doar sa astepti . Evaluatorul este blocat si se va debloca in curand .