156 Reg

[•domino]

Aici puteţi discuta despre problema Reg.

[•vladcyb1]

calculul x=(x[i-1]*a+b*i) mod c poate fi facut intr-un mod inteligent ceva ? pt ca eu il fac pe int64 si imi mananca mult timp. Poate sa fie si de la solutie care e T*N*logK  

[•greco]

Nu-i buna complexitatea.

[•gogu]

Eu am facut in O(T*N*logN) si a mers dar la limita initial. Mie imi mergea acasa destul de bine dar pe infoarena era extrem de incet din cauza compilatorului freepascal. Mi-am dat seama ca nu face operatia mod bine la int64 asa ca pana la urma am facut ceva de genul asta:

Cod:

 exp:=(a*x[i-1]+b*i);
 x[i]:=exp-c*(exp div c);

La mine acasa merge chiar mai incet asa dar se pare ca pe infoarena merge de cam 3 ori mai repede. E un bug tampit de compilator.

[•svalentin]

interesant acest "bug".. dar nu uita ca pe infoarena se compileaza cu optimizarile activate! Acasa ai incercat cu ele activate? De multe ori schimbari mici de cod, pot duce la schimbari mari de timpi din cauza optimizarilor (compilatorul "vede" ca poate aplica optimizari in noul caz)

hint: treci pe C

[•greco]

Nu e bug... pur si simplu modul in care compilatorul decide ce optimizari sa faca este foarte ciudat, de unde si deviza programatorilor de C: "daca nu merge baga niste instructiuni vide in locuri aleatoare si compileaza din nou". :p

[•gogu]

Sincer, nu cred ca operatorul mod ar fi ceva caruia i-ar trebui optimizari extraordinare si nu ar trebui sa fie influentat in nici un fel de optiuni de compilare (decat daca e dupa un div, caz in care se calculeaza si restul si catul simultan). Acasa am compilat cu fpc 2.0, cu si fara optimizari la optiuni de compilare si am scos timpi aproape identici. La infoarena se compileaza cu versiunea 1.9.4, care cred ca are mult bug-uri. Odata am luat chiar o eroare de compilare si cauza care am vazut-o in borderou era:

Cod:

Free Pascal Compiler version 1.9.4 [2004/08/12] for i386
Copyright (c) 1993-2004 by Florian Klaempfl
Target OS: Linux for i386
Compiling jtemp.pas
jtemp.pas(12,9) Fatal: Internal error 200306091

Va rog sa faceti un update la fpc 2.0 si gcc 4.0.

[•pauldb]

Imi puteti spune cat da pe testul urmator?

5
7 5 11 100 4
6 6 17 100 9
21 6 19 1000 13
3 2 31 1000 5
9 1 37 2000 7

[•DITzoneC]

Cod:

18
44
31
26
36

[•astronomy]

Chiar, acum se poate pune si limita aia la memorie

[•filipb]

fixed

[•bogdan2412]

Pai acum ar trebui reevaluate si toate sursele..

[•domino]

Vom reevalua, dar doar cele din infoarena 2 (restu s-au pierdut).

[•gcosmin]

pare cam aiurea sa puneti alte limite... pare ok faza cu teste schimbate... dar asa... nu stiu... mie asa mi se pare... sa isi zica si altii parerea
plus ca eu daca am sursa de pe infoarena1 tot cu 100 raman.. si nu ar trebui, pentru ca am sursa care folosea mai mult de 7mb.

[•domino]

Daca vrei sa ramai cu 100 de puncte, poti s-o lasi asa:)

[•DraStiK]

Știu ca topicul acesta e foarte vechi, dar am o mare nelămurire:

Cum as putea obține 100p dacă doar declararea unui vector int de 2000000 îmi depășește memoria pe 3 teste.