dijagonale!

jel moze pomoc oko ovoga?

mogu da opisem algoritam kako sam radio ali mi nije jasno zasto 2 test primera padaju na vremenu kada bi u najgorem slucaju bilo prolazaka oko 10000*10000/2!!!

pa, to je sasvim dovoljno da bi palo na vremenu :)

Da, to ti je 50 000 000, sto je previse za 1 sekundu. Racunaj oko 10 000 000 za jednu sekundu. Tada neces omasiti :)

aha!
ok, ja sam, ne znam zasto, mislio da moze mnogo vise od 10mil... no dobro, hvala!

Pa asemblerskih operacija moze vise (mada ne znam koliko), ali ovo nisu sve asemblerske sigurno :)

paaa... mozda cu da pokusam ovo da odradim u asembleru... :)
ali, poslao sam sledeci program za zadatak koji sam vec uradio:
...
begin
for i:=1 to 180 000 000 begin end;
end.

i vreme izvrsavanja svih test primera je u opsegu od 0.46 do 0.52 sekunde. :)

ok, razumem da se ovim samo prolazi do 180 miliona i nista se ne obavlja ali ipak je mnogo vise od 10 mil!

pa, sracunaj malo koliko se tebi operacija obavi sa tih 50 000 000* NE ZNAM KOLKO ...
uzmi u obzir i to da se sabiranje najbrze obavlja od svih aritm. operacija..
a ne verujem da server laze :)

ok bato, sto se ljutis! :)
evo sta je bio problem: koristio sam slogove i u tih 50mil sam mnogo puta pozivao razlicite elemente niza sastavljenog od slogova! to oduzima mnogo vremena!
napravio sam 3 niza umesto niza sastavljenog od slogova i problematicni testovi su prosli za manje od pola sekunde!!!
izvinjavam se sto sam vas iscimao bez veze!

poz

ma ne ljutim se bre , sta ti je :)..na koga da se ljutim ?!
izvinjavam se ako je tako delovalo..

[quote author=milan micic link=topic=10238.msg11577#msg11577 date=1163588068]
izvinjavam se sto sam vas iscimao bez veze!
[/q]
zasta se bre izvinjavas ?! :)
samo napred, i uvek pitaj kad ne znas !

U, sto smo mnogo fini :)

Recimo, obicno sabiranje dva broja i dodela nekom (naravno) bi trebalo da bude valjda 4 asemblerske direktive, sto i nije bitno koliko je tacno, vec samo da za neke jednostavnije stvari kad se prevede u masinski kod postaje "komplikovanije"

Na "normalnom" racunar (oni koji se zvanicno koriste na takmicenjima), mozes da ocekujes da ti prodje oko 20,000,000 operacija (cirka), ali moras da pazis da izvrsavanje svake operacije ne zahteva isto vreme. Npr, slogove se trudi da nikad ne koristis, njih uvek mozes da svedes na niz (mozda malo komplikovanije ali brze). Takodje pazi na to na je MOD mnogo spora operacija, pa i nju izbegavaj kad god mozes (ako kao rez treba da das neki broj po modulu m, nemoj da uvek uzimas mod m - uvek mozes da svedes da rez mod m dobije tako sto od rez oduzmes m jedna ili dva puta). Pametno je da, ukoliko niz trebas da sortiras, da na pocetku napravis random permutaciju od njega (inace slozenost nece biti n log n, nego ~n * n - tj. ne bi uvek trebao slozenost (sa informaticke strane) strogo da gledas matematicki tj. O (n * sqrt (n) + n * n) != O (n * n)

Hm, malo je sve to slozenije... u vecini slucajeva nije problem brzina procesora, vec brzina memorije, narocito ako se radi o DP problemu, gde se pristupa nizu/matrici.

Recino:

for (int i=0; i<1000; i++)
   for(int j=0; j<1000; j++)
      Mat[i][j] = ....

Je ili dosta brze, ili dosta sporije od

for (int i=0; i<1000; i++)
   for(int j=0; j<1000; j++)
      Mat[j][i] = ....

Sve zavisi kako procesor keshira memoriju.

Inace, processor na 1Ghz, bi trebao da odradi 1G operacija, ukoliko su medjusobno nezavisne, medjutim to se retko desava :) jel for petlja sama po sebi ima deo i<1000;i++, sve uzastopne operacije koje su zavisne.