Am si eu o intrebare in legatura cu testul 48. Ce are asa de special? Am trimis de foarte multe ori sursa si am incercat sa acopar cam orice caz particular si tot nu imi dau seama ce are. Rog pe oricine l-a rezolvat sa-mi dea macar un hint.

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.

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.

Un compilator bun nu poate inlocui cateva optimizari facute de mana. Si pascalul poate fi foarte rapid, doar ca compilatorul de pe infoarena se comporta un pic cam ciudat.
Uite borderoul meu de pascal, facut cu un back de sub 20 de linii.

Cod:

TEST 1	...[0.27s]...	OK!
TEST 2	...[0.29s]...	OK!
TEST 3	...[0.27s]...	OK!
TEST 4	...[0.28s]...	OK!
TEST 5	...[0.01s]...	OK!
TEST 6	...[0.01s]...	OK!
TEST 7	...[0.01s]...	OK!
TEST 8	...[0.01s]...	OK!
TEST 9	...[0.01s]...	OK!
TEST 10	...[0.01s]...	OK!

Am cam trebuit sa optimizez un pic, dar mi se pare normal. In primul rand, cel mai bine e cand variabilele sunt mici si poti sa profiti in plin de cache.

Testele ar fi trebuit sa fie mai echilibrate un pic.
Cu arbori de intervale nu merge mult mai bine decat cu un brute.
Asta pentru ca varianta in O(P*N*M*logN*logM) se detaseaza clar de una in O(P*N^2*M^2) decat cand N si M sunt mari, iar in cazul asta oricum ia TLE. Varianta mea de arbori de intervale, destul optimizata, a luat initial 40. (La concurs 0  ).
Dupa multe, multe, multe optimizari si incercari, am reusit sa iau 100 cu solutia asta, care acum se comporta aproape ca si cum ar fi O(P*M*N).
Apropo, va rog sa nu mai propuneti asa de multe probleme de deque. Sunt deja destule.

"Optimizarea" pe care am facut-o eu a fost de fapt un brute-force in O(N^2*M^2).

Am luat toate submatricele cu dimensiuni intre R*C si N*M ale matricii marite si vad care are media aritmetica maxima.Suma intr-o submatrice se face destul de usor in O(1), cu niste precalculari.Trebuie sa ai grija doar sa trunchiezi rezultatul, nu sa il rotunjesti.
Mai trebuie sa faci cateva mici imbunatatiri, de exemplu sa nu iei submatrici care nu au coltul stanga sus in matricea initiala de NxM, dar e mai simplu si parca mai rapid decat daca faci cu deque, ca in solutia oficiala.

Am irosit cateva ore din viata mea pentru a ajunge la codul asta. E ce se intampla cand esti in vacanta la tara si te plictisesti rau de tot .  

Vorbeam de impartirile care trebuie sa le faci atunci cand reactualizezi numarul tau mare. O impartire se face de 10 ori mai incet decat o adunare sau inmultire pe numere intregi (e ceva de procesor, nu stiu de ce).
Uite bucata esentiala din sursa mea:

Cod:

procedure calc(var a,b,c:numar);
var i:longint;
begin
for i:=1 to b[0] do c[i]:=x*b[i]-y*a[i]; {recurenta, dar nu zic x si y}
c[0]:=b[0];
for i:=1 to c[0] do
 begin
 while c[i]>=base do
               begin
               inc(c[i+1]);
               dec(c[i],base);
               end;
 if (c[i]<0) then
             begin
             inc(c[i],base);
             dec(c[i+1]);
             end;
 end;
if c[c[0]+1]>0 then inc(c[0]);
end;

Chiar daca e in pascal, cu cateva mici trucuri, sursa imi merge in 0.3 secunde pentru n=20.000.

Pentru cei care nu au reusit sa implementeze o ridicare la putere in timp logaritmic, garantez ca merge o implementare directa a recurentei de gradul 2.
Totusi, ca sa intre in timp trebuie sa faci mai multe optimizari la operatiile pe numere mari (de exemplu, folosirea unei baze cat mai mari, cam 10^8, si cand reactualizezi numarul, incearca sa nu faci impartiri).
Asa poti sa intri in 0.5 secunde pe orice test.
Nu ar trebui sa nu merga, pentru ca asimptotic, daca nu folosesti un algoritm  super avansat de inmultire, ca Karatsuba sau FFT, tot O(N^2) ai complexitate.

Cred ca trebuiau facute niste teste putin mai dificile.
Un brute force O(N*K) la care mai adaugi 2-3 linii ia 100 p, deoarece pe cazuri generate random se comporta cam ca un O(N).

Aria am facut-o cu determinanti. Imparteam poligonul in n-1 triunghiuri cu varfuri in punctele p0 pi si pi+1. Tu cum faci?

Testele 5-10 poti sa le iei daca faci doar aria poligonului, puncte fiind pe laturi parca doar la testele 1-4, cele care le iei(asa a fost la mine, dupa ce am ignorat varfurile aflate intre alte 2 varfuri).
Poate nu iei varfurile ca puncte de pe laturi, nu stiu ce sa zic.
Oricum, ti-au iesit testele mai grele, vezi ca poate nu iti merge cmmdc in unele cazuri, nu stiu.

Testele sunt toate aproape de maxim. Incearca sa nu mai folosesti subprograme, ca sunt un pic mai incete. Calculeaza totul in programul principal.
Nu stiu cat de mult o sa te ajute, dar sa stii ca am incercat cu arbori de intervale si imi iese din timp la un test(si de fiecare data e alt test parca, dar).
Nu stiu nici eu ce optimizari sa fac, dar poate e doar fiinca am facut in pascal.

Sa zicem ca sirurile tale sunt a si b de lungime n si m.
Am verificat daca i si j sunt ultimele pozitii la care apare caracterul a in sirurile tale, lucru care il faci in O(1) adica ai pa[n,a]=i si pb[m,b[j]], pa[i,c] este ultima aparitie a caracterului c in primele i caractere ale lui a(la fel si pt pb). Atunci adaugi nr[i,j] la rezultat.

Sorry atunci. Doar ca pe un test maxim care sa fie facut cat mai defavorabil, cred ca programul ar sta cateva secunde bune. Torusi, e O(2^N*N*M) pentru n=20 si M=50, cateva miliarde de operatii.
Sau poate se gaseste foarte repede solutia pe teste random.
E ceva demonstrat in sensul asta?
Oricum, interesanta problema.

Voi ati bagat jumatate din teste de dimensiune maxima?
Initial luam 50 din cauza TLE, si dupa ce am omorat dikjstra cand am in varful heap-ului nodul terminal, am luat 100.
Bagati teste mai echilibrate

probabil alea sunt testele cu raspuns -1 (nu ai solutie)

nr[i,j]=1 daca a[i,j]=1 si x=y[j] altfel calculezi

Felicitari! E chiar bine de stiut ca ne apreciati parerile.
Multumesc!

De ce nu afisati in borderoul de evaluare si timpii de executie?
Poate trimit de mai multe ori surse diferite si sunt interesat sa vad care optimizari merita si ce timpi scot.
De asemenea, s-ar putea face un clasament in functie de timpul de executie al celor care au luat 100, ca si la unele ACM-uri.
Totul e o idee desigur, dar doar zic ca ar merita.

am luat de mai multe ori 80 p la problema asta si pana la urma mi-am dat seama ca problema era de la citire:

while not eoln(f) do
 begin
 inc(n);
 read(f,a[n]);
 end;
readln(f);
while not eoln(f) do
  begin
  inc(m);
  read(f,b[m]);
  end;
while not (a[n] in ['a'..'z']) do dec(n);
while not (b[m] in ['a'..'z']) do dec(m);

Scuze pentru cod, dar dupa ce am adaugat ultimele 2 linii am luat 100. De ce? E o chestie de linux? Nu vad ce ar putea sa fie specific la testele 6 si 9 parca. Clarificati-ma si pe mine daca puteti.

tu ai bagat operatii pe numere mari?

Pentru cei in pascal:
Cred ca am trimis de peste 10 ori sursa si de fiecare data lua 0 p. Si era ciudat, fiindca la mine mergea pe orice test ca si un brute force care lua 40 p.
Pana la urma am setat un vector care era declarat array[1..max] sa fie
array[0..max] si am luat 100.
In windows merge, insa in linux face figuri, asa ca aveti grija la oni, daca lucrati in free pascal de windows sa nu aveti neplaceri dupa